Abstract Nonsense

Crushing one theorem at a time

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<q<p 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<q<p then 1<p-q+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

Advertisements

November 7, 2010 - Posted by | Algebra, Halmos, Linear Algebra, Uncategorized | , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: