Lesson 8 of 8 · 18 min

More applications of matrices

Investigate Markov chains, Leontief input–output models, Hill ciphers, areas from determinants, and the eigenvalues behind long-run behaviour.

What you will be able to do

  • Use a transition matrix to predict the next state of a Markov chain and find its long-run state.
  • Solve a Leontief input–output model X=(I−A)−1D\bm{X} = (\bm{I} - \bm{A})^{-1}\bm{D}.
  • Encode and decode a message with a matrix (Hill cipher).
  • Find the area of a triangle from a determinant, and recognise eigenvalues and eigenvectors.

Note

What the exam covers

The syllabus asks you to investigate these applications, so you will meet them in class and in assessment such as a problem-solving and modelling task. By the syllabus note, the external exam may assess only dominance and Leslie matrices.

Markov chains. Two cafés share a town's 1000 regular coffee drinkers. Each week, 80%80\% of café A's customers come back to A and 20%20\% switch to B; 70%70\% of B's customers stay and 30%30\% switch to A. Put the proportions in a transition matrix, with column jj for "from state jj":

T=[0.80.30.20.7]Sn+1=TSn\bm{T} = \begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix} \qquad \bm{S}_{n+1} = \bm{T}\bm{S}_n

Each column adds to 11, because everyone goes somewhere. Starting with 500500 at each café, S1=TS0=[550450]\bm{S}_1 = \bm{T}\bm{S}_0 = \begin{bmatrix} 550 \\ 450 \end{bmatrix}.

Interactive

The long run

Slide nn up. The state settles at 600600 customers for A and 400400 for B, whatever the starting split: this is the steady state, where TS=S\bm{TS} = \bm{S}.

With the same transition matrix, one week the cafés have 300300 (A) and 700700 (B) customers. How many go to café A the next week?

Leontief input–output models. Industries buy from one another. If producing $1 of manufacturing needs $0.20 of agriculture, then a12=0.2a_{12} = 0.2 in the technology matrix A\bm{A}. For total outputs X\bm{X} and external demand D\bm{D}, output must cover what the industries use plus what consumers buy:

X=AX+D⟹(I−A)X=D⟹X=(I−A)−1D\bm{X} = \bm{AX} + \bm{D} \quad \Longrightarrow \quad (\bm{I} - \bm{A})\bm{X} = \bm{D} \quad \Longrightarrow \quad \bm{X} = (\bm{I} - \bm{A})^{-1}\bm{D}

That is an AX+BX=C\bm{AX} + \bm{BX} = \bm{C} equation in disguise, solved with technology.

Worked example

Solve a Leontief input–output model

  • Complex familiar
  • Technology active

An economy has three sectors: agriculture, manufacturing and services. The technology matrix (dollars of each row sector's output used to make $1 of each column sector's output) and the external demand, in millions of dollars, are

A=[0.10.20.10.30.10.20.20.30.1],D=[430480350]\bm{A} = \begin{bmatrix} 0.1 & 0.2 & 0.1 \\ 0.3 & 0.1 & 0.2 \\ 0.2 & 0.3 & 0.1 \end{bmatrix}, \qquad \bm{D} = \begin{bmatrix} 430 \\ 480 \\ 350 \end{bmatrix}

Find the total output each sector must produce.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Write X=AX+D\bm{X} = \bm{AX} + \bm{D}.

  2. Rearrange to X=(I−A)−1D\bm{X} = (\bm{I} - \bm{A})^{-1}\bm{D}.

  3. Solve with technology and check one row.

Watch out for

  • Using (A−I)−1(\bm{A} - \bm{I})^{-1}, which gives negative outputs.

  • Solving AX=D\bm{AX} = \bm{D}: that ignores the external demand being on top of internal use.

Cryptology. The Hill cipher turns letters into numbers (A=1A = 1, B=2B = 2, …, Z=26Z = 26), groups them into columns, and multiplies by an encoding matrix E\bm{E}. Only someone who knows E−1\bm{E}^{-1} can recover the message. For example, with

E=[110121023],E[192113]=[407481]\bm{E} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 2 & 3 \end{bmatrix}, \qquad \bm{E}\begin{bmatrix} 19 \\ 21 \\ 13 \end{bmatrix} = \begin{bmatrix} 40 \\ 74 \\ 81 \end{bmatrix}

the word SUM is sent as 40,74,8140, 74, 81. Since det⁡(E)=1\det(\bm{E}) = 1, E−1=[4−31−33−12−21]\bm{E}^{-1} = \begin{bmatrix} 4 & -3 & 1 \\ -3 & 3 & -1 \\ 2 & -2 & 1 \end{bmatrix} has whole-number entries, and E−1[407481]\bm{E}^{-1}\begin{bmatrix} 40 \\ 74 \\ 81 \end{bmatrix} gives back 19,21,1319, 21, 13.

Using the same matrix E\bm{E}, encode the word CAT, which is [3120]\begin{bmatrix} 3 \\ 1 \\ 20 \end{bmatrix}.

History

The real Hill cipher

Lester Hill published the cipher in 1929. The real version works modulo 26, so every coded number is again a letter, and the encoding matrix needs an inverse modulo 26. Cracking it is a matter of linear algebra, which is why it is now a teaching example, not a secure code.

Area. In Unit 2 you saw that a 2×22 \times 2 matrix multiplies areas by ∣det⁡∣|\det|. A 3×33 \times 3 determinant gives the area of a triangle straight from its vertices (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2), (x3,y3)(x_3, y_3):

Area=12∣det⁡[x1y11x2y21x3y31]∣\text{Area} = \frac{1}{2}\left|\det\begin{bmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{bmatrix}\right|

If the determinant is 00, the three points are collinear.

The triangle with vertices (2,1)(2, 1), (6,2)(6, 2) and (3,5)(3, 5).

Use the determinant formula to find the area of the triangle with vertices (2,1)(2, 1), (6,2)(6, 2) and (3,5)(3, 5), in square units.

Eigenvalues and eigenvectors

Some vectors are only stretched by a matrix, not turned: Av=λv\bm{Av} = \lambda\bm{v}. Such a v\bm{v} (not zero) is an eigenvector of A\bm{A} and the number λ\lambda is its eigenvalue. They are found from det⁡(A−λI)=0\det(\bm{A} - \lambda\bm{I}) = 0.

They explain the long-run behaviour you have seen. The café steady state is an eigenvector with λ=1\lambda = 1: [0.80.30.20.7][0.60.4]=[0.60.4]\begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}\begin{bmatrix} 0.6 \\ 0.4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.4 \end{bmatrix}. A Leslie matrix's long-term growth ratio is its largest eigenvalue, and the stable age distribution is the matching eigenvector.

Summary

  • Markov chain: Sn+1=TSn\bm{S}_{n+1} = \bm{TS}_n with each column of T\bm{T} adding to 11; the steady state satisfies TS=S\bm{TS} = \bm{S}.

  • Leontief model: X=AX+D\bm{X} = \bm{AX} + \bm{D}, so X=(I−A)−1D\bm{X} = (\bm{I} - \bm{A})^{-1}\bm{D}.

  • Hill cipher: encode with E\bm{E}, decode with E−1\bm{E}^{-1}; det⁡(E)=±1\det(\bm{E}) = \pm 1 keeps the numbers whole.

  • The area of a triangle is half the absolute value of a 3×33 \times 3 determinant of its vertices.

  • Eigenvectors satisfy Av=λv\bm{Av} = \lambda\bm{v}; they describe long-run states in Markov and Leslie models.

  • These applications are for investigation; the external exam may assess only dominance and Leslie matrices.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 8 of 80% read

Save your progress with a free account