7.05 Binary and permutation matrices

A binary matrix contains elements that are either 0 or 1.

So for instance, this means that \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} , and \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}are all binary matrices.

A permutation matrix of order n is an n \times n (square) binary matrix with every row and column containing exactly one 1, with all other elements 0.

In other words, a permutation matrix is either the identity matrix or else the identity matrix with one or more rows swapped around.

Here are some examples:

\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix}

Note most importantly that, above and below, or to the left and to the right, of each occurrence of 1 are zeros. Each 1 has its own row and column.

The word permutation refers to a specific order or arrangement and stems from the Latin word "mutare" meaning to change or mutate. This is exactly what happens when we apply a permutation matrix to a column matrix.

Look at this matrix product:

\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix}= \begin{bmatrix} b \\ c \\ a \end{bmatrix}

Notice how the position of the 1's in the permutation matrix dictates the re-ordering of the elements in the column matrix.

We know that there are six possible orderings of the letters a,b, and c given as:

Corresponding to these are the six order 3 permutation matrices given as:

P_1= \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, P_2= \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, P_3= \begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}

P_4= \begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}, P_5= \begin{bmatrix} 0 & 0 & 1\\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}, P_6= \begin{bmatrix} 0 & 0 & 1\\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}

Each of these matrices can be applied to the ordered triple abc (written as a column matrix) to produce one of the six arrangements of the letters.

Consider the product given as P_3 \begin{bmatrix} a \\ b \\ c \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix} = \begin{bmatrix} b \\ a \\ c \end{bmatrix} .

The position of the 1's in P_3 mean that b is picked up first (only because the 1 is in the middle position in the top row), then a is picked up second (the 1 is in the first position of the second row) and then finally c is picked up third (the 1 is in the third position in the third row).

This insight of positioning simplifies the task of multiplication with permutation matrices. We'll see that this idea can be applied in other instances.

Examples

We could extend this idea by considering products of the permutation matrices amongst themselves.

For example, we notice that for any P_i for i=1 to 6, we have that P_1\times P_i=P_i, simply because P_1 is the identity matrix.

But what about other products? Products like P_2\times P_3 or P_4\times P_6.

For the product P_2\times P_3 we have:

\begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}

The multiplication is very easy once you understand what is happening. You may need to read the following logic a few times, but it is worth it, particularly when you have many products to calculate:

• We start in the usual way with the first row of P_2 and the first column of P_3. We then notice that the two zeros in the first row of P_2 eliminate whatever numbers are in the second and third positions of the first column of P_3. In other words the (1,1)–element of P_3 is being selected for the (1,1)–element in the product.

  

  1 selects 0 to place in the (1,1)–element in the product.

• Similarly, in row 2 of P_2, the 1 occurs at the end of the row. This means that the third element of column 1 of P_3 is being selected for the (2,1)–element of the product.

  

  1 selects 0 to place in the (2,1)–element in the product.

• Finally, in row 3 of P_2, the 1 occurs in the second position, and so the second row of column 1 of P_3 is being selected for the (3,1)–element of the product.

  

  1 selects 1 to place in the (3,1)–element in the product.

Multiplying the six permutation matrices by themselves means we can generate a table of 36 products. There is not the space to show all 36 products in the table, but there is one thing to realise before we start.

If all we are doing through multiplication is swapping the position of the rows, then every single product we generate must also be a permutation matrix. Look back and see, for example, that P_2\times P_3=P_4.

This means that the table of products is a table of permutation matrices.

Examples