[Math] What mathematical algebra explains sequence of circular shifts on rows and columns of a matrix

foundationsgroup-theorymatricespermutationsrubiks-cube

Consider a simple matrix (3X3) with entries thus:
[1 2 3;
4 5 6;
7 8 9;]

Circular shifts can be performed on any row or any column thus:
row-(1/2/3)-(right/left) and column-(1/2/3)-(up/dn)

Examples: R1-right transforms [1 2 3] to [3 1 2].
R3-left makes [7 8 9], [8 9 7].
Also: C1-up converts [1 4 7] to [4 7 1].

Now these moves can be performed repeatedly on the initial matrix.
Assume a sequence of moves thus:
R1-r, C1-up, R3-left, C2-dn, R2-r, C3-up

This converts the initial matrix to this matrix (you can work this to confirm):
[4 9 1; 6 7 3; 8 5 2].

Now assume that you know NONE of these moves?

Given simply the 2 matrices: the initial and the final, what method shall help me find the moves that lead from the initial to final, or final to initial. The latter shall be an inverted sequence of each former moves' reverse.

What algebra goes here in?
Please point to any and every resource like group theory, number theory, permutation theory, sequential circuits etc…

This matrix 'jumbling' if you say so, inspired in part from the Rubik's Cube finds some interesting applications in cryptography and data transformation.

I look forward to answers and some future collaboration.

Best Answer

Permutation theory is all that's needed.

I'll assume that both dimensions of the matrix are at least 2. (If one of the dimensions is $1$, of course only cyclic permutations are possible).

If all the entries are different and both the sides of the matrix have odd lengths, then only even permutations of the elements are possible, because each of the basic moves is an even permutation. (If there are at least one pair of equal elements, then we can always find an even permutation that looks like any odd one, so in that case all rearrangements of the elements are possible).

If at least one of the lengths are even, then every permutation is possible.

In the $2\times 2$ case it is easy to make any desired permutation. The following algorithm works if there are at least 3 columns (and, mutatis mutandis, if there are at least 3 rows):

  1. Put the right elements into position in the two first cells of the first row. Let's call these elements $X$ and $Y$. (This is easy enough because at this step we don't care where any of the other elements go in this phase).

  2. If the permutation we still need to do at this point is odd, then slide the bottom row (if there's an even number of columns) or the last column (if there's an even number of rows) once in your favorite direction. Now the permutation is even.

  3. Express the desired permutation as a sequence of evenly many swaps of elements that are not $X$ or $Y$ (which are already in position). Perform each swap by doing the following three steps:

  4. Let the elements we want to swap be $A$ and $b$. Perform a sequence of moves that place $a$ and $b$ next to each other beneath $X$ and $Y$. Again it it immaterial what happens to element that are not in $\{A,B,X,Y\}$.

  5. Do C2d R2r C2u R1r C2d R2l C2u R1l C2d R2r C2u R2l. This will exchange $a$ and $b$ with the side effect of also exhanging $x$ and $y$, but leaves everything else unchanged:

    X Y m m    X q m m    X q m m    X A m m    m X A m    m q A m    m q A m
A B n n -> A Y n n -> n A Y n -> n B Y n -> n B Y n -> n X Y n -> X Y n n
p q . .    p B . .    p B . .    p q . .    p q . .    p B . .    p B . .
p q . .    p q . .    p q . .    p q . .    p q . .    p q . .    p q . .

   m Y A m    Y A m m    Y q m m    Y q m m    Y X m m    Y X m m
-> X B n n -> X B n n -> X A n n -> n X A n -> n B A n -> B A n n
   p q . .    p q . .    p B . .    p B . .    p q . .    p q . .
   p q . .    p q . .    p q . .    p q . .    p q . .    p q . .

  6. Do the opposite of the moves from step (4).

Since steps (4), (5), (6) are repeated an even number of times, their net effect is to leave $x$ and $y$ where they started out. But that means the desired permutation has been achieved.

Related Question