Abstract Nonsense

Permutations (Pt. IV Consequences for Permutation Matrices)

Point of post: This will be a relatively short post discussing a nice corollary of the last theorem in the last post relating to permutation matrices. In essence, it shows that every permutation matrix may be decomposed into the product of commuting periodic matrices.

Motivation

Despite the developed of permutation matrices in our discussion was to give a succinct and intuitive proof for a theorem in the next post, there’s no reason the information can’t go both ways. In the last post we showed that every element of $S_n$ may be decomposed into the product of disjoint cycles that every permutation matrix may be decomposed as the product of the image of cycles. So, let’s explore what the image of cycles look like.

The image of cycles are periodic

In general a matrix $A$ is called periodic if there exists $k\in\mathbb{N}$ such that $A^k=I$. The smallest such $k$ is called the period of $A$.

Theorem: Let $\sigma\in S_n$ be a cycle of length $p>1$. Then, $\sigma^p=\text{id}_{[n]}$ and if $1 then $\sigma^q\ne\text{id}_{[n]}$.

Proof: We recall that by definition there exists $a_1,\cdots,a_p\in S_n$ such that

$\sigma(x)=\begin{cases}a_{k+1\text{ mod }p} & \mbox{if} \quad x=a_k\text{ }k\in[p]\\ x & \mbox{if} \quad x\ne a_k\text{ }k\in[p]\end{cases}$

Thus, it clearly follows that

$\sigma^p(x)=\begin{cases} a_{k+p\text{ mod }p} & \mbox{if}\quad x=a_k\text{ }k\in[p]\\ x & \mbox{if}\quad x\ne a_k\text{ }k\in[p]\end{cases}=\begin{cases}a_k & \mbox{if} \quad x=a_k\text{ }k\in[p]\\ x & \mbox{if}\quad x\ne a_k \text{ }k\in[p]\end{cases}=\text{id}_{[n]}$

Also, if $1 then $1 we see that

$\sigma^q(a_{p-q+1})=a_{p+1\text{ mod }p}=a_1\ne a_{p-q+1}$

so that $\sigma^q\ne\text{id}_{[n]}$. $\blacksquare$

From this it follows that:

Corollary: The image of a cycle $\sigma\in S_n$ of length $p$ under the isomorphism $\theta$ from previous posts is a periodic matrix of period $p$.

Proof: To see that $P_{\sigma}$ is periodic we merely notice that

$P_{\sigma}^p=\theta(\sigma)^p=\theta\left(\sigma^p\right)=\theta\left(\text{id}_{[n]}\right)=I$

Also, recalling that the inverse of a group isomorphism is a group isomorphism we see that if $P_{\sigma}^q=I$ then

$\sigma^q=\theta^{-1}\left(P_{\sigma}\right)^q=\theta^{-1}\left(P_{\sigma}^q\right)^{-1}=\theta^{-1}\left(I\right)=\text{id}_{[n]}$

so that $q\geqslant p$. Thus, $P_{\sigma}$ is a periodic matrix with period $p$ as was to be shown. $\blacksquare$

Remark: For those more acquainted with group theory this really is just a specific case of the fact that if $G,G'$ are groups and $\phi:G\to G'$ an isomorphism then $\text{ord}(g)=\text{ord}\left(\phi(g)\right)$, where $\text{ord}$ is the order of the element.

Main Theorem

As the heading suggested in this second we prove the seminal theorem, namely

Theorem: Every element of $\text{PermMat}_n$ can be written as the product of commuting periodic matrices.

Proof: Let $P\in\text{PermMat}_n$, then we know that $P=P_{\pi}$ for some $\pi\in S_n$. But, we know that every permutation can be written as the product of disjoint cycles. Thus, there exists disjoint cycles $\sigma_1,\cdots,\sigma_k\in S_n$ such that

$\pi=\sigma_1\cdots\sigma_k$

Then,

$P=P_{\pi}=\theta\left(\pi\right)=\theta\left(\sigma_1\cdots\sigma_k\right)=\theta(\sigma_1)\cdots\theta(\sigma_k)=P_{\sigma_1}\cdots P_{\sigma_k}$

But, by the corollary to the last theorem we know that $P_{\sigma_k}$ is a periodic matrix. Thus, the theorem will be proven if we can prove that the matrices $P_{\sigma_1},\cdots,P_{\sigma_k}$ all commute. But, this follows immediately since

$P_{\sigma_1}\cdots P_{\sigma_k}=\theta\left(\sigma_1\cdots\sigma_k\right)=\theta(\sigma_{\pi(1)}\cdots\sigma_{\pi(k)})=P_{\sigma_{\pi(1)}}\cdots P_{\sigma_{\pi(k)}}$

for all $\pi\in S_k$. The conclusion follows. $\blacksquare$

References:

1. Halmos, Paul R. ” Finite-dimensional Vector Spaces,. New York: Springer-Verlag, 1974. Prin