2
$\begingroup$

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,j\leq 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?

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

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.