How to transpose a matrix?

Hello everyone,


I am wondering how to transpose a matrix (m * n) with only constant space complexity O (1). (The transpose algorithm should execute/operate on the original matrix.)


thanks in advance,
George

Erm, O(1) matrix transposing is completely impossible. O(1) means that the algorithm would run in a constant time, regardless of the size of the input matrix.

Are you sure you don't mean O(n)? That would mean that the time it takes the algorithm to run has a strictly linear correlation with the input matrix's size.

Also note that copying a matrix is also an O(n) algorithm, so, strictly speaking, copying the input elements to temporary matrix in transposed order, and assigning the referenced input matrix to the resulting matrix would still be O(n).

Hope that helps.

codergeek42,




Thank you very much for your comments. In my question, I mean space complexity is O(1) -- not time complexity.

Anyway, do you have any good ideas?


regards,
George

The are alot of good packages out there that does this for you, for example in java there is the Jama package.. I would say google that and look at the algorithims yoruself.

tragen,




Thank you very much for providing the information. I have read related information from JAMA,

http://math.nist.gov/javanumerics/jama/

I am not sure whether the matrix transposition implementation of Jama package requires only constant additional space complexity O(1). Are you sure about that?


regards,
George

If the matrix is stored as a 2-dimensional array M, then transposing just means M[i][j] is set to M[j][i] and vice versa for all i and j within the dimensions. The basic operation is just a swap: t = M[i][j]; M[i][j] = M[j][i]; M[j][i] = t. Iterate over all (i, j) with i < j and you're done. The only space overhead is the temporary variable t and the variables i and j controlling your loops, i.e., constant space complexity.