Source: Friedberg, Insel, Spence – Linear Algebra, 4th Ed.
Tags: matrix limit, Markov chain, transition matrix, stochastic matrix, probability vector, regular transition matrix, fixed probability vector, stationary vector, Gerschgorin disk theorem, absorbing Markov chain
Difficulty: Intermediate to Advanced | Prerequisites: Sections 5.1 and 5.2 (eigenvalues, eigenvectors, diagonalizability), basic probability, limits of sequences.
This section applies the diagonalization machinery of Sections 5.1 and 5.2 to a natural question: when does the sequence A, A^2, A^3, ... converge to a limit matrix L? The answer involves eigenvalues: convergence happens when every eigenvalue is either inside the unit disk or equal to 1 (with an additional dimension condition on the eigenspace for eigenvalue 1). The major application is Markov chains, where transition matrices model probabilistic state changes over time. If you are comfortable with diagonalization and computing A^n = QD^nQ^{-1}, you are ready.
The limit of A^m (as m goes to infinity) exists when all eigenvalues satisfy |λ| < 1 or λ = 1, and the eigenvalue 1 behaves well (eigenspace dimension equals its multiplicity). For regular transition matrices (some power has all positive entries), the limit always exists, has identical columns, and each column is the unique fixed probability vector.
Matrix limit (lim A^m)
The sequence A^1, A^2, A^3, ... converges to L if every entry (A^m){ij} converges to L{ij} as m approaches infinity.
Think of it as: apply the transformation A repeatedly, and watch whether the results settle down to a fixed outcome.
Transition matrix (stochastic matrix)
A square matrix with nonnegative entries where each column sums to 1. Entry M_{ij} represents the probability of moving from state j to state i in one step.
In simple terms, each column is a probability distribution over where you might end up next, given your current state.
Probability vector
A column vector with nonnegative entries that sum to 1.
Think of it as: a snapshot of how likely you are to be in each possible state at a given moment.
Markov chain
A stochastic process with finitely many states, where the probability of transitioning from one state to another depends only on the current state (not on history or time).
In simple terms, it is a "memoryless" random process. Where you go next depends only on where you are now.
Regular transition matrix
A transition matrix A such that some power A^s has only positive entries (no zeros anywhere).
Think of it as: after enough steps, there is a nonzero probability of getting from any state to any other state. No state is permanently isolated.
Fixed probability vector (stationary vector)
The unique probability vector v satisfying Av = v for a regular transition matrix A. It is an eigenvector for eigenvalue 1 that is also a probability vector.
In simple terms, once the system reaches this distribution, it stays there forever. It is the long-run equilibrium.
Gerschgorin disk
For an n × n matrix A, the ith Gerschgorin disk C_i is the disk in the complex plane centred at A_{ii} with radius r_i = sum of |A_{ij}| for j ≠ i. Every eigenvalue of A lies in at least one of these disks.
Think of it as: a quick, computation-free way to bound where eigenvalues can be. Very useful for transition matrices.
Absorbing state / absorbing Markov chain
An absorbing state is one that, once entered, is never left (the probability of staying is 1). A Markov chain is absorbing if it is possible to reach an absorbing state from any non-absorbing state in finitely many steps.
The limit exists if and only if:
(a) Every eigenvalue of A lies in S = {λ ∈ C : |λ| < 1 or λ = 1}.
(b) If 1 is an eigenvalue, then dim(E_1) equals the algebraic multiplicity of 1.
Condition (a) is intuitive: λ^m converges only if |λ| < 1 (converges to 0) or λ = 1 (stays at 1). Condition (b) rules out defective eigenspaces at λ = 1, which cause polynomial growth (e.g., [[1,1],[0,1]]^m = [[1,m],[0,1]] diverges).
If A is diagonalizable and all eigenvalues lie in S, then lim A^m exists. Procedure:
Diagonalise: Q^{-1}AQ = D = diag(λ_1, ..., λ_n).
Compute lim D^m: each diagonal entry λ_i^m goes to 1 (if λ_i = 1) or 0 (if |λ_i| < 1).
Result: lim A^m = Q · (lim D^m) · Q^{-1}.
If lim A_m = L, then lim(PA_m) = PL and lim(A_mQ) = LQ for any conformable matrices P, Q.
Corollary: lim(QAQ^{-1})^m = Q(lim A^m)Q^{-1}. This is why diagonalization works for limits.
Columns of a transition matrix are probability vectors.
The product of a transition matrix and a probability vector is a probability vector. (The system stays normalised.)
The product of two transition matrices is a transition matrix. (Composing transitions gives a transition.)
Characterisation (Theorem 5.15): M is a transition matrix ⇔ M^t u = u, where u = (1, 1, ..., 1)^T. And v is a probability vector ⇔ u^t v = (1).
Given transition matrix A and initial probability vector P:
A^m P gives the probability distribution after m steps.
(A^m)_{ij} = probability of moving from state j to state i in m steps.
lim A^m P (if it exists) gives the long-run distribution.
Since A^t u = u (where u is the all-ones vector), u is an eigenvector of A^t with eigenvalue 1. Because A and A^t share eigenvalues, 1 is an eigenvalue of A.
Every eigenvalue of A lies in some Gerschgorin disk. From this:
Corollary 1: |λ| ≤ ρ(A), the maximum row sum.
Corollary 2: |λ| ≤ min{ρ(A), ν(A)}, where ν(A) is the maximum column sum.
Corollary 3: For a transition matrix, |λ| ≤ 1 (since each column sums to 1).
For a regular transition matrix A:
All eigenvalues satisfy |λ| ≤ 1.
If |λ| = 1, then λ = 1 and dim(E_1) = 1. (All other eigenvalues are strictly inside the unit circle.)
The algebraic multiplicity of 1 is also 1.
lim A^m always exists (no diagonalizability assumption needed).
L = lim A^m is itself a transition matrix.
AL = LA = L.
Every column of L is the same vector v, the fixed probability vector.
For any initial probability vector w, lim A^m w = v. The long-run outcome is independent of where you start.
For a regular transition matrix A, find the fixed probability vector by:
Solve (A - I)v = 0 to find the eigenspace for λ = 1.
The solution space is one-dimensional. Take any nonzero solution.
Scale it so its entries sum to 1. That is the fixed probability vector.
A transition matrix of the form [[I, B],[O, C]] has absorbing states (corresponding to I). These matrices are never regular (the absorbing columns remain fixed). The limit can still be computed via diagonalization. Example: the community college enrollment model, where "graduated" and "quit" are absorbing states.
In a population with unrestricted mating and gene types G and g with proportions a and b (where a + b = 1), the genotype distribution reaches equilibrium after just one generation. The equilibrium distribution is (a^2, 2ab, b^2) for genotypes GG, Gg, gg. This is a direct consequence of the Markov chain analysis.
Limit of powers (diagonalizable case): lim A^m = Q · diag(lim λ_1^m, ..., lim λ_n^m) · Q^{-1}
where lim λ_i^m = 1 if λ_i = 1, and 0 if |λ_i| < 1.
Gerschgorin disk centre and radius: Centre: A_{ii}, Radius: r_i = Σ_{j≠i} |A_{ij}|
Fixed probability vector equation: Av = v, with v a probability vector (entries ≥ 0, sum to 1).
Transition matrix characterisation: M is a transition matrix ⇔ M has nonneg entries and M^t u = u.
Markov chains model weather forecasting (sunny/rainy transitions), queueing systems (customer arrivals and service), financial models (credit rating migration), genetics (allele frequency changes across generations), and web page ranking (the original PageRank algorithm). The fixed probability vector gives the long-run steady state of any system modelled as a regular Markov chain.
"Every transition matrix has a convergent power sequence." False. If A has eigenvalue -1 (e.g. the swap matrix [[0,1],[1,0]]), then A^m oscillates and does not converge. You need every eigenvalue in S.
"The initial probability vector affects the long-run distribution for a regular Markov chain." It does not. Theorem 5.20(f) states that for any starting vector w, lim A^m w is the same fixed probability vector v. The starting point is "forgotten."
"A transition matrix with zero entries is never regular." A transition matrix with some zero entries can still be regular if some power A^s has all positive entries (see the example in the text with M^2 being all positive).
"Gerschgorin disks give the exact eigenvalues." They do not. Gerschgorin disks give regions where eigenvalues must lie. The actual eigenvalues could be anywhere inside those regions.
⚠️ The conditions for lim A^m to exist (Theorem 5.13: eigenvalues in S, eigenspace dimension condition) are frequently tested. Be ready to check both.
⚠️ Computing the fixed probability vector for a regular transition matrix is a standard exam problem. Solve (A - I)v = 0, then normalise.
⚠️ Know the distinction between regular and non-regular transition matrices. A quick check: if A or a low power of A has all positive entries, it is regular.
⚠️ Gerschgorin's theorem is a popular "state and apply" exam question. Know how to locate disks and use them to bound eigenvalues.
⚠️ The city-suburb and community college examples from the text are classic exam templates. Understand the setup, the computation of A^m P, and the interpretation of the limit.
True or false: Every transition matrix has 1 as an eigenvalue. A: True (Theorem 5.17).
True or false: If A is a transition matrix and lim A^m exists, then L = lim A^m has rank 1. A: Not always. It is true for regular transition matrices, but absorbing chains can produce limits of higher rank.
True or false: The product of a transition matrix and a probability vector is a probability vector. A: True (Corollary to Theorem 5.15).
Fill in the blank: A regular transition matrix is one for which some power A^s has only ______ entries. A: Positive.
Q: Determine whether lim A^m exists for A = [[0.90, 0.02],[0.10, 0.98]].
A: A is a transition matrix with all positive entries, so it is regular. By Theorem 5.20, lim A^m exists.
Q: Find the fixed probability vector for A = [[0.90, 0.02],[0.10, 0.98]].
A: Solve (A - I)v = 0: [[-0.10, 0.02],[0.10, -0.02]]v = 0. This gives -0.10v_1 + 0.02v_2 = 0, so v_2 = 5v_1. A solution is (1, 5). Normalise: v = (1/6, 5/6). So eventually 1/6 of the population lives in the city and 5/6 in the suburbs.
Q: Does lim A^m exist for A = [[0, 1],[1, 0]]?
A: The eigenvalues of A are 1 and -1. Since -1 is not in S (it is not inside the unit disk and it is not equal to 1), the limit does not exist. Indeed, A^m oscillates between I and A.
Q: Use Gerschgorin's theorem to show that all eigenvalues of a transition matrix satisfy |λ| ≤ 1.
A: For a transition matrix, each column sums to 1. By Corollary 2 to Theorem 5.16, |λ| ≤ ν(A) = max column sum = 1.
Q: In a Markov chain with transition matrix A and initial vector P, what does the vector A^3 P represent?
A: A^3 P gives the probability distribution over all states after 3 steps (3 time periods from the initial state).
Matrix limits connect back to diagonalization (Section 5.2), since computing lim A^m relies on A = QDQ^{-1}. The eigenvalue condition |λ| < 1 or λ = 1 connects to stability theory in differential equations (Section 5.2 application). The Jordan canonical form (Chapter 7) provides the tools to handle condition (b) of Theorem 5.13 in the non-diagonalizable case. Gerschgorin's theorem also connects to numerical linear algebra, where eigenvalue localisation is a standard tool.
matrix limit, limit of matrix powers, Markov chain, Markov process, transition matrix, stochastic matrix, probability vector, regular transition matrix, stationary distribution, fixed probability vector, steady state, Gerschgorin disk theorem, eigenvalue bounds, row sum, column sum, absorbing Markov chain, absorbing state, Hardy-Weinberg law, convergence of matrix sequence