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?

Improve this question
$\endgroup$
4
  • 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, 2013 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, 2013 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, 2013 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, 2013 at 21:35

1 Answer 1

Reset to default
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.

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.