Matrices and Markov Chains

A matrix is a rectangle of numbers in rows and columns. Multiplying a matrix by a column of numbers gives a new column, so a matrix is a rule that turns one list into another, and a product of two matrices applies one rule after the other.

How are matrices described and added?

The order of a matrix is its number of rows, then its number of columns: 2 rows and 3 columns is a 2 × 3. An entry is named by its row, then its column.

Add or subtract two matrices entry by entry, so they must have the same order. To multiply a matrix by a number, multiply every entry by that number. See The order of a matrix and Adding, subtracting and scaling matrices.

How does matrix multiplication work, and why is AB not BA?

To multiply two matrices, pair a row of the left matrix with a column of the right: multiply matching entries and add the products. That sum is one entry of the product, and row 1 with column 1 fills row 1, column 1.

A row of A must be as long as a column of B, so AB exists only when A has as many columns as B has rows. A 2 × 3 times a 3 × 2 is a 2 × 2: the outer numbers give the order of the answer.

The rule is built this way because it totals a bill: a row of quantities times a column of prices is one shop's takings.

Order matters. AB and BA are usually different matrices, and they can even have different orders: a 2 × 3 times a 3 × 2 is 2 × 2, but the product the other way round is 3 × 3. Matrix multiplication is not commutative.

The identity matrix I has ones down the main diagonal and zeros everywhere else, and multiplying by I changes nothing, just as multiplying a number by 1 does. The inverse of A is the matrix that multiplies with A to give I. A pattern in the powers of A is proved by induction: check the formula at n = 1, then multiply the assumed matrix by A once more. See The matrix product, Combining data with a matrix product, Why AB differs from BA, The identity and zero matrices and Matrix powers by induction.

What does a determinant measure?

For the 2 × 2 matrix (a b; c d), the determinant is ad − bc: the product down the main diagonal minus the product along the other diagonal. For (4 2; 5 3) it is 12 − 10 = 2.

The determinant is the factor by which the matrix scales area, and a negative determinant also reflects. A determinant of 0 squashes the plane onto a line, so different points land on the same point and nothing can send them back apart. A matrix with determinant 0 has no inverse.

When the determinant is not 0, the inverse of (a b; c d) takes three moves: swap a and d, change the signs of b and c, then divide every entry by ad − bc. Check by multiplying: the product is I.

The inverse solves simultaneous equations in one step. Write the pair as A X = b, with the coefficients in A, the unknowns in the column X and the constants in b, then multiply both sides on the left by $A^{-1}$A⁻¹ to leave X on its own.

A 3 × 3 determinant expands along a row: each entry of row 1 multiplies the 2 × 2 determinant left when its row and column are deleted, with the signs +, −, +. It measures volume, and it is 0 exactly when there is no inverse. The 3 × 3 inverse is the transposed matrix of cofactors divided by the determinant, and it solves three equations in one step. See The determinant of a 2 × 2 matrix, The inverse of a 2 × 2 matrix, Solving simultaneous equations with a matrix inverse, The determinant of a 3 × 3 matrix, The inverse of a 3 × 3 matrix and Solving three equations with a matrix inverse.

What are eigenvalues and eigenvectors?

Most columns change direction when multiplied by A = (4 −1; 2 1), but (1, 1) comes back as (3, 3): the same direction, stretched by 3. A column that A only stretches is an eigenvector, and the factor is its eigenvalue: $Av=\lambda v$A v = λ v. Any multiple of an eigenvector is another, so an eigenvector names a direction. A negative eigenvalue reverses it, and 0 collapses it.

To find the eigenvalues, rewrite $Av=\lambda v$A v = λ v as $\left(A-\lambda I\right)v=0$(A − λI) v = 0. A non-zero column sent to zero means $A-\lambda I$A − λI has no inverse, so $\det \left(A-\lambda I\right)=0$det(A − λI) = 0. Subtracting $\lambda I$λI takes $\lambda$λ off each diagonal entry, so here $\det \left(A-\lambda I\right)=\left(4-\lambda \right)\left(1-\lambda \right)+2={\lambda }^2-5\lambda +6$det(A − λI) = (4 − λ)(1 − λ) + 2 = λ² − 5λ + 6, the characteristic polynomial. Its roots, 2 and 3, are the eigenvalues.

For each eigenvalue, solve $\left(A-\lambda I\right)v=0$(A − λI) v = 0. At $\lambda =3$λ = 3 both rows give y = x, so v = (1, 1); at $\lambda =2$λ = 2 they give y = 2x, so v = (1, 2).

Put the eigenvectors as the columns of P and the eigenvalues, in the same order, on the diagonal of D. Then A P = P D, so $A=PD{P}^{-1}$A = P D P⁻¹. Powers follow, because every inner $P^{-1}P$P⁻¹ P cancels: $A^n=P{D}^n{P}^{-1}$Aⁿ = P Dⁿ P⁻¹, and $D^n$Dⁿ is found entry by entry. See Eigenvalues and eigenvectors, The characteristic polynomial, Finding an eigenvector, Diagonalizing a 2 × 2 matrix and Matrix powers by diagonalization.

What is a Markov chain, and why does it settle down?

A Markov chain moves between a fixed set of states, and each move depends only on the current state, not on the history. Suppose each year 0.2 of a city's people move to the country and 0.3 of the country's people move to the city. Those shares fill a transition matrix T. Each column is one starting state, so its entries add to 1.

Multiply T by this year's split and next year's split comes out. After n years the split is $T^n$Tⁿ times the start, and diagonalizing T makes $T^n$Tⁿ easy to find.

A transition diagram shows the same numbers as arrows between the states, with a loop for the share that stays. A chain is regular when some power of T has every entry positive. A state whose only arrow loops back to itself traps everyone who enters it, so that chain is not regular.

Start everyone in the city and the split settles. A settled split is one that T leaves unchanged, so it is an eigenvector of T with eigenvalue 1. Solve (T − I) s = 0: both rows give 2x = 3y, so the long-run split is 3 city to 2 country.

Every transition matrix has eigenvalue 1, because its columns add to 1. The other eigenvalues are smaller than 1 in size, so their share of any start shrinks with each step, and the eigenvector for 1 is what remains. PageRank is this vector for the matrix of links between web pages. See Transition matrices, Transition diagrams and The long-run steady state.

Where this leads

Matrix arithmetic says what a matrix does to a column, the determinant says whether that can be undone, and eigenvalues say what happens when the matrix is applied many times. A Markov chain is that last question asked about a matrix of probabilities.

The mistakes worth naming

• Multiplying entry by entry. The matrix product pairs each row of the left matrix with each column of the right.
• Assuming AB = BA. Work out both.
• Cancelling a matrix. AB = AC gives B = C only when A has an inverse.
• Treating a zero determinant as a small answer. It means the matrix has no inverse.

Learn this properly in the app

Every lesson linked above is illustrated in Math Challenge, with worked examples and practice questions. Matrices acting on shapes continue in congruence, circle theorems and transformations, and the characteristic polynomial uses the factoring from quadratics and polynomials.