Year 12 Discrete Mathematics: Permutation matrices

Permutation matrices are matrices that rearrange entries without changing the values themselves. They are a clean discrete-mathematics example of structure controlling action. A permutation matrix usually has exactly one $1$ in each row and each column, with zeros elsewhere. That pattern ensures that multiplication reorders coordinates rather than scaling or combining them arbitrarily. Once you see that, permutation matrices stop looking mysterious and start looking like organised shuffling devices.

A permutation matrix does not create new values. It repositions existing values by sending entries to new locations.

Subtopic 1: Recognising a permutation matrix

The most basic task is to decide whether a given matrix is a permutation matrix. The test is structural: each row and each column should contain exactly one $1$ and all other entries should be $0$ . If a row has two ones, or a column has none, or a non-zero value other than $1$ appears, the matrix is not a permutation matrix.

Worked example 1

Problem: Decide whether

P = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]

is a permutation matrix.

Row 1 has one $1$ .
Row 2 has one $1$ .
Row 3 has one $1$ .
Each column also has exactly one $1$ .

Answer: yes,

P

is a permutation matrix.

Subtopic 2: Applying a permutation matrix

Multiplying by a permutation matrix reorders the components of a vector or the rows or columns of a matrix, depending on how the multiplication is set up. The important point is that no new weighted combination is being created. The entries are being selected and relocated. This is why interpretation matters so much: you should be able to say which component goes where.

Worked example 2

Problem: Let

P = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]

and

v = [[4], [7], [9]]

. Find

P v

First component: $0 (4) + 1 (7) + 0 (9) = 7$ .
Second component: $0 (4) + 0 (7) + 1 (9) = 9$ .
Third component: $1 (4) + 0 (7) + 0 (9) = 4$ .

Answer:

P v = [[7], [9], [4]]

. The vector entries have been cycled.

Why this is a permutation

In the previous example, the numbers $4$ , $7$ , and $9$ all remain present. They are simply moved to new positions. That is the signature of a permutation matrix. This is different from general matrix multiplication, where entries are often blended together through weighted sums. Here the sparse structure of the matrix forces a clean reordering instead.

Worked example 3

Problem: Explain why

Q = [[1, 0, 0], [0, 1, 1], [0, 0, 1]]

is not a permutation matrix.

Row 2 contains two ones instead of exactly one.
Column 3 also contains two ones.
So the structure required for a pure reordering is broken.

Answer:

Q

is not a permutation matrix because it does not have exactly one

1

in each row and each column.

Common traps

Checking rows only and forgetting to check columns as well.
Assuming any zero-one matrix is a permutation matrix.
Multiplying correctly but failing to interpret which entry moved where.
Missing that left multiplication and right multiplication can reorder different parts of a matrix model.

Revision focus

A strong revision habit is to interpret the action before calculating the full product. Ask which old component will become the new first component, then the new second, and so on. If you can predict the rearrangement, the arithmetic becomes more of a confirmation than a guess.

It is also useful to compare permutation matrices with general transition matrices. One redistributes by exact relocation, the other can split or combine quantities. Seeing that contrast makes the purpose of the special one-one structure much clearer.