[ALGEBRA] Spectral applications

Matrix powers, independent modes and long-term behaviour through diagonalisation.

This page uses diagonalisation to compute matrix powers and to read the long-term behaviour of each mode. In an eigenbasis, repeated multiplication by $A$ becomes repeated scalar multiplication, so the first question is how many independent modes a repeated eigenvalue supplies.

The same separation reappears in linear ODE systems, with $e^{\lambda t}$ in place of $\lambda^n$ and in Markov systems, with a probability interpretation.

Multiplicities

[DEFINITION]

Diagonalisation

An $n\times n$ matrix $A$ over a field $F$ is diagonalisable over $F$ if there are an invertible matrix $P\in M_n(F)$ and a diagonal matrix $D\in M_n(F)$ such that

P^{-1}AP=D, \qquad\text{equivalently}\qquad A=PDP^{-1}.

The columns of $P$ are the eigenvectors in the chosen eigenbasis and the corresponding eigenvalues appear on the diagonal of $D$ .

[DEFINITION]

Algebraic multiplicity

The algebraic multiplicity of an eigenvalue $\lambda$ is its multiplicity as a root of the characteristic polynomial.

[DEFINITION]

Geometric multiplicity

The geometric multiplicity of an eigenvalue $\lambda$ is the dimension of its eigenspace $E_\lambda$ .

The geometric multiplicity counts the independent eigenvectors available for that eigenvalue and hence how many it can contribute to an eigenbasis.

These two counts explain the failed diagonalisation example: an eigenvalue can repeat in the characteristic polynomial while its eigenspace supplies too few independent eigenvectors.

[THEOREM]

Comparing the multiplicities

For every eigenvalue,

\text{geometric multiplicity} \leq \text{algebraic multiplicity}.

[PROOF]

Let $g=\dim E_\lambda$ and begin a basis of the whole space with a basis of $E_\lambda$ . In these coordinates, the first $g$ columns of $A$ have $\lambda I_g$ in their first $g$ entries and zeros below. Thus $A-tI$ is block upper triangular, with $\lambda-t$ on each of those $g$ diagonal positions. Its determinant has the factor $(\lambda-t)^g$ , so the algebraic multiplicity is at least $g$ .

[1]:Comparing the multiplicities

[EXAMPLE]

Three repeated-eigenvalue cases

Consider the three matrices

A_1= \begin{pmatrix} 3&2&0\\ 0&3&2\\ 0&0&3 \end{pmatrix}, \qquad A_2= \begin{pmatrix} 3&0&0\\ 0&3&2\\ 0&0&3 \end{pmatrix}, \qquad A_3=3I.

Each has characteristic polynomial $(3-\lambda)^3$ , so the algebraic multiplicity of $\lambda=3$ is $3$ .

For $A_1$ ,

A_1-3I= \begin{pmatrix} 0&2&0\\ 0&0&2\\ 0&0&0 \end{pmatrix},

so $x_2=x_3=0$ and

E_3=\operatorname{span}\left\{ \begin{pmatrix}1\\0\\0\end{pmatrix} \right\}.

The geometric multiplicity is $1$ .

For $A_2$ ,

A_2-3I= \begin{pmatrix} 0&0&0\\ 0&0&2\\ 0&0&0 \end{pmatrix},

so $x_3=0$ and

E_3=\operatorname{span}\left\{ \begin{pmatrix}1\\0\\0\end{pmatrix}, \begin{pmatrix}0\\1\\0\end{pmatrix} \right\}.

The geometric multiplicity is $2$ . Finally, $A_3-3I=0$ , so the eigenspace is $\mathbb R^3$ and the geometric multiplicity is $3$ . Only the last case has three independent eigenvectors and hence an eigenbasis.

[routine]

[1]:Algebraic multiplicity
[2]:Geometric multiplicity

Matrix powers

[PROPOSITION]

Powers of a diagonal matrix

D=\operatorname{diag}(\lambda_1,\ldots,\lambda_m),

then, for every non-negative integer $k$ ,

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

The matrix stays diagonal because each coordinate direction is acted on independently.

[PROOF]

For $k=0$ , both sides equal $I$ . If the formula holds for $k$ , then

D^{k+1}=D^kD =\operatorname{diag}(\lambda_1^k\lambda_1,\ldots,\lambda_m^k\lambda_m) =\operatorname{diag}(\lambda_1^{k+1},\ldots,\lambda_m^{k+1}).

Induction proves the result.

[1]:Powers of a diagonal matrix

[THEOREM]

Powers after diagonalisation

A=PDP^{-1},

then, for every non-negative integer $k$ ,

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

[1]:Diagonalisation
[2]:Powers of a diagonal matrix
[3]:Proof
[4]:Compute a matrix power by diagonalisation

[PROOF]

For $k=0$ , both sides are $I$ . If $A^k=PD^kP^{-1}$ , then

A^{k+1} =A^kA =PD^kP^{-1}PDP^{-1} =PD^{k+1}P^{-1}.

[1]:Powers after diagonalisation

[METHOD]

Compute a matrix power by diagonalisation

To compute $A^k x_0$ for a non-negative integer $k$ when $A$ is diagonalisable:

choose an eigenbasis and form $P$ from its eigenvectors;
form the diagonal matrix $D$ from the corresponding eigenvalues;
write $A=PDP^{-1}$ ;
replace $A^k$ by $PD^kP^{-1}$ , so the powers are taken only on the diagonal;
apply the result to $x_0$ .

Equivalently, if $x_0=c_1v_1+\cdots+c_nv_n$ in the eigenbasis, then

A^kx_0 =c_1\lambda_1^kv_1+\cdots+c_n\lambda_n^kv_n.

This form shows each mode evolving on its own.

[1]:Diagonalisation
[2]:Powers after diagonalisation
[3]:Evolve a Markov system by diagonalisation
[4]:Markov systems
[5]:Diagonalisation of a stress matrix
[6]:Long-term behaviour of the modes
2 more

[THEOREM]

Discrete stability from root moduli

Write a characteristic root in polar form as

r_j=\rho_j e^{i\theta_j}.

Then

|r_j^n|=\rho_j^n.

Thus $\rho_j<1$ gives a decaying mode, $\rho_j>1$ gives an unbounded mode and $\rho_j=1$ gives a non-decaying mode.

Long-term behaviour

[THEOREM]

Long-term behaviour of the modes

Suppose $A=PDP^{-1}$ is diagonalisable, so it has an eigenbasis. A mode contribution $c\lambda^kv$ with $c\ne0$ decays to zero when $|\lambda|<1$ , has constant magnitude when $|\lambda|=1$ and grows when $|\lambda|>1$ . Without an eigenbasis, a Jordan block can produce additional factors such as $k\lambda^{k-1}$ , so the diagonalisation hypothesis is what makes this scalar classification complete (especially at the unit circle).

This is the modulus test for the modes of a scalar recurrence from stability of systems. Diagonalisation reduces a matrix recurrence to such scalar modes.

[EXAMPLE]

Powers of the all-ones matrix

For

A= \begin{pmatrix} 1&1\\ 1&1 \end{pmatrix},

use the eigenvectors computed for the all-ones matrix:

P= \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}, \qquad D= \begin{pmatrix} 2&0\\ 0&0 \end{pmatrix}, \qquad P^{-1} =\frac12 \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}.

Therefore, for $n\geq1$ ,

\begin{aligned} A^n &=PD^nP^{-1}\\ &=\frac12 \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix} \begin{pmatrix} 2^n&0\\ 0&0 \end{pmatrix} \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}\\ &=2^{n-1} \begin{pmatrix} 1&1\\ 1&1 \end{pmatrix}. \end{aligned}

For $x_0=(a,b)^{\mathsf T}$ ,

A^nx_0 =2^{n-1}(a+b) \begin{pmatrix}1\\1\end{pmatrix}.

The component in the $0$ -eigenspace disappears after one step, while the component in the $2$ -eigenspace grows like $2^n$ .

[routine]

[EXAMPLE]

A three-by-three power

Let

A= \begin{pmatrix} 3&1&1\\ 0&2&0\\ 0&0&2 \end{pmatrix},

and take the eigenvectors

v_1=\begin{pmatrix}1\\0\\0\end{pmatrix}, \qquad v_2=\begin{pmatrix}-1\\0\\1\end{pmatrix}, \qquad v_3=\begin{pmatrix}-1\\1\\0\end{pmatrix},

for eigenvalues $3,2,2$ , respectively. Then

P= \begin{pmatrix} 1&-1&-1\\ 0&0&1\\ 0&1&0 \end{pmatrix}, \qquad D= \begin{pmatrix} 3&0&0\\ 0&2&0\\ 0&0&2 \end{pmatrix}, \qquad P^{-1}= \begin{pmatrix} 1&1&1\\ 0&0&1\\ 0&1&0 \end{pmatrix}.

The multiplication check gives $A=PDP^{-1}$ and hence

A^n=P \begin{pmatrix} 3^n&0&0\\ 0&2^n&0\\ 0&0&2^n \end{pmatrix} P^{-1} = \begin{pmatrix} 3^n&3^n-2^n&3^n-2^n\\ 0&2^n&0\\ 0&0&2^n \end{pmatrix}.

The eigenvalue $2$ is repeated but has two independent eigenvectors, $v_2$ and $v_3$ . Together with $v_1$ they form an eigenbasis, so the diagonal power calculation is valid.

[exam]

[1]:Compute a matrix power by diagonalisation

Next, linear ODE systems use the same mode decomposition in continuous time.

Spectral applications

Diagonalisation

Discrete stability from root moduli

On this page