MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$

How can the first element and the size of the next cycle in the permutation $\mathcal{P}(v_i)$ of the entries of $v$ be calculated, when $\mathcal{P}(v_i)$ represents the transpose $A^T\in\mathbb{C}^{n\times m}$ of $A$, i.e. when $A^T_{rs}=\mathcal{P}(v_i)_{n*r+s}$?

Background of the question is to calculate the matrix transpose with a minimal number of assignments and only one additional temporary value.
If for example a cycle were $(a,b,c)$, then using the extra variable $t$, the part of the permutation related to the cycle could be calculated as $t:=a; a:=b; b:=c; c:=t;$

Being able to calculate the first element and the size of the cycles is important to avoid having to remember the elements that already have been permuted.
By the first element of the next cycle I mean the entry of $v$ with the smallest index, that has not yet been permuted.

share|cite|improve this question
up vote 1 down vote accepted

I just found the paper "In-Place Transposition of Rectangular Matrices" by Fred G. Gustavson and Tadeusz Swirszcz, which provides a solution for the problem.

An online version of the paper can be found here:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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