Skip to main content

Steady states and Perron-Frobenius

When does a Markov chain have exactly one steady state, and reach it from every start? State the Perron-Frobenius theorem, see the second-largest eigenvalue set the speed, and work the two ways it fails: separate pieces and a chain that flips for ever.
M03.9.2L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: M03.9.1 Markov matrices M03.2.4 The power method

What you will be able to do
  • State the Perron-Frobenius theorem for a positive, and for an irreducible and aperiodic, Markov matrix.
  • Explain from the eigen-expansion why the distance to the steady state shrinks like the second-largest eigenvalue modulus to the power t.
  • Diagnose the two failures: separate pieces (eigenvalue 1 repeated) and a periodic flip (eigenvalue -1).
  • Find a steady state both by iterating with a stopping rule and by solving (P-transpose - I) pi = 0 with the entries adding to 1.

The question

A sampler in Bayesian machine learning wanders between states so that, in the long run, it visits each one in proportion to a target probability. PageRank needs one ranking, not one per starting page. Both rely on the same promise: the chain has exactly one steady state and reaches it from every start. When can that promise be kept, and how fast?

From the last lesson

1. How does a distribution move one step forward under a row-stochastic matrix \(\mat{P}\)?

Show answer

\(\vect{\pi}_{t+1} = \mat{P}\T\vect{\pi}_t\).

2. Why can no eigenvalue of a Markov matrix exceed 1 in size?

Show answer

Each entry of \(\mat{P}\vect{v}\) is a weighted average of the entries of \(\vect{v}\), so for an eigenvector, \(\abs{\lambda}\,\max_i\abs{v_i} \le \max_i\abs{v_i}\). Equivalently, the max-norm of \(\mat{P}\) is 1.

Intuition

Take a chain on three states in which every move has a positive chance. Start it in state 1, or in state 2, or in state 3. Every distribution on three states is a point of a triangle, with “surely in state \(k\)” at corner \(k\), so each run of the chain is a path in the triangle.

Two panels. Left, titled A positive chain: a 3 by 3 matrix with rows 0.3, 0.2, 0.5; 0.2, 0.6, 0.2; and 0.1, 0.2, 0.7, labelled from 1, from 2 and from 3, with the note every entry greater than 0. Right, titled Three starts, one destination: a grey triangle with blue corners labelled all in 1, all in 2 and all in 3. From each corner a green path of dots runs into the triangle, and all three paths end at a black star labelled pi equals (1/6, 1/3, 1/2).
M03.9.2-F1

The positive chain \(\mat{Q}\) from three different starts. Wherever it starts, the chain ends at the same point of the triangle: the steady state \((1/6, 1/3, 1/2)\).

All three paths end at one point. Because every state can reach every other in one step, the chain mixes its starting information away. The Perron-Frobenius theorem turns that picture into a guarantee, and the second eigenvalue says how fast the forgetting happens.

Build it up

Step 1. Write the start in eigenvectors. Suppose \(\mat{P}\T\) has eigenvalues \(1, \lambda_2, \dots, \lambda_n\) with eigenvectors \(\vect{\pi}, \vect{v}_2, \dots, \vect{v}_n\), and write \(\vect{\pi}_0 = {\vect{\pi} + c_2\vect{v}_2 + \dots + c_n\vect{v}_n}\). As in M03.2.2, each step multiplies each part by its eigenvalue:

\[ \begin{aligned} \vect{\pi}_t &= \vect{\pi} + c_2\lambda_2^t\vect{v}_2 \\ &\quad + \dots + c_n\lambda_n^t\vect{v}_n . \end{aligned} \]

Step 2. The other parts carry no probability. If \(\mat{P}\T\vect{v} = \lambda\vect{v}\) with \(\lambda \ne 1\), then the entries of \(\vect{v}\) add up to 0. Proof: using \(\mat{P}\vect{1} = \vect{1}\),

\[ \begin{aligned} \lambda\,\vect{1}\T\vect{v} &= \vect{1}\T\mat{P}\T\vect{v} \\ &= (\mat{P}\vect{1})\T\vect{v} = \vect{1}\T\vect{v}, \end{aligned} \]

so \({(\lambda - 1)\,\vect{1}\T\vect{v}} = 0\), and \(\lambda \ne 1\) forces \(\vect{1}\T\vect{v} = 0\). Adding these parts moves probability between states without creating or destroying any.

Step 3. The slowest part sets the speed. If every \(\abs{\lambda_j} < 1\) for \(j \ge 2\), every extra part fades and \(\vect{\pi}_t \to \vect{\pi}\). The part that fades slowest belongs to the largest of the \(\abs{\lambda_j}\), the second-largest eigenvalue modulus. The distance to the steady state shrinks by about that factor every step.

A log-scale chart of the distance from pi t to the steady state, from 1 down to 0.00001, against the step t from 0 to 12. Three green lines with different hollow markers, one for each corner start, fall in parallel straight lines. A dashed orange line above them, with the same slope, is labelled slope of 0.4 to the t: the second eigenvalue.
M03.9.2-F2

For the positive chain \(\mat{Q}\), the distance to the steady state, summed over the three states, falls along a straight line on a log scale. Its slope is that of \(0.4^t\), and 0.4 is the second eigenvalue of \(\mat{Q}\).

The eigenvalues of \(\mat{Q}\) are 1, 0.4 and 0.2, so the second-largest modulus is 0.4. For the running chain of the last lesson it is also 0.4, and the formula there showed exactly this.

The formal statement

Two words describe the arrows of a chain. It is irreducible when every state can reach every other state along arrows. A state has period \(h\) when every return to it takes a multiple of \(h\) steps, with \(h\) as large as possible; the chain is aperiodic when every period is 1. A single self-loop makes its state aperiodic.

NoteTheorem: Perron-Frobenius, for Markov matrices

Let \(\mat{P}\) be a Markov matrix that is positive (every entry above 0), or more generally irreducible and aperiodic. Then

  1. the eigenvalue 1 is simple, and every other eigenvalue has \(\abs{\lambda} < 1\);
  2. there is exactly one stationary distribution \(\vect{\pi}\), and all its entries are positive;
  3. from every starting distribution, \(\vect{\pi}_t \to \vect{\pi}\), and the distance shrinks roughly like \(\abs{\lambda_2}^t\), where \(\abs{\lambda_2}\) is the second-largest modulus.

Irreducible and aperiodic together are the same as “some power \(\mat{P}^m\) is positive”, which is how Austin states the theorem.

Go deeper: a proof of parts 1 and 2 for a positive matrix

Every eigenvalue of size 1 is 1, with only constant eigenvectors. Let \(\mat{P}\vect{v} = \lambda\vect{v}\) with \(\abs{\lambda} = 1\), and pick \(i\) with \(\abs{v_i}\) largest. The proof of M03.9.1 gives \(\abs{v_i} = \abs{\sum_j p_{ij}v_j} \le \sum_j p_{ij}\abs{v_j} \le \abs{v_i}\), so both inequalities are equalities. The second forces \(\abs{v_j} = \abs{v_i}\) for every \(j\), since every \(p_{ij} > 0\). The first, the triangle inequality, is an equality only when all the \(v_j\) point the same way in the complex plane. So all the \(v_j\) are equal, \(\vect{v}\) is constant, and \(\lambda = 1\).

So the eigenspace of \(\mat{P}\) for 1 is the line of \(\vect{1}\), and since \(\mat{P} - \mat{I}\) and its transpose have the same rank, the eigenspace of \(\mat{P}\T\) for 1 is a line too.

The eigenvalue 1 is simple. If it were repeated with only one eigenvector, \(\mat{P}\) would have a block like the shear of M03.1.3: a vector \(\vect{w}\) with \({\mat{P}\vect{w} = \vect{w} + \vect{1}}\), so that \({\mat{P}^t\vect{w} = \vect{w} + t\,\vect{1}}\) grows like \(t\). But every power \(\mat{P}^t\) is a Markov matrix (exercise 3 of M03.9.1), so each entry of \(\mat{P}^t\vect{w}\) is a weighted average of the entries of \(\vect{w}\), and it cannot grow.

There is a steady state, and it is positive. Take a real \(\vect{u} \ne \vect{0}\) with \(\mat{P}\T\vect{u} = \vect{u}\), and let \(\abs{\vect{u}}\) hold the sizes of its entries. By the triangle inequality, entry \(j\) of \(\mat{P}\T\abs{\vect{u}}\) is \({\sum_i p_{ij}\abs{u_i}} \ge {\abs{\sum_i p_{ij}u_i}} = \abs{u_j}\). The two vectors also have the same total, because \({\vect{1}\T\mat{P}\T\abs{\vect{u}}} = {(\mat{P}\vect{1})\T\abs{\vect{u}}} = {\vect{1}\T\abs{\vect{u}}}\). A vector that is at least another entry by entry, with the same total, equals it, so \({\mat{P}\T\abs{\vect{u}} = \abs{\vect{u}}}\). Divided by its total, \(\abs{\vect{u}}\) is a stationary distribution \(\vect{\pi}\), the only one because the eigenspace is a line. Finally, each entry of \(\vect{\pi} = \mat{P}\T\vect{\pi}\) is \(\sum_i \pi_i p_{ij} > 0\), because some \(\pi_i > 0\) and every \(p_{ij} > 0\).

What goes wrong without the conditions. Two small chains show why each condition is there.

Separate pieces. Join the running chain on states 1 and 2 with a second chain on states 3 and 4 that stays put with probability 0.7, and add no arrow between them. The chain is not irreducible. Each piece has the eigenvalues 1 and 0.4, so the whole has 1 twice, and every mixture

\[ \begin{aligned} \vect{\pi} &= a\,\big(\tfrac56, \tfrac16, 0, 0\big) \\ &\quad + (1 - a)\,\big(0, 0, \tfrac12, \tfrac12\big) \end{aligned} \]

with \(0 \le a \le 1\) is stationary. Which one you reach depends on how much probability starts in each piece.

Two panels. Left, titled No arrow between the pieces: four states in a row. States 1 and 2 are joined by green arrows labelled 0.1 and 0.5, with loops 0.9 and 0.5; a dashed line separates them from states 3 and 4, joined by arrows labelled 0.3 and 0.3, with loops 0.7 and 0.7. Labels read piece A and piece B. Right, titled Two limits, by start: bars over states 1 to 4. Grey bars for a start in state 1 reach 5/6 and 1/6 on states 1 and 2 and nothing on 3 and 4. Sky-blue bars for a start in state 3 reach 1/2 on states 3 and 4 and nothing on 1 and 2.
M03.9.2-F3

A chain in two pieces has the eigenvalue 1 twice and a whole family of steady states. A start in state 1 never leaves piece A, and a start in state 3 never leaves piece B.

A flip. The chain that always swaps its two states has \(\mat{P} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\). It is irreducible, so it has exactly one steady state, \((1/2, 1/2)\). But every return takes an even number of steps: its period is 2. The eigenvalues are 1 and \(-1\), and from \((1, 0)\) the distribution alternates \((1, 0), (0, 1), (1, 0), \dots\). The \(-1\) part never fades; it only changes sign.

Two panels. Left, titled The flip: two states 1 and 2 joined by green arrows both labelled 1, with the note eigenvalues 1 and minus 1. Right, titled Chance of state 1, from pi 0 equals (1, 0): green dots zigzag between 1 and 0 at every step from 0 to 9, around a dashed line at 0.5, with the note the steady state 1/2 (dashed) is never reached.
M03.9.2-F4

The flip is irreducible but periodic. Its one steady state exists but is never reached: the eigenvalue \(-1\) makes the distribution swing for ever.

Worked example

Find the steady state of \(\mat{Q} = \begin{bmatrix} 0.3 & 0.2 & 0.5 \\ 0.2 & 0.6 & 0.2 \\ 0.1 & 0.2 & 0.7 \end{bmatrix}\) by hand, and estimate how many steps the chain needs.

The steady state solves \(\mat{Q}\T\vect{\pi} = \vect{\pi}\). Its rows are balance equations: the probability arriving at a state equals the probability that is there. For states 1 and 2, reading down the columns of \(\mat{Q}\):

\[ \begin{aligned} \pi_1 &= 0.3\pi_1 + 0.2\pi_2 + 0.1\pi_3, \\ \pi_2 &= 0.2\pi_1 + 0.6\pi_2 + 0.2\pi_3 . \end{aligned} \]

The third balance equation adds nothing new. Adding all three gives \({\pi_1 + \pi_2 + \pi_3}\) on both sides, because each row of \(\mat{Q}\) adds to 1, so any two of them imply the third.

Multiply the first by 10 and collect: \({7\pi_1 = 2\pi_2 + \pi_3}\). Multiply the second by 5 and collect: \({2\pi_2 = \pi_1 + \pi_3}\). Put the second into the first: \({7\pi_1 = \pi_1 + 2\pi_3}\), so \(\pi_3 = 3\pi_1\), and then \({2\pi_2 = 4\pi_1}\), so \(\pi_2 = 2\pi_1\). The entries add to 1, so \({\pi_1 + 2\pi_1 + 3\pi_1} = 1\) and

\[ \vect{\pi} = \big(\tfrac16,\; \tfrac13,\; \tfrac12\big). \]

A worked-example trace of six boxes in three rows. Top row, blue: pi 1 equals 0.3 pi 1 plus 0.2 pi 2 plus 0.1 pi 3, and pi 2 equals 0.2 pi 1 plus 0.6 pi 2 plus 0.2 pi 3, under the heading Two balance equations (the third repeats them). Green arrows labelled times 10, collect and times 5, collect lead to the middle row, green: 7 pi 1 equals 2 pi 2 plus pi 3, and 2 pi 2 equals pi 1 plus pi 3. An arrow labelled put 2 pi 2 into the left equation leads to the bottom row, vermillion: pi 3 equals 3 pi 1 and pi 2 equals 2 pi 1, and 6 pi 1 equals 1. The last line reads so pi equals (1/6, 1/3, 1/2), using pi 1 plus pi 2 plus pi 3 equals 1.
M03.9.2-F5

The steady state by elimination. Two balance equations fix the ratios \(1 : 2 : 3\), and the condition that the chances add to 1 fixes the scale.

Check. The first balance equation gives \({0.3/6 + 0.2/3 + 0.1/2} = {0.05 + 0.0667 + 0.05} = 0.1667 = 1/6\).

How fast. \(\mat{Q}\T\) has trace \({0.3 + 0.6 + 0.7} = 1.6\), and its eigenvalues are 1, 0.4 and 0.2, which do add to 1.6. The second-largest modulus is 0.4, so each step cuts the distance by about 0.4. Since \(0.4^{15} \approx 1.1 \times 10^{-6}\), about fifteen steps buy six decimal places.

Code

The power method of M03.2.4, specialised: no rescaling is needed, because a distribution keeps its total of 1. Stop when one step changes the distribution by less than a tolerance.

import numpy as np

Q = np.array([[0.3, 0.2, 0.5],
              [0.2, 0.6, 0.2],
              [0.1, 0.2, 0.7]])

def steady_by_iteration(P, pi0, tol=1e-10, max_steps=10_000):
    """Apply P-transpose until the distribution moves less than tol (summed over states)."""
    pi = np.asarray(pi0, dtype=float)
    for step in range(1, max_steps + 1):
        new = P.T @ pi
        if np.abs(new - pi).sum() < tol:
            return new, step
        pi = new
    raise RuntimeError("no convergence: is the chain periodic or in pieces?")

pi_iter, steps = steady_by_iteration(Q, [1.0, 0.0, 0.0])
print("by iteration:", pi_iter, " steps:", steps)
by iteration: [0.16666667 0.33333333 0.5       ]  steps: 26

The direct route solves \((\mat{P}\T - \mat{I})\vect{\pi} = \vect{0}\) together with \(\vect{1}\T\vect{\pi} = 1\). That is \(n + 1\) equations in \(n\) unknowns, one of them redundant, so stack them and let least squares (M03.7) solve the consistent system exactly.

def steady_by_solving(P):
    n = len(P)
    A = np.vstack([P.T - np.eye(n), np.ones(n)])   # balance equations, then "add to 1"
    b = np.concatenate([np.zeros(n), [1.0]])
    pi, *_ = np.linalg.lstsq(A, b, rcond=None)
    return pi

print("by solving:  ", steady_by_solving(Q))

flip = np.array([[0.0, 1.0], [1.0, 0.0]])
print("flip, solved:", steady_by_solving(flip))
try:
    steady_by_iteration(flip, [1.0, 0.0], max_steps=500)
except RuntimeError as err:
    print("flip, iterated:", err)
by solving:   [0.16666667 0.33333333 0.5       ]
flip, solved: [0.5 0.5]
flip, iterated: no convergence: is the chain periodic or in pieces?

Solving answers \((1/2, 1/2)\) for the flip, which is indeed its steady state, while iteration refuses to settle. For the chain in two pieces the stacked system is one equation short (rank 3 for 4 unknowns), and least squares quietly returns just one member of the family. Iterating tells you whether the steady state is reached; solving tells you what it is, if it is unique.

Explore

The random surfer in lesson M03.9.4 lets you break the conditions of this lesson on purpose. Set the damping factor to 1 and switch off the link from page 1 to page 2: what is left is a two-page flip between pages 1 and 3, and the read-out shows a second eigenvalue of size 1.

Pitfalls

Two panels of the chance of state 1 against the step t from 0 to 12, each with a dashed line at 0.5. Left, marked with a cross and titled Flip: always move: the green dots zigzag between 1 and 0 for ever, with the note eigenvalue minus 1: flips for ever. Right, marked with a tick and titled Lazy flip: stay with 0.2: the dots swing from 1 to 0.2 to 0.68 and so on with shrinking swings that settle at 0.5, with the note eigenvalue minus 0.6: settles at 1/2.
M03.9.2-F6

Wrong beside right. Letting the chain stay put with probability 0.2 turns the eigenvalue \(-1\) into \(-0.6\), and the swings now shrink by 0.6 each step.

“A steady state exists, so the chain gets there.”

Every Markov matrix has a steady state, but the flip shows that having one is not reaching it. Convergence needs every eigenvalue other than 1 inside the unit circle, which is what aperiodicity buys. Samplers and PageRank add a little “laziness” or “teleporting” for exactly this reason.

“The speed is set by the second-largest eigenvalue.”

By its modulus. The lazy flip has eigenvalues 1 and \(-0.6\); the relevant number is \(0.6\), not \(-0.6\), and a complex pair counts by its modulus too. An eigenvalue of size 0.999 is legal and harmless for uniqueness but makes the chain need thousands of steps: a slowly mixing sampler.

“Perron-Frobenius needs every entry of \(\mat{P}\) to be positive.”

Positive is enough, not necessary. The chain with rows \((0.5, 0.5, 0)\), \((0.25, 0.5, 0.25)\) and \((0, 0.5, 0.5)\) has zeros, yet it is irreducible and has self-loops, and its square is positive. The theorem holds for it (exercise 1).

Check yourself

Recall

1. State the conclusion of the Perron-Frobenius theorem for a positive Markov matrix.

Show answer

The eigenvalue 1 is simple and every other eigenvalue has modulus below 1; there is exactly one stationary distribution, with positive entries; and every start converges to it.

2. What sets the speed of convergence to the steady state?

Show answer

The second-largest eigenvalue modulus \(\abs{\lambda_2}\): the distance shrinks roughly like \(\abs{\lambda_2}^t\).

3. Why do the eigenvectors of \(\mat{P}\T\) for eigenvalues other than 1 have entries adding to 0?

Show answer

From \(\lambda\,\vect{1}\T\vect{v} = \vect{1}\T\mat{P}\T\vect{v} = (\mat{P}\vect{1})\T\vect{v} = \vect{1}\T\vect{v}\), so \((\lambda - 1)\vect{1}\T\vect{v} = 0\), and \(\lambda \ne 1\).

4. What goes wrong for a chain in two separate pieces?

Show answer

The eigenvalue 1 is repeated, every mixture of the pieces’ steady states is stationary, and the limit depends on the start.

5. What are the eigenvalues of the flip, and what does the distribution do?

Show answer

1 and \(-1\). From \((1, 0)\) the distribution alternates between \((1, 0)\) and \((0, 1)\) for ever and never reaches the steady state \((1/2, 1/2)\).

Exercises

1. ★ For the chain with rows \((0.5, 0.5, 0)\), \((0.25, 0.5, 0.25)\) and \((0, 0.5, 0.5)\), find the steady state by balance equations, and check that \(\mat{P}^2\) is positive.

Show solution

Balance at state 1: \({\pi_1 = 0.5\pi_1 + 0.25\pi_2}\), so \(\pi_2 = 2\pi_1\). Balance at state 3: \({\pi_3 = 0.25\pi_2 + 0.5\pi_3}\), so \(\pi_2 = 2\pi_3\). Hence \(\pi_3 = \pi_1\), and \({\pi_1 + 2\pi_1 + \pi_1} = 1\) gives \(\vect{\pi} = (1/4, 1/2, 1/4)\). The first row of \(\mat{P}^2\) is row 1 of \(\mat{P}\) times \(\mat{P}\), that is, half of row 1 plus half of row 2:

\[ \begin{aligned} &0.5\,(0.5, 0.5, 0) \\ &\quad + 0.5\,(0.25, 0.5, 0.25) \\ &\quad = (0.375,\; 0.5,\; 0.125). \end{aligned} \]

By the mirror symmetry the last row is \((0.125, 0.5, 0.375)\), and the middle row is

\[ \begin{aligned} &0.25\,(0.5, 0.5, 0) \\ &\quad + 0.5\,(0.25, 0.5, 0.25) \\ &\quad + 0.25\,(0, 0.5, 0.5) \\ &\quad = (0.25,\; 0.5,\; 0.25). \end{aligned} \]

Every entry is positive.

2. ★★ For the chain in two pieces, which steady state is reached from \(\vect{\pi}_0 = (0.5, 0, 0.5, 0)\)?

Show solution

No probability ever crosses between the pieces, so piece A keeps its total of 0.5 and piece B keeps 0.5. Within each piece the distribution settles at that piece’s steady state, scaled by its total. So the limit is

\[ \begin{aligned} &0.5\,\big(\tfrac56, \tfrac16, 0, 0\big) + 0.5\,\big(0, 0, \tfrac12, \tfrac12\big) \\ &\quad = \big(\tfrac{5}{12}, \tfrac{1}{12}, \tfrac14, \tfrac14\big), \end{aligned} \]

the member of the family with \(a = 0.5\).

3. ★★★ The lazy version of a Markov matrix is \(\mat{L} = \tfrac12(\mat{I} + \mat{P})\). Show that it is a Markov matrix with the same steady states as \(\mat{P}\), and that it has no eigenvalue of modulus 1 other than 1 itself.

Show solution

Its entries are non-negative and \({\mat{L}\vect{1} = \tfrac12(\vect{1} + \vect{1})} = \vect{1}\). Also \({\mat{L}\T\vect{\pi} = \tfrac12(\vect{\pi} + \mat{P}\T\vect{\pi})}\), which equals \(\vect{\pi}\) exactly when \(\mat{P}\T\vect{\pi} = \vect{\pi}\). Since \(\mat{L}\vect{v} = \tfrac12(\vect{v} + \mat{P}\vect{v})\), \(\mat{P}\vect{v} = \lambda\vect{v}\) holds exactly when \(\mat{L}\vect{v} = \tfrac12(1 + \lambda)\vect{v}\), so the eigenvalues of \(\mat{L}\) are the numbers \(\mu = (1 + \lambda)/2\). With \(\abs{\lambda} \le 1\), the triangle inequality gives \({\abs{1 + \lambda} \le 1 + \abs{\lambda} \le 2}\), so \(\abs{\mu} \le 1\). Equality needs \(\abs{\lambda} = 1\) and \(\lambda\) pointing the same way as 1, that is, \(\lambda = 1\). So \(\abs{\mu} = 1\) only for \(\mu = 1\); the flip’s \(-1\), for example, becomes 0.

Summary card

One steady state, reached from everywhere, when the chain is irreducible and aperiodic.

The anchor figure again: a positive 3 by 3 Markov matrix beside the triangle of distributions, with paths from all three corners ending at the same black star, the steady state (1/6, 1/3, 1/2).
M03.9.2-F1

Every start, one destination.

  • Expansion. \(\vect{\pi}_t = \vect{\pi} + \sum_{j \ge 2} c_j\lambda_j^t\vect{v}_j\), with \(\vect{1}\T\vect{v}_j = 0\).
  • Perron-Frobenius. Positive, or irreducible and aperiodic: 1 is simple, all other \(\abs{\lambda} < 1\).
  • Speed. Distance \(\approx C\,\abs{\lambda_2}^t\).
  • Failures. Pieces: 1 repeated. Period 2: eigenvalue \(-1\).
  • Solve. \((\mat{P}\T - \mat{I})\vect{\pi} = \vect{0}\) with \(\vect{1}\T\vect{\pi} = 1\).

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Dan Margalit and Joseph Rabinoff, Interactive Linear Algebra, section 5.6 Stochastic matrices (Georgia Tech). The Perron-Frobenius theorem for a positive stochastic matrix (a unique steady state spanning the 1-eigenspace, reached from any start), stated for column-stochastic matrices, the transpose of ours.
  • David Austin, Understanding Linear Algebra, section Markov chains and Google’s PageRank algorithm (open textbook). The Perron-Frobenius theorem with “positive” meaning that some power of the matrix has positive entries: 1 is an eigenvalue, all others have modulus below 1, and every chain converges to the unique positive steady state.
  • Wikipedia, Perron-Frobenius theorem, sections Positive matrices and Perron-Frobenius theorem for irreducible non-negative matrices: an irreducible matrix of period \(h\) has exactly \(h\) eigenvalues of maximal modulus, and primitive matrices are the irreducible aperiodic ones.
  • NumPy reference, numpy.linalg.lstsq: it minimises \(\norm{\vect{b} - \mat{A}\vect{x}}\) for under-, well- or over-determined systems, returning the solution, residuals, rank and singular values.

Next. M03.9.3 Graphs as matrices leaves probabilities behind for a moment and turns the arrows themselves into a matrix. Hitting times, recurrence and the probabilistic theory of chains are in M07.7, and samplers built on these guarantees are in M07.10.

This lesson unlocks

M03.9.3 Graphs as matrices M07.7 Markov chains (planned)

Your progress is saved in this browser only. No account, no tracking.
Back to top