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}$ 


**Question:**  

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.



Cycles of Permutation Related to Rectangular Matrix Transposition
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:  

<http://www.orcca.on.ca/conferences/cca2008/papers/gustavson.pdf>


