How to transpose a matrix?

[George Lin]

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

[Marilyn de Queiroz]

Can you state the problem in pseudocode?

[Steve Fahlbusch]

Set a flag - true if transposed, false otherwise

Have the access methods swap the indicies if transposed.

[George Lin]

Steve,

Originally posted by Steve Fahlbusch:
Set a flag - true if transposed, false otherwise

Have the access methods swap the indicies if transposed.

I can not understand your idea since it is so brief. :-) Could you provide some sample implementation please? I think it just needs several lines.


regards,
George

[George Lin]

Marilyn,

Originally posted by Marilyn de Queiroz:
Can you state the problem in pseudocode?

I think my question is how to write pseudocode from my problem -- if I can do that, I have no question. :-)

Anyway, why you are confused with my problem, do not understand transpose of a matrix or some other points?


regards,
George

[Charles Lyons]

Firstly, how are you storing your matrix - as a 2-dimensional array, a collection of objects or something else?

I don't think it is possible to do an O(1) transposition, unless you've got some clever OO mechanism which can simply relabel a row as a column and vice-versa. Even then, you'll have n rows/m columns to relabel, so the order of complexity will not be constant and will depend on the size of matrix. Probably the best you will get is O(log[n]), which I think only applies when the matrix is square? The 'blind' algorithm takes an [n][m] array and converts all entries to the [m][n] transposed array, using two loops, and will get you at worst O(n^2).

Try Googling around for matrix transposition algorithms; failing that, I'm sure there are books on the subject (probably covering hundreds of pages just for this one algorithm!)

Good luck!
[ January 07, 2006: Message edited by: Charles Lyons ]

[Steve Fahlbusch]

Assuming that you have some implemenation of matrix that will allow for direct access to any element. So you have an accessor:

getElement( i, j )

Which will return the ith,jth element of the matrix: return matrix( i, j )

change that to:

    getElement( i, j ) {
        if Transpose {
             return matrix ( j, i );
        else
             return matrix ( i, j );
    }
    

[fred rosenberger]

do you need to PHYSICALLY transpose the matrix? or do you just need to ACCESS the transposed matrix?

if you need (for some reason) to actually move the elements around, you can't do it in O(1).

But if all you have to do is access an element of the transposed matrix, then Steve has given you the answer.

What is a transposed matrix? it is the matrix created when every element at (x,y) gets moved to position (y,x). so really, all you have to do is access the elements in a different way, and you're done.

[George Lin]

Steve,

Originally posted by Steve Fahlbusch:
Assuming that you have some implemenation of matrix that will allow for direct access to any element. So you have an accessor:

getElement( i, j )

Which will return the ith,jth element of the matrix: return matrix( i, j )

change that to:

    getElement( i, j ) {
        if Transpose {
             return matrix ( j, i );
        else
             return matrix ( i, j );
    }
    

Your idea is very smart! But I need to transpose the matrix in-place other than from output level (showed in your sample).

Do you have any good ideas?


regards,
George

[George Lin]

fred,

Originally posted by fred rosenberger:
do you need to PHYSICALLY transpose the matrix? or do you just need to ACCESS the transposed matrix?

if you need (for some reason) to actually move the elements around, you can't do it in O(1).

But if all you have to do is access an element of the transposed matrix, then Steve has given you the answer.

What is a transposed matrix? it is the matrix created when every element at (x,y) gets moved to position (y,x). so really, all you have to do is access the elements in a different way, and you're done.

Thank you very much for your reply!

I need to transpose the matrix PHYSICALLY in-place. When mentioning O(1), I mean the space complexity is O(1) -- not the time complexity.

Do you have any good ideas?


regards,
George

[George Lin]

Charles,

Originally posted by Charles Lyons:
Firstly, how are you storing your matrix - as a 2-dimensional array, a collection of objects or something else?

I don't think it is possible to do an O(1) transposition, unless you've got some clever OO mechanism which can simply relabel a row as a column and vice-versa.

About the storage data structure -- we can use any common data structure if transpose operation can be completed with only O(1) space complexity.

I think you mid-understand my problem a bit -- when mentioning O(1), I mean the space complexity, not the time complexity.


regards,
George

[Charles Lyons]

My apologies - mostly the talk is about time complexity because memory is so cheap these days, so naturally I assumed this was your intention!

Now, I'm a little rusty on complexities, so please say if I'm talking rubbish. O(1) space complexity means the algorithm uses the same amount of storage memory space regardless of how large the input is.

I'm going to assume you're using a 2-dimensional array to store the data, and since that array could be of any datatype, I'll call it "Arr[][]". I'll let the first dimension be the rows, and the second the columns within each row. For an m x n matrix we therefore have Arr[m][n]. Clearly this array will have to be as large the matrix, and therefore will occupy more memory space for larger input - but this isn't the fault of the algorithm (only the input).

To be honest, I can't see a way to transpose a general m x n matrix without having a second Arr[n][m] array to put it in. We cannot dereference the first array to resize it, then reference its entries! We would have to have two arrays in memory.

However, we can optimise for a square n x n array with data Arr[n][n], since they we don't have to change the sizes of each dimension. We can create an O(1) space algorithm by swapping entries on either side of the principle diagonal, and I think this sketch should do it:

Arr[n][n] matrix;
/* i is rows of the original matrix */
for(int i=0; i < matrix.length; i++) { 
    /* j is columns of original matrix */
    for(int j=0; j < matrix[i].length; j++) {
        if(i == j) {
            /* Principle diagonal entries don't change */
            continue;
        }
        /* Otherwise only swap entries above the diagonal */
        if(j > i) {
            Arr swap = Arr[i][j];
            Arr[i][j] = Arr[j][i];
            Arr[j][i] = swap;
        }
    }
}

I think that should give O(1) space complexity - we are only declaring i, j and swap for each iteration, and these will always be declared for any size array. In addition, we only have swap for those entries above the diagonal, which is significantly less than half the matrix - for an n x n this is actually n*(n-1)/2.

The time complexity of this algorithm is O(n^2), making it inefficient. As I said previously, there are O(log[n]) algorithms, but they use caching of pieces of the matrix for efficiency, and this increases the space complexity. I would think this trade-off is probably worthwhile in the long-run.

I'm not so sure about the general m x n problem - please repost if you can clarify or have any further ideas...

[Steve Fahlbusch]

George,

there are many ways of accomplishing this and since this is not a real problem (ie: this is a made-up homework assignment) why don't you post the full requirements, that way we can address you solution to the problem statement.

For instance, if this is for a data structures course the approach might be much differnt than an algorithms course. (and my previous posts reflected an approach i would expect from my students, but lets see what is expected).

[Paul Clapham]

It's quite interesting how the entries in this thread are pretty much the same as the entries in another thread on the Sun Java forum.
[ January 08, 2006: Message edited by: Paul Clapham ]

[George Lin]

Steve,

Originally posted by Steve Fahlbusch:
George,

there are many ways of accomplishing this and since this is not a real problem (ie: this is a made-up homework assignment) why don't you post the full requirements, that way we can address you solution to the problem statement.

For instance, if this is for a data structures course the approach might be much differnt than an algorithms course. (and my previous posts reflected an approach i would expect from my students, but lets see what is expected).

It is not from a homework. The whole requirements are too long -- so I just post a spcific requirement independent part. The total goal is to do some matrix computation with very very limited storage -- for an embedded system. The time to do the computation is not a mandatory requirement -- only the additional space required needs to be limited to a minimal level.

Anyway, do you have any good ideas?


regards,
George

[George Lin]

Charles,

Originally posted by Charles Lyons:
My apologies - mostly the talk is about time complexity because memory is so cheap these days, so naturally I assumed this was your intention!

Now, I'm a little rusty on complexities, so please say if I'm talking rubbish. O(1) space complexity means the algorithm uses the same amount of storage memory space regardless of how large the input is.

I'm going to assume you're using a 2-dimensional array to store the data, and since that array could be of any datatype, I'll call it "Arr[][]". I'll let the first dimension be the rows, and the second the columns within each row. For an m x n matrix we therefore have Arr[m][n]. Clearly this array will have to be as large the matrix, and therefore will occupy more memory space for larger input - but this isn't the fault of the algorithm (only the input).

To be honest, I can't see a way to transpose a general m x n matrix without having a second Arr[n][m] array to put it in. We cannot dereference the first array to resize it, then reference its entries! We would have to have two arrays in memory.

However, we can optimise for a square n x n array with data Arr[n][n], since they we don't have to change the sizes of each dimension. We can create an O(1) space algorithm by swapping entries on either side of the principle diagonal, and I think this sketch should do it:

Arr[n][n] matrix;
/* i is rows of the original matrix */
for(int i=0; i < matrix.length; i++) { 
    /* j is columns of original matrix */
    for(int j=0; j < matrix[i].length; j++) {
        if(i == j) {
            /* Principle diagonal entries don't change */
            continue;
        }
        /* Otherwise only swap entries above the diagonal */
        if(j > i) {
            Arr swap = Arr[i][j];
            Arr[i][j] = Arr[j][i];
            Arr[j][i] = swap;
        }
    }
}

I think that should give O(1) space complexity - we are only declaring i, j and swap for each iteration, and these will always be declared for any size array. In addition, we only have swap for those entries above the diagonal, which is significantly less than half the matrix - for an n x n this is actually n*(n-1)/2.

The time complexity of this algorithm is O(n^2), making it inefficient. As I said previously, there are O(log[n]) algorithms, but they use caching of pieces of the matrix for efficiency, and this increases the space complexity. I would think this trade-off is probably worthwhile in the long-run.

I'm not so sure about the general m x n problem - please repost if you can clarify or have any further ideas...

I have found a solution to deal with the general m*n problem, please reference to "ACM Algorithm 467: Matrix Transposition in Place".

Anyway, I am very interested in the O(log[n]) time complexity algorithms, do you know where can I find related resources?


regards,
George

[Steve Fahlbusch]

George,

I would still set a flag, and swap the indices in all of the accessors.

Size complexity ( 1 bit - boolean value )

Time complexity O(1)

- so as i said earlier, change the accesors to check the flag and all setters/getters using swapped indicies
[ January 09, 2006: Message edited by: Steve Fahlbusch ]

[George Lin]

Steve,

Originally posted by Steve Fahlbusch:
George,

I would still set a flag, and swap the indices in all of the accessors.

Size complexity ( 1 bit - boolean value )

Time complexity O(1)

- so as i said earlier, change the accesors to check the flag and all setters/getters using swapped indicies

[ January 09, 2006: Message edited by: Steve Fahlbusch ]

In my question, I mean the space complexity -- not the time complexity -- to be O(1).

Anyway, I do not quite understand your points. Could you provide some pseudo-code please?


regards,
George

[Steve Fahlbusch]

George,

I know you mean size - look at my last post size complexity is 1 bit (not order of 1, but just 1 bit) - or normally stated - to implement a transpose that has a flag (boolean) and then changing all accessors to swap indicies if transposed (see earlier post) then the overhead would be one bit. In java this usually means throwing away a whole boolean, which is almost always smaller than one element of a matrix (one would expect say a double, or at least a float).

As to the pseudocode - that was provided for you in a previous post (for the getElement) you just need to implment that approach for any / all direct accessors of the underlying data (whatever that would be, you didn't specify). Normally this would only be two getElement and setElement. I would probably suggest a dynamic single indexed array - but that's up to you, and i couldn't recommend anything without seeing the requirements (as that will probably impact the implementation).

[Jeff Verdegan]

George, I helped you in Sun's forums. That's the last time I help you here or there. You should know better than to crosspost by now.

[Joel McNary]

Originally posted by Jeff Verdegan:
George, I helped you in Sun's forums. That's the last time I help you here or there. You should know better than to crosspost by now.

Whoa down there, pardner. Not everyone reads the Sun forums (I don't -- I find the people there to generally be too acerbic for my liking) and not everybody reads JavaRanch (fools!), so George was just trying to get the most amount of exposure to his problem. You certainly didn't have to answer him here (or there).

We do have a crossposting policy at JavaRanch -- choose one forum on the Ranch in which to ask your question. But we don't discourage people from posting the same question to multiple sites.

That said, I'm reading this and thiking that this is not really beginner's stuff anyway, so I'm going to move this to the intermediate forum. Please continue the discussion (nicely) there.