## 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 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 is called *periodic *if there exists such that . The smallest such is called the *period *of .

**Theorem: ***Let be a cycle of length . Then, and if then .*

**Proof: **We recall that by definition there exists such that

Thus, it clearly follows that

Also, if then we see that

so that .

From this it follows that:

**Corollary: ***The image of a cycle of length under the isomorphism from previous posts is a periodic matrix of period .*

**Proof:** To see that is periodic we merely notice that

Also, recalling that the inverse of a group isomorphism is a group isomorphism we see that if then

so that . Thus, is a periodic matrix with period as was to be shown.

*Remark: *For those more acquainted with group theory this really is just a specific case of the fact that if are groups and an isomorphism then , where 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 can be written as the product of commuting periodic matrices.*

**Proof: **Let , then we know that for some . But, we know that every permutation can be written as the product of disjoint cycles. Thus, there exists disjoint cycles such that

Then,

But, by the corollary to the last theorem we know that is a periodic matrix. Thus, the theorem will be proven if we can prove that the matrices all commute. But, this follows immediately since

for all . The conclusion follows.

**References:**

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

No comments yet.

## Leave a Reply