Linear Algebra · Lesson 05

Powers and long-run behaviour

Applying a map again and again stretches each eigenvector by its eigenvalue again and again. Eigenvalues larger than one in size win, those smaller than one fade away, and the long-run behaviour of a repeated process can be read off the eigenvalues without computing a single power.

Foundations8 min readRevision 1

Read freely. Sign in when you want to save your place.

Sign in to save progress

A^{k} = P D^{k} P^{- 1}

λ_{i}^{k}

Chapter navigation

Intuition

Applying a map again and again stretches each eigenvector by its eigenvalue again and again. Eigenvalues larger than one in size win, those smaller than one fade away, and the long-run behaviour of a repeated process can be read off the eigenvalues without computing a single power.

Several savings accounts at different interest rates, left alone for decades, end up dominated by the one with the highest rate. The eigenvalues are the rates, and the eigenvectors the accounts.

Powers through eigenvectors

If $A=PDP^{-1}$ , then , and is diagonal with entries . Equivalently, write a vector in a basis of eigenvectors, ; then . For large the terms with the largest dominate.

A^{k} v = λ^{k} v

A = P D P^{- 1}

- 1

A^k=PD^kP^{-1}

D^k

\lambda_i^k

\mathbf{x}=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n

A^k\mathbf{x}=c_1\lambda_1^k\mathbf{v}_1+\cdots+c_n\lambda_n^k\mathbf{v}_n

k

|\lambda_i|

A^k\mathbf{x}=c_1\lambda_1^k\mathbf{v}_1+\cdots+c_n\lambda_n^k\mathbf{v}_n

Reading the long run

If every $|\lambda_i|<1$ , then $A^k\mathbf{x}\to\mathbf{0}$ for every $\mathbf{x}$ .
If one eigenvalue is larger in size than all the others and $c_1\neq0$ , then $A^k\mathbf{x}$ lines up with its eigenvector, growing or shrinking like .
A Markov matrix has non-negative entries and columns adding up to $1$ ; it moves shares of a population between states. $1$ is always an eigenvalue, because $A^{T}$ sends $(1,\ldots,1)$ to itself and and have the same eigenvalues.
When the other eigenvalues of a Markov matrix have $|\lambda|<1$ , the shares settle on the eigenvector for $1$ , scaled to add up to $1$ , whatever the start.

Each year $10\%$ of the people of town A move to town B and $20\%$ of those of B move to A. Starting with everybody in B, the share in A climbs year by year towards $\tfrac23$ . The Markov matrix $\begin{pmatrix}0.9&0.2\\0.1&0.8\end{pmatrix}$ has eigenvalues $1$ and $0.7$ : the eigenvector for $1$ , $(2,1)$ , is the long run, and the gap to it shrinks by the factor $0.7$ each year.

Powers of a diagonalisable matrix

A=PDP^{-1}\implies A^k=PD^kP^{-1}

Multiply two copies of $PDP^{-1}$ : the $P^{-1}P$ in the middle is $I$ and disappears, leaving $PD^2P^{-1}$ . Each further factor cancels the same way. A power of a diagonal matrix is taken entry by entry on the diagonal, so $A^k$ costs two multiplications however large $k$ is.

Proof steps

A^2=PDP^{-1}PDP^{-1}=PD^2P^{-1}

The inner $P^{-1}P$ is $I$ .

A^{k+1}=PD^kP^{-1}\,PDP^{-1}=PD^{k+1}P^{-1}

The same cancellation at every step.

D^k=\operatorname{diag}(\lambda_1^k,\ldots,\lambda_n^k)

A diagonal matrix is multiplied entry by entry on its diagonal.

A^k\mathbf{v}_i=\lambda_i^k\mathbf{v}_i

Equivalently, each eigenvector is stretched by $\lambda_i$ at every step, so $k$ steps multiply it by $\lambda_i^k$ .

Applications

Practice

Powers of a Diagonal Matrix

A diagonal matrix is powered entry by entry: each diagonal entry is raised to the power, and the zeros stay zeros.

\begin{pmatrix}2&0\\0&3\end{pmatrix}^{4}=\begin{pmatrix}16&0\\0&81\end{pmatrix}

Try it

What is the entry in row 2, column 2 of $\begin{pmatrix}-1&0\\0&3\end{pmatrix}^{5}$ ?