# Cycles of Permutation Related to Rectangular Matrix Transposition

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.

## 1 Answer

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