# Complexity of transposing matrices represented as list of row or column vectors

Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix

|1, 2, 3|
|4, 5, 6|
|7, 8, 9|


is $\Omega(n^2)$ a lower bound for transposing? Assume the matrix is not always square. I have to touch each element at least once, because going from 2 x 5 to 5 x 2 matrix for example, will mean going from a list of 5 lists to a list of 2 lists, so I can't really do any tricks with the array indices, right?

Is there a faster way to transpose matrices?

• Depending on your application, you can have O(1) transpose for your matrix class by switching the indices, i.e. translate m[i][j] to m[j][i] transparently. – adrianN Mar 20 '13 at 10:35
• The trick @adrianN mentions might work very nicely. You might also be interested in cache-oblivious matrix transposition algorithms if you have a practical application. – Juho Mar 22 '13 at 23:20
• @adrianN, great solution for square matrices thanks. Perhaps my understanding of run-time is flawed, but how would diagonally swapping elements of an arbitrarily large array be O(1) ? For an array of size NxN, i have to do at minimum N^2 - N swaps? Each swap would involve at least 3 steps like temp = m[i][j], m[i][j] = m[j][i], and m[j][i] = temp? Please elaborate, thank you. – amallya Mar 23 '13 at 20:19
• @amallya: What adrianN means is: Given some vector $(a_0,\dots,a_{(k\cdot l)-1})$ which represents an $k\times l$-matrix and an access function $f(i,j)=a_{i*k+j}$ for $0\leq i < k,0\leq j < l$. If you transpose your matrix your access functions changes to $f^T(i,j)=a_{j*k+i}$ for $0\leq j < k,0\leq i < l$. The vector stays the same you just use different addresses. – frafl Mar 23 '13 at 21:35

If the matrices are stored in the usual way, that is as long vectors, then the complexity is $\Theta(n^2)$. The reason is that if all the off-diagonal entries in the matrix are different, you will need to change all of them, and there are $n^2-n$ of them.