# Transpose a matrix without a buffering one

How is it possible to transpose a `MxN` matrix without using a "buffering" matrix? In the latter case it's easy and quite the "classic" approach...

Given a `matrix[M][N]`, I would like to put it into a `void transpose_matrix(int matrix[][])` function which operates directly on the matrix passed as reference which, as previosly said, would edit the matrix memory space to transpose its elements.

e.g:

A =

``````1 2 3 4
5 6 7 8
9 1 2 3
``````

A after transposing itself (without pretty printing):

``````1 5 9 2
6 1 3 7
2 4 8 3
``````

How would A looked like in a `NxM` matrix:

``````1 5 9
2 6 1
3 7 2
4 8 3
``````

Thanks!

: Printing the matrix as if it was actually a "new" `NxM` matrix.

• Without seeing how the matrix will look in NxM form, I can only guess what you mean. Do you mean you have your MxN matrix in a linear array, interpreted as a matrix, and since your NxM matrix will physically fit into the same linear storage, you want to apply a transposing in-place in this linear array? – Doc Brown Jan 31 '15 at 9:12
• By how is it possible, are you asking how to do it? (In which case, the answer is don't -- link to LAPACK etc) Or are you asking how it is done in some particular framework/hardware (such as how it is done in LAPACK, or How is it done in AMD64 cpus). Or perhaps how could it be done in hardware (It would be easy to build hardware that could transpose any matrix up to a given size as a non-sequential operation) – Lyndon White Jan 31 '15 at 12:35

Doing that efficiently is complex.

Wikipedia has a nice article on the subject: In-place matrix transposition with many interesting references.

A simple "follow-the-cycles" C implementation with O(1) auxiliary storage requirement (and heavily non-consecutive memory accesses) is:

``````/// \param[in] m input matrix
/// \param[in] h number of rows of \a m
/// \param[in] w number of columns of \a m
///
/// Performs in-place transposition of matrix \a m.
void transpose(double m[], const unsigned h, const unsigned w)
{
for (unsigned start = 0; start <= w * h - 1; ++start)
{
unsigned next = start;
unsigned i = 0;
do
{
++i;
next = (next % h) * w + next / h;
} while (next > start);

if (next >= start && i != 1)
{
const double tmp = m[start];
next = start;
do
{
i = (next % h) * w + next / h;
m[next] = (i == start) ? tmp : m[i];
next = i;
} while (next > start);
}
}
}
``````

You can find a faster (C++) implementation requiring O(MN) auxiliary storage, one bit per element, here (the In-place transposition of a matrix question on Stackoverflow). Also take a look at Transpose a 1 dimensional array, that does not represent a square, in place.

PS in a number of circumstances it isn't necessary or desirable to physically reorder a matrix to its transposed ordering: it could be enough to provide options to specify that certain matrices are to be interpreted in transposed order.

Some details about the above algorithm (assuming the input matrix `A(3;4)` of your question):

The first chunk: (`do``while`) is a sort of sequence generator:

``````next-sequence  start     next    i
-----------------------------------
                0        0    1
[1,4,5,9,3]        1        1    5       <-
[2,8,10,7,6]       2        2    5       <-
[3,1]              3        1    1
[4,5,9,3]          4        3    3
[5,9,3]            5        3    2
[6,2]              6        2    1
[7,6]              7        6    1
[8,10,7]           8        7    2
[9,3]              9        3    1
[10,7]            10        7    1
              11       11    1
``````

Not every sequence is useful:

• sequences of length 1 (`i == 1` e.g. `` and ``) mean no data motion and can be skipped;
• sequences where the final value of `next` is smaller than `start` can be skipped since they are sub-sequences of an already seen sequence.

Second chunk (`if`) will perform the data motion described by a sequence.

E.g. `[1,4,5,9,3]` means the value in position 4 goes to position 1, value in position 5 goes to position 4 … while position 1 goes to position 3 (written using the standard notation for cycles/permutations it's `(1 3 9 5 4)`).

``````(position % h) * w + position / h;