4
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – adrianN Mar 20 '13 at 10:35
  • $\begingroup$ 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. $\endgroup$ – Juho Mar 22 '13 at 23:20
  • $\begingroup$ @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. $\endgroup$ – amallya Mar 23 '13 at 20:19
  • 1
    $\begingroup$ @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. $\endgroup$ – frafl Mar 23 '13 at 21:35
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.