Search topics

Search

Construct, apply and invert a permutation matrix

Start a set of 8
1 OF 6
Reload matrix P
\(\displaystyle \begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\)
Stock counts S (slots 1, 2, 3)
\(\displaystyle \begin{bmatrix}14\\6\\9\end{bmatrix}\)

A vending rack has three slots with stock counts S, and the rack is reloaded in the order given by the reload matrix P. What is the column PS after the reload?

Year 12, VCE Units 3 & 4, Chapter 10, 4 difficulty levels, No calculatorBuild a worksheet

Use a permutation matrix

A permutation matrix is square and binary, with one 1 in each row and each column. Multiplying by it rearranges positions, while the values themselves stay the same

\[P^{-1}=P^{T}\]
  1. Use binary entries Every entry of a permutation matrix is either 0 or 1 \(\displaystyle p_{ij}\in\{0,1\}\)
  2. Place one 1 in each row and column Each row and each column must contain exactly one 1 \(\displaystyle \sum_j p_{ij}=1,\quad \sum_i p_{ij}=1\)
  3. Track positions in a column vector For a column vector, each output position takes one input value selected by its row \(\displaystyle \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}\)
  4. Use the transpose for the inverse The inverse permutation matrix is found by transposing the matrix \(\displaystyle P^{-1}=P^{T}\)

Worked example

The value in position 1 moves to position 3, the value in position 2 moves to position 1 and the value in position 3 moves to position 2. Construct P and find the following product

\[P\begin{bmatrix}6\\1\\9\end{bmatrix}\]
  1. \(\displaystyle P=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\)The first output takes input position 2, the second takes input position 3 and the third takes input position 1
  2. \(\displaystyle 0\times6+1\times1+0\times9=1\)The first output position receives the value from input position 2
  3. \(\displaystyle 0\times6+0\times1+1\times9=9\)The second output position receives the value from input position 3
  4. \(\displaystyle 1\times6+0\times1+0\times9=6,\quad P\begin{bmatrix}6\\1\\9\end{bmatrix}=\begin{bmatrix}1\\9\\6\end{bmatrix}\)The third output position receives the value from input position 1, so the entries are rearranged to 1, 9, 6

Common mistakes

Changing values instead of positions
✕\(\displaystyle P=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix},\quad P\begin{bmatrix}4\\7\\2\end{bmatrix}=\begin{bmatrix}8\\14\\4\end{bmatrix}\)✓\(\displaystyle P\begin{bmatrix}4\\7\\2\end{bmatrix}=\begin{bmatrix}7\\2\\4\end{bmatrix}\)
A permutation matrix rearranges positions only, so it does not multiply or otherwise change the vector entries
Checking only the rows
✕\(\displaystyle P=\begin{bmatrix}1&0&0\\1&0&0\\0&0&1\end{bmatrix}\)✓\(\displaystyle P=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}\)
A valid permutation matrix has exactly one 1 in every row and every column, not just every row
Assuming the inverse is the same matrix
✕\(\displaystyle P=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix},\quad P^{-1}=P\)✓\(\displaystyle P^{-1}=P^{T}\)
The inverse of a permutation matrix is its transpose; it is the same matrix only for a self-inverse permutation

Difficulty levels

introIdentify or apply a simple permutation matrix such as a two-position swap
standardConstruct a permutation matrix from a stated rearrangement of positions
challengeFind an inverse or apply a repeated permutation using matrix powers
examChoose the valid matrix, vector result, inverse or order from diagnostic alternatives

Questions about this topic

What makes a matrix a permutation matrix?+

It is a square binary matrix with exactly one 1 in each row and exactly one 1 in each column

What happens to a vector when a permutation matrix is applied?+

Its entries are rearranged into new positions. The values and their multiplicities do not change

How is the inverse permutation matrix found?+

Transpose the permutation matrix. Thus P inverse is P transpose

Can I use a calculator?+

No. This topic is practised without a calculator

Which year level and chapter is this?+

Year 12, VCE Units 3 & 4, General Mathematics, chapter 10: Matrices

In this chapter

State the order of a matrix and locate its elementsIdentify row, column, square, symmetric and zero matricesRead information from a labelled data matrixRead, transpose and classify a matrixConstruct a matrix from labelled information or an entry rule10A Matrix notation, types and construction: Solve a matrix equation10A Matrix notation, types and construction: Construct, apply and invert a permutation matrixAdd and subtract matricesFind unknown entries in a matrix equationMultiply a matrix by a scalarCombine scalar multiples of matrices10B Linear operations on matrices: Determine whether an inverse exists and calculate itDecide whether a matrix product is defined and give its orderMultiply matricesEvaluate powers of a square matrixIdentify and construct the identity matrix10C Matrix products, powers and permutations: Construct, apply and invert a permutation matrixFind the determinant of a 2 × 2 matrixFind the inverse of a 2 × 2 matrixWrite simultaneous equations as a matrix equationSolve simultaneous equations using the inverse matrix10D Determinants, inverses and matrix equations: Determine whether an inverse exists and calculate it10D Determinants, inverses and matrix equations: Solve a matrix equationUse matrix multiplication to answer an application questionUse row and column matrices of ones to extract totalsRepresent a network in a matrixIdentify the network a connection matrix describesInterpret connection sums and symmetryCount routes using powers of a connection matrixConstruct and analyse relation matrices