Transpose a Matrix

Transposing a matrix swaps its rows and columns. Whatever sat in row i, column j of A ends up in row j, column i of the result, usually written Aᵀ. Picture flipping the grid over its main diagonal, the line from the top-left corner to the bottom-right: the cells on that line stay put and every other cell jumps to the mirror position.

The shape changes too. A matrix with 3 rows and 4 columns becomes one with 4 rows and 3 columns, because each of the 4 old columns is now a row. Nothing is lost and nothing is computed: the same 12 values just live at new addresses. In the visualizer, watch the pointer on A move along a row while the pointer on Aᵀ moves down a column.

One rule covers every cell: B[j][i] = A[i][j]. Two nested loops visit each cell of A in row-major order and copy it to the swapped position in B.

B = new matrix[cols][rows]
for i in 0 .. rows-1:
  for j in 0 .. cols-1:
    B[j][i] = A[i][j]
return B

The first line matters more than it looks: B must be created with cols rows and rows columns, or the very first write outside a square matrix goes out of bounds. The loops do one read and one write per cell, so the whole thing costs rows × cols steps, which is exactly what the counters above show.

A square matrix can be transposed without a second matrix. Every cell above the diagonal has a partner below it, so you swap the pairs:

for i in 0 .. n-1:
  for j in i+1 .. n-1:
    swap(A[i][j], A[j][i])

The inner loop starts at i + 1 so each pair is swapped exactly once. Start it at 0 instead and every pair is swapped twice, which puts the matrix back the way it was. Non-square matrices cannot use this trick, because a 3 × 4 grid has no room to become 4 × 3 in the same memory, so in practice you build a new one. Python has a one-liner for that: list(zip(*a)) unpacks the rows and zips them into columns.

• Linear algebra. Dot products, least-squares fits and covariance matrices are all written with a transpose, and a matrix equal to its transpose is called symmetric.
• Tables and data. A spreadsheet of records in rows becomes a table of fields in rows, which is what most charting tools want.
• Speed. Memory is fastest when read in a straight line. An algorithm that walks columns can transpose once and then walk rows.
• Interviews. Transpose Matrix is a warm-up on its own, and it is the first half of rotating a matrix in place.

• Allocating the wrong shape. Making the result rows × cols works on a square and crashes on anything else.
• Swapping every pair twice. In the in-place version the inner loop must start at i + 1, not 0.
• Confusing it with rotation. A transpose reflects; a rotation turns. Compare the two on the rotate page with the same grid.

Every operation on these pages costs one step per cell. See how that growth compares with other algorithms: Big-O Playground →