# Conditions when a permutation matrix is symmetric

I am now playing with permutation matrices, http://mathworld.wolfram.com/PermutationMatrix.html.

Also, there is a similar discussion: Symmetric Permutation Matrix. I want to ask more details than this one.

As we know, a permutation matrix is orthogonal, i.e., $$E^T=E^{-1}$$. I am interested in when it is symmetric, i.e., $$E^T=E^{-1} = E$$

Suppose

1. Start from an identity matrix $$I_n$$.
2. $$n$$ can be even or odd number.
3. Pick $$(i,j)$$, where $$0 and $$i, j$$ are integer. Exchange $$i$$-th and $$j$$-th columns of $$I_n$$ (identity matrix) and get $$E$$. Then $$E$$ is symmetric. This is because $$E_{ii}=E_{jj}=0$$ and $$E_{ij}=E_{ji}=1$$.
4. Based on 3., if I pick a number of sets $$(i,j)$$, $$(k,l)$$, $$(q,r), \ldots$$, without repeated index in each $$(\cdot,\cdot)$$, and permute columns of $$I_n$$ according to these sets, then the resulting permutation matrix $$E$$ is symmetric.

One key thing here is "without repeated index in each $$(\cdot,\cdot)$$". This is because if I do $$(1,2)$$ and $$(2,3)$$ for $$I_3$$ for example, I get

$$\begin{bmatrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix},$$

which is not symmetric. In this case, I repeat $$2$$ in each suit.

Is the above correct? Or I miss some key assumptions?

• Yes, in general the permutation is idempotent when is a disjoint product of fix points and cycles of length $2.$ – Phicar Apr 19 at 23:41
• Yes, it's correct. A permutation matrix describes a permutation $\pi$. You want $E^2 = I$, so $\pi\circ\pi = id$. – amsmath Apr 19 at 23:42

You’re correct!

We can think of the action of $$E$$ on the set of $$n$$ standard basis vectors as a permutation $$\sigma$$ on $$\{1,\dots,n\}$$ and vice versa.

Let $$E$$ be symmetric, and let $$i$$ be the only nonzero entry in the first row. This means that $$e_{1i}=e_{i1}$$ by symmetry. Thus $$E$$ swaps the first and the $$i^{th}$$ standard basis vectors, so $$(1~i)$$ is a cycle in the cycle decomposition of $$\sigma$$. This argument applies to the rest of the rows to show that $$\sigma$$ is a product of disjoint transpositions.

As you have noted condition for a permutation matrix $$E$$ to be symmetric is that $$E^{-1}=E$$, and this condition can be expressed as $$E^2=I$$.

Interpreting the last condition as repeating the permutation is identity. So this represents a permutation that is its own inverse. That is if $$E$$ sends a basis vector $$v$$ to $$W$$ $$E^2=I$$ implies $$Ew=v$$. (possible that $$v=w$$)

So this corresponds to a permutation where an element is fixed, or if it sends $$x$$ to $$y$$ then it has to send $$y$$ to $$x$$. Thus this consists of many disjoint swaps (and possibly some fixed points).

In group theory it is a permutation of cycle type corresponding to the partition of $$n$$ into $$2$$'s and $$1$$'s. For example $$9=2+2+2+ 1^6$$ (that is 1 repeated six times).