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:
- for each column, permute the elements of the column
- for each row, permute the elements of the row
- 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.
Best Answer
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.