Matrix Transpose

The transpose of a matrix is formed by turning all rows into columns (and columns into rows). Formally, for a matrix $A$, its transpose $A^T$ is defined by $(A^T)_{ij} = A_{ji}$, meaning the element in row $i$, column $j$ of $A^T$ comes from row $j$, column $i$ of $A$. If $A$ has size $m \times n$, then $A^T$ will have size $n \times m$.

In the context of computer vision and linear algebra, matrices often represent linear transformations, images, or coordinate changes. The transpose operation is fundamental: for example, the transpose of a transformation matrix often corresponds to changing between row-vector and column-vector conventions, and for orthogonal matrices, $A^{-1} = A^T$. In implementation terms, transposing is just reindexing: you are not changing values, only where they are stored.

---

1. Background Knowledge

• A matrix is a rectangular array of numbers with $m$ rows and $n$ columns, often written as $m \times n$.
• The transpose $A^T$ swaps the roles of rows and columns:
• Row 0 of $A$ becomes column 0 of $A^T$.
• Column 1 of $A$ becomes row 1 of $A^T$, and so on.

If $A$ is:

$$A = \begin{bmatrix} a & b & c \\ d & e & f \end{bmatrix}$$

then:

$$A^T = \begin{bmatrix} a & d \\ b & e \\ c & f \end{bmatrix}$$

This shows both the shape change ($2 \times 3 \to 3 \times 2$) and the index swap.

---

2. Algorithm / General Approach

The general pattern:

• Create a new matrix $B$ with dimensions n x m if $A$ is m x n.
• For each element at position (i, j) in the original matrix $A, copy it to position (j, i) in the new matrix$B.

In pseudocode-like terms:

• Outer loop over rows of $A$.
• Inner loop over columns of $A$.
• Assign B[j][i] = A[i][j].

No advanced algorithms are needed; it is a direct, double-loop transformation.

---

3. Step-by-Step Strategy

Assuming:

• Input: 2D array A with m rows and n columns.
• Output: 2D array B which will be n x m.

Steps:

1. Read dimensions

• Let m = number of rows in A.
• Let n = number of columns in A.

2. Allocate result matrix

• Create B with size n rows and m columns.

3. Nested loops for copying

• For i from 0 to m - 1:
• For j from 0 to n - 1:
• Set B[j][i] = A[i][j].

4. Return or print B

• Depending on the platform, either return B or print it in the expected format.

Example (in a C-like pseudocode):

// A: m x n
int B[n][m];
for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 B[j][i] = A[i][j];
 }
}

---

4. Common Pitfalls

• Wrong dimensions of result matrix:
• Forgetting to allocate n x m and instead allocating m x n again.
• Index mix-up:
• Writing B[i][j] = A[j][i] (wrong) instead of B[j][i] = A[i][j] (right).
• In-place transpose mistakes (if required):
• For non-square matrices, in-place transpose in a flat array is tricky; if the problem does not explicitly demand in-place, use a separate matrix.
• For square matrices, you must swap only elements above/below the diagonal once; double-swapping reverts changes.
• Off-by-one errors in loops:
• Make sure loops use < with the correct bounds (i < m, j < n).

---

5. Time & Space Complexity

• Time Complexity:

• You visit each element exactly once and do a constant-time assignment, so the time is:

• $O(m \cdot n)$

• Space Complexity (with a separate matrix):

• You store an additional n x m matrix:

• $O(m \cdot n)$

• Space Complexity (for in-place transpose of a square matrix only):

• If done carefully, it can be:

• $O(1)$ extra space (just a temporary variable for swaps).