Gfyuki

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<i,jleq n$ 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?

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).