Diagonalization is not only a classification of matrices; it turns repeated or continuous linear evolution into scalar problems. If with diagonal, then every power and every expression built from can be computed from the diagonal entries of . This unit applies the idea to three standard situations: discrete dynamical systems and Markov chains, linear recurrences, and the linear differential system . It uses eigenvalues and eigenvectors (5.1), diagonalization and similarity (5.2) and the diagonalization tests of 5.3.
Powers of a diagonalizable matrix
Theorem 5.5.1
(Powers through an eigenbasis)
Suppose where and the columns of are eigenvectors with . Then for every integer ,
If , then the solution of with initial vector is
Proof
(Canceling the inner factors)
In the product every inner cancels, leaving . For the second statement, by induction on , and linearity gives the formula.
The coefficients are the coordinates of in the eigenvector basis, that is, the solution of .
Markov chains
Definition 5.5.2
(Column-stochastic matrix)
A square matrix is column-stochastic if all entries are nonnegative and every column sums to . If is a vector of probabilities (nonnegative entries summing to ) describing the distribution over states at time , and is the probability of moving from state to state in one step, then .
Theorem 5.5.3
(Eigenvalues of a column-stochastic matrix)
Let be an column-stochastic matrix. Then is an eigenvalue of , and every eigenvalue of (real or complex) satisfies . Moreover, where is the all-ones vector, so : total probability is conserved.
Proof
(The largest entry of an eigenvector of the transpose)
The column sums being says , so is an eigenvalue of . Since , the matrices and have the same eigenvalues. Now let with (possibly complex), and choose with maximal. The -th row of has nonnegative entries summing to , so
Hence .
Proof X-ray
Where nonnegativity and unit sums enter
The proof has two moves. First, and have the same eigenvalues, so it suffices to study ; its rows (not its columns) each sum to , which turns the column condition into a statement about averages. Second, choose the index at which is largest. The -th row of is a set of nonnegative weights summing to , so is a weighted average of the entries of and cannot exceed the largest modulus; this gives , and is what allows the cancellation. Nonnegativity is used in the step . Without it the conclusion fails: has both column sums equal to but eigenvalues and .
Definition 5.5.4
(Stationary distribution)
A probability vector (nonnegative entries summing to ) with is called a stationary distribution of the column-stochastic matrix .
Theorem 5.5.5
(Convergence to the stationary distribution)
Let be column-stochastic and diagonalizable over , with eigenvalue of multiplicity one and all other eigenvalues satisfying . Then there is a vector with and entries summing to , and for every initial vector ,
Proof
(Eigenbasis expansion and conservation of total probability)
Expand with . Then because . Conservation gives for all , so in the limit . Taking shows , so has entries summing to and .
Counterexample mode
Unless the other eigenvalues have modulus below one, the iterates need not converge
Claim: if is column-stochastic, diagonalizable over , and is a simple eigenvalue, then converges for every probability vector . This is false when another eigenvalue has modulus . Take the swap matrix . Its columns sum to , and its eigenvalues are with eigenvector and with eigenvector , so it is diagonalizable and is simple. For we get , , and so on: the sequence alternates and has no limit. In the expansion , the term does not tend to . The repair is the hypothesis for every eigenvalue .
Linear recurrences and differential systems
A recurrence becomes a first-order system for :
The eigenvalues are the roots of , and the power formula gives in closed form when the roots are distinct.
For the differential system , , with , put . Then , which decouples into the scalar equations , with solutions .
Theorem 5.5.6
(Solving the linear system by an eigenbasis)
If has the eigenbasis and , then the unique solution of , is
Proof
(Direct differentiation and uniqueness)
Differentiating, , and . Uniqueness: any solution gives with , whose solutions are determined by since .
The statements on powers, convergence and differential systems above all assume a full eigenbasis. When an eigenvalue is repeated, first apply the diagonalization tests of 5.3 and 5.4.
Worked examples
Worked example 5.5.7
(A Markov chain with a closed-form orbit)
Let (each column sums to ). The trace is and the determinant is , so gives and . For : gives , so . For : gives . Starting from , solve : and give , . Hence
Check at : the formula gives , and directly . The stationary distribution is .
Worked example 5.5.8
(Fibonacci numbers from an eigenbasis)
With , and , put , so with . The eigenvalues are and (roots of ), with eigenvectors and . Write : and give . The second component of is
Check : , so .
Worked example 5.5.9
(A decoupled differential system)
Let and . The eigenvalues are with and with . Since , the eigenbasis solution formula gives
Check: and .
Common mistakes and subtle points
Common mistake
(Row-stochastic conventions reverse the eigenvector)
If the rows rather than the columns of the transition matrix sum to , a row vector of probabilities evolves by , and the stationary vector is a left eigenvector. For (the matrix of the first worked example transposed), the right eigenvector for is , which is not a distribution. The stationary row vector is : indeed .
Common mistake
(An eigenvector is not yet a distribution)
Row reduction gave for in the first worked example, but its entries sum to , not . Every nonzero multiple is also an eigenvector, so the stationary distribution is the multiple whose entries sum to , namely .
Common mistake
(Discrete powers versus continuous exponentials)
For an eigenvalue contributes , and decay needs . For it contributes , and decay needs . For instance gives , which never decays, but ; and gives in the discrete system, while grows in the continuous one.
Exercises
Quick check
(Find the stationary distribution of the column-stochastic matrix and the other eigenvalue.)
Solution · Guided solution
The trace is and the determinant is , so gives eigenvalues and . For : gives ; normalizing by the sum gives the stationary distribution . Check: .
Quick check
(Solve with , .)
Solution · Guided solution
The characteristic equation is with roots and , so . The conditions and give , . Hence . Check: and .
Quick check
(Solve , for .)
Solution · Guided solution
is lower triangular with eigenvalues and . For : gives . For : gives . Solve : , . Hence . Check: and .
Quick check
(Show that the column-stochastic matrix has eigenvalues and , and state when converges for every if .)
Solution · Guided solution
The column sums are , so is an eigenvalue, and the trace is , so the other eigenvalue is . For we have , and exactly when . In that case the matrix is diagonalizable (two distinct eigenvalues) and the convergence theorem gives convergence for every . When the matrix is , so converges trivially, but the limit depends on and there is no unique stationary distribution. When the matrix is the swap and oscillates unless has equal entries. Hence converges for every exactly when , and it converges to times a single stationary distribution exactly when .
Quick check
(Find a formula for where .)
Solution · Guided solution
The eigenvalues have eigenvectors and , so and . Then