Algorithm

What is a transpose of a Matrix?

The transpose of a matrix is obtained by interchanging the rows and columns of the original matrix.

The rows of the original matrix become columns of the transpose matrix and the columns of the original matrix become rows of the transpose matrix.

How to transpose a matrix?

Create a new matrix
Start traversing the current matrix row-wise.
Copy all elements of first row of input matrix to first column of new matrix.
Repeat the process for all rows in the input matrix for consecutive columns of the new matrix.
At the end of the process, the new matrix will be a transpose of input matrix.


#include <stdio.h>
#define N 3   // Defining the size of the matrix

// Structure to store a matrix
struct Matrix {
    int mat[N][N];
};

// Function to compute the transpose of a matrix
void transpose(struct Matrix *input, struct Matrix *output) {
    int i, j;

    // Loop through each element and swap rows with columns
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            output->mat[i][j] = input->mat[j][i];
        }
    }
}

// Driver code
int main() {
    // Initialize the matrix
    struct Matrix mat1 = { 
        { {1, 2, 3},
          {4, 5, 6},
          {7, 8, 9} } 
    };

    struct Matrix mat2; // To store the transposed matrix
    int i, j;

    // Call the transpose function
    transpose(&mat1, &mat2);

    // Print the transposed matrix
    printf("Transposed matrix is:\n");
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", mat2.mat[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Complexity Analysis

Time Complexity: O(N × N) This is because we iterate through each element of the matrix exactly once. For a matrix of size N × N, there are N² elements, so the total work done is proportional to N².

Space Complexity: O(N × N) We use an additional matrix to store the transpose, which requires the same amount of space as the original matrix (N² elements). Apart from this, only a few integer variables are used, which take constant space.