# Proving that an algorithm can generate all permutations of a matrix

I have a matrix

$$\begin{bmatrix}a & b\\\ c & d\end{bmatrix}$$

and I want to generate all 24 possible permutations of the elements of the matrix, e.g.

$$\begin{bmatrix}b & a\\\ c & d\end{bmatrix}, \begin{bmatrix}a & c\\\ d & b\end{bmatrix}...$$

using a particular procedure:

1. for each column, permute the elements of the column
2. for each row, permute the elements of the row
3. for each column, again permute the elements of the column

In each of these cases, the permutation applied need not be the same between rows/columns.

It's my gut feeling that this set of permutations could generate any permutation of a starting $$M\times N$$ matrix, but I'm not really sure how to go about proving it. I've shown that it works for $$2\times 2$$ and $$3\times 3$$ matrices, but I was wondering how should I approach proving this for $$M\times N$$ matrices?

I saw these two posts, but neither of them quite answered my question, since the row/column permutations they considered were constrained:

What permutations of matrix entries do row and column transpositions generate?

Do cyclic permutations of rows and column entries generate all permutations?

I also saw a third post that was asking a very similar question, but only did the first two steps (column permutation followed by a row permutation). Clearly in their case, they couldn't generate all permutations of a $$2\times 2$$ matrix since the procedure could only generate $$16$$ unique matrices from a starting $$2\times 2$$ matrix, less than the $$24$$ unique permutations of the starting matrix.

• I understand that you allow only operation on a single column or row in one step? not to be permuted whole columns/rows? Jun 8 at 12:12
• @Widawensen I can understand Steps 1, 2 and 3 of the procedure (which seem perfectly clear), but I cannot understand your question. Jun 8 at 13:42

Ok, I think I may have a proof that is satisfactory for my purposes.

Proof by induction. If a permutation $$\sigma$$ of a matrix $$\mathbf{A}$$ comprised of $$n$$ individual row and column permutations can be written in the form $$C_{post}RC_{pre}$$ (where $$C$$ is a sequence of permutations applied to individual columns of the matrix and $$R$$ is a sequence of permutations applied to individual rows of the matrix), then a sequence of $$n+1$$ individual row/column permutations formed by applying an additional permutation after $$\sigma$$ can also be written in the form $$C_{post}RC_{pre}$$.

Base case: the identity permutation $$\sigma_I(\mathbf{A}) = \mathbf{A}$$ is of the form $$C_{post}RC_{pre}$$ where $$C_{post}$$, $$C_{pre}$$ and $$R$$ are all empty sequences.

Consider now the permutation $$\sigma$$ which is comprised of $$n$$ row and column permutations: $$\sigma(\mathbf{A}) = (C_{post}R_0C_{pre})(\mathbf{A})$$

Now consider adding a single permutation (either a row permutation $$\sigma_{R_i}$$ or a column permutation $$\sigma_{C_j}$$). There are two cases: $$\sigma^{\prime}(\mathbf{A}) = (\sigma_{R_i}\sigma)(\mathbf{A})$$ $$\sigma^{\prime\prime}(\mathbf{A}) = (\sigma_{C_j}\sigma)(\mathbf{A})$$ In the case of $$\sigma^{\prime\prime}$$, an additional column permutation is applied, which does not change the form of $$\sigma$$, so $$\sigma^{\prime\prime}$$ can be written as $$C^{\prime}_{post}R_0C_{pre}$$.

In the case of $$\sigma^{\prime}$$, we notice that the last three terms are in the form $$R_{post}CR_{pre}$$: $$\sigma^{\prime} = \sigma_{R_i}C_{post}R_0$$

A sequence of row permutations followed by a sequence of column permutations, followed by a sequence of row permutations can also be written as a sequence of column permutations followed by a sequence of row permutations followed by a sequence of column permutations. That is,

$$\exists R^{\prime}, C^{\prime}_{pre}, C^{\prime}_{post} : R_{post}CR_{pre} = C^{\prime}_{post}R^{\prime}C^{\prime}_{pre}$$

Therefore, we can rewrite $$\sigma^{\prime}$$: $$\sigma^{\prime} = C^{\prime}_{post}R^{\prime}C^{\prime}_{pre}C_{pre}$$

Therefore, a sequence of $$n + 1$$ individual row/column permutations formed by applying an additional permutation after a sequence of $$n$$ row/column permutations which is in the form $$C_{post}RC_{pre}$$ can also be written in the form $$C_{post}RC_{pre}$$. Since this is true for the base case ($$n = 0$$), and is true for $$n + 1$$ if $$n$$ is true, then it is true generally for any number of individual row/column permutations.