Permutation matrices

 The symmetric group Sn for n > 0 is the set of permutations of n distinct elements. We have seen the cycle notation representation, but we can also use permutation matrices, which are matrices whose entries are all ones and zeros, with the rule that every row and every column has a single one in it, all the other entries equal to zero.

Lemma: The identity matrix for In for n x n matrices is a permutation matrix.

Proof: By definition, the identity matrix has ones on the main diagonal and zeros in every other position.

Here is a table showing how S3 can be written as 3x3 permutation matrices. For example the permutation (123) is represented by the matrix which moves column 1 of the identity to column 2, column 2 of the identity to column 3, and column 3 of the identity to column 1.

In some books, rows are moved instead columns, but this way, multiplying the matrices left to right gives the same result as combining the permutations left to right.

 

Cycle notation is more compact than permutation matrix representation, but multiplying 0-1 matrices is a very easy operation, especially since we know if we get a one in a row or column, we can immediately fill in zeros in the rest of both the row and column.

Next time, we will use the Cayley table in a special form that will let us turn any group of order n into a permutation group representation of nxn matrices.