# Number of permutation cycles in matrix transposition

I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/

The matrix can be thought of as a permutation and its transposition as another permutation. I need to convert the first one into another. I have found a relation between the Cycles in the Permutation and the number of swaps required as:

Minimum Swaps = Total Elements in Permutation - Number of Cycles

However, I don't know how to calculate the matrix of size $2^a 2^b$ where $a+b \leq 500000$.

• The point of the problem is for you to solve it by yourself. You're not going to learn anything if someone solves it for you. – Yuval Filmus Jun 25 '13 at 4:06
• I am not asking for a complete answer. I just want to learn on how it can be done. I am just asking for ideas. Nothing more. – divanshu Jun 25 '13 at 22:08

Let's take a simple example: $$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}' = \begin{pmatrix} a & d & g \\ b & e & h \\ c & f & i \end{pmatrix}.$$ So we need to exchange $(b,d),(f,h),(c,g)$, i.e. the answer is 3. Now try to generalize this to $A \times B$ matrices. Obtain a formula, substitute $A = 2^a$ and $B = 2^b$, and find a way to efficiently compute the result modulo a small prime $p$.
When $A = 2^a$ and $B = 2^b$, things look nicer. The permutation taking a position in the original matrix to the corresponding position in the transposed matrix corresponds to left shift by an amount $a$. Suppose $g = \mathrm{gcd}(a,b)$ and $a' = a/g,b' = b/g$. We can now think of the operation as a left shift by the amount $a'$ of a string of length $a'+b'$ over an alphabet of size $G = 2^g$. The number of orbits is then the number of necklaces of length $a'+b'$, which has an explicit formula. (The shift amount doesn't matter since $a'$ is invertible modulo $a' + b'$ due to $(a',b')=1$.)
• How far did you get in my algorithm? Did you find a formula for arbitrary $A,B$? When $A = B$, at least, it's not that difficult. You can start with that case. – Yuval Filmus Jun 26 '13 at 2:30
• Ok. So suppose $N = 2^n$. How can you compute $N(N-1)/2 \pmod{p}$ efficiently? Hint: You never need to actually compute $N$. – Yuval Filmus Jun 26 '13 at 16:05
• I recommend you take some small cases (not necessarily powers of $2$), compute the result, and try to generalize. There is probably a simple formula in the case $A \neq B$ as well. Don't expect me to solve your problem for you. – Yuval Filmus Jun 26 '13 at 21:08