# Non-simplifiable permutation matrices

The permutation matrices for $$2$$ and $$3$$ dimensions look like this:

• $$2$$-dimensional:

$$M_1^{2d} = \left(\begin{matrix} 1 &0\\ 0 &1\end{matrix}\right), \qquad M_2^{2d} = \left(\begin{matrix}0 &1\\1 &0\end{matrix}\right)$$

• $$3$$-dimensional:

$$M_1^{3d} = \left(\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}\right), \qquad M_2^{3d} = \left(\begin{matrix}1&0&0\\0&0&1\\0&1&0\end{matrix}\right), \qquad M_3^{3d}=\left(\begin{matrix}0&1&0\\1&0&0\\0&0&1\end{matrix}\right)$$

$$M_4^{3d} = \left(\begin{matrix}0&0&1\\0&1&0\\1&0&0\end{matrix}\right), \qquad M_5^{3d} = \left(\begin{matrix}0&1&0\\0&0&1\\1&0&0\end{matrix}\right), \qquad M_6^{3d} = \left(\begin{matrix}0&0&1\\1&0&0\\0&1&0\end{matrix}\right)$$

Matrices $$M_1^{2d}$$ and $$M_1^{3d}$$ are the identity matrices. Furthermore, $$M_2^{3d}, M_3^{3d}, M_4^{3d}$$ are permutations of only two elements (thus their action is described by only $$M_2^{2d}$$).

The only complete permuations (where each of the elements is permutated) are $$M_2^{2d}$$, $$M_5^{3d}$$, $$M_6^{3d}$$. One conditions for that is $$\mbox{Tr}(M)=0$$.

Does this subset of permutation matrices have a special name? Is there a way to construct them easily?

• These are the permutations with no fixed points; also called derangements. – Sudarsan Dec 16 '14 at 2:19
• What about a matrix like $$\pmatrix{&1\\1\\&&&1\\&&1}$$ This doesn't keep anything fixed, but it doesn't move every element to every space. In a sense, this one is described by $M_2^{2d}$. Do you want to include things like this? – Ben Grossmann Dec 16 '14 at 2:21
• @Omnomnomnom Oh, I didn't see this coming, only wrote it up to d=3, and thought I have covered everything important. Your example is a double-application of $M_2^{2d}$. Now the Derangement covers the case when no place is fixed, including your example. Is there a way to exclude such examples as you gave aswell? – Mario Krenn Dec 16 '14 at 2:26
• By the cycle decomposition theorem, the permutations you want are exactly those corresponding to cycles of length $d$. – Ben Grossmann Dec 16 '14 at 2:27
• Ah OK, I thought so but was not sure whether in higher dimensions something "unexpected" can happen. So, for a given d-dimensional space, there are only (d-1) non-simplifiable permutation matrices - which are exactly the cyclic ones. Do I understand that correctly? – Mario Krenn Dec 16 '14 at 2:33

It looks like you want the permutations corresponding to all cycles of length $d$. We can characterize these permutations as follows:

Let $\sigma_d$ denote the permutation $i \mapsto i+1 \pmod d$, corresponding to the matrix $$\pmatrix{ &&&&1\\ 1\\ &1\\ &&\ddots\\ &&&1 }$$ The cycles of length $d$ on $d$ elements are exactly those that can be written as $\tau \sigma _d \tau^{-1}$, where $\tau$ is an arbitrary permutation on $d$ elements.

In general, there will be $(d-1)!$ such permutations out (of the $d!$ total permutations).

Such a permutation that is not simply a power of $\sigma_d$: take $1 \mapsto 2 \mapsto 4 \mapsto 3$, as given by $$\pmatrix{ &&1\\ 1\\ &&&1\\ &1 }$$ The above is not a power of $$\pmatrix{ &&&&1\\ 1\\ &1\\ &&1 }$$

• Shouldn't it be $(d-1)$ instead of $(d-1)!$? If yes, then I understand it. – Mario Krenn Dec 16 '14 at 2:35
• Not quite. You're just think about the powers $\sigma_d ^k$ of $\sigma_d$. Of course, when $d = 3, (d-1) = (d-1)!$. We need to think bigger here. – Ben Grossmann Dec 16 '14 at 2:36
• The counting method involved to prove $(d-1)!$ is pretty straight-forward to understand. Lets say you have $d$ elements and WLOG, pick the first element. The first element has $d-1$ places to go to (if it sits in the first place then it completes a cycle). Now, pick the element where the first element went to; this particular element has $d-2$ places to go to (cannot go to 1st place or sit at its own place). And so on. In the end we see that the number of permutations with only one "cycle" is exactly equal to $(d-1)!$. You can make the proof more rigorous but this is just the sketch. – Sudarsan Dec 16 '14 at 2:39
• Oh very nice, now I see it: There is 1 identity, 6x 2-dim subset, 1x 2-dim^2, 8x 3-dim subset, 3 cyclic, 4 anticyclic: 23 matrices. 4!=24, so one additional matrix, exactly that one you show. Very interesting. Thanks alot for that "Fun with Matrices 101" :) – Mario Krenn Dec 16 '14 at 2:56