Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.