Ttgjyuk

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

$$beginbmatrix0 & 0 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 endbmatrix,$$

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