Matrix Powers, Recurrences, and Linear Dynamics

Repeated application of one linear rule produces a discrete recurrence. Letting the current state determine its rate of change produces a continuous dynamical system. An eigenvector basis separates coupled states into independent modes.

Diagonalization turns matrix powers into scalar powers

If $A=SDS^{-1}$, the intermediate factors cancel:

$$A^n=SD^nS^{-1}.$$

The diagonal matrix $D^n$ replaces every eigenvalue by $\lambda_i^n$. Expanding an initial state in the eigenvector basis gives

$$\mathbf x_n=A^n\mathbf x_0 =\sum_i c_i\lambda_i^n\mathbf v_i.$$

Long-term behavior depends on which $c_i$ are nonzero and on the magnitudes $|\lambda_i|$. Cancellation, repeated roots, and nondiagonalizable cases require additional care.

A higher-order recurrence becomes first order in a larger state

The chapter on sequences and recurrences emphasizes that a recurrence needs initial values. For

$$u_{n+2}=a u_{n+1}+b u_n,$$

set $\mathbf x_n=(u_{n+1},u_n)^{\mathsf T}$. Then

$$\mathbf x_{n+1} =\begin{pmatrix}a&b\\1&0\end{pmatrix}\mathbf x_n.$$

The companion matrix has characteristic equation $\lambda^2-a\lambda-b=0$, the same equation used in the scalar method. The state also preserves the roles of both initial values.

For Fibonacci, $a=b=1$. The eigenvalues are $\varphi=(1+\sqrt5)/2$ and $\psi=(1-\sqrt5)/2$. Solving for the initial-state coefficients gives Binet's formula, and the growth ratio approaches $\varphi$ because $|\psi|<1<\varphi$.

Initial conditions determine the specific recurrence

For Fibonacci, fix $F_0=0,F_1=1$. The distinct roots give

$$F_n=c\varphi^n+d\psi^n.$$

The initial conditions require $c+d=0$ and $c\varphi+d\psi=1$. Since $\varphi-\psi=\sqrt5$,

$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5}.$$

With $T_0=T_1=1$, the same recurrence instead gives $T_n=F_{n+1}$. An identical update rule does not imply identical values or threshold times.

A Markov update is another linear dynamical system

The column-stochastic model in Matrix as Graph obeys

$$\mathbf p_{n+1}=P\mathbf p_n.$$

Conservation gives $\mathbf1^{\mathsf T}P=\mathbf1^{\mathsf T}$, while a stationary state satisfies $P\boldsymbol\pi=\boldsymbol\pi$. Eigenvalue $1$ preserves the stationary component; other modes determine how deviations decay or oscillate.

The existence of eigenvalue $1$ alone does not prove convergence. A two-state swap has a stationary distribution and another unit-modulus mode that oscillates forever. Irreducibility, periodicity, and spectral structure control the general result.

Continuous time replaces powers by a matrix exponential

For

$$\mathbf x'(t)=A\mathbf x(t), \qquad \mathbf x(0)=\mathbf x_0,$$

define

$$\mathbf x(t)=e^{tA}\mathbf x_0, \qquad e^{tA}=\sum_{k=0}^{\infty}\frac{t^kA^k}{k!}.$$

Termwise differentiation verifies $(e^{tA})'=Ae^{tA}$. If $A=SDS^{-1}$, then

$$e^{tA}=S\operatorname{diag}(e^{\lambda_1t},\ldots,e^{\lambda_nt})S^{-1}.$$

Why termwise differentiation is valid

Choose a submultiplicative matrix norm. On any bounded interval $|t|\le T$,

$$\left\|\frac{t^kA^k}{k!}\right\| \le\frac{(T\|A\|)^k}{k!}.$$

A convergent scalar exponential series bounds the terms; the derivative series has a similar bound. Local uniform convergence justifies differentiation. This assumes constant $A$; an arbitrary time-dependent matrix cannot simply be substituted into the same formula.

For continuous forcing, the initial-value solution is

$$\mathbf x(t)=e^{tA}\mathbf x_0+ \int_0^t e^{(t-s)A}\mathbf f(s)\,ds.$$

Differentiation verifies the equation and initial condition: the upper endpoint contributes $\mathbf f(t)$ and the remaining terms give $A\mathbf x(t)$.

One concrete submultiplicative norm is $\|A\|_\infty=\max_i\sum_j|a_{ij}|$: applying the triangle inequality to each row of $AB$ gives $\|AB\|_\infty\le\|A\|_\infty\|B\|_\infty$. The scalar exponential series and the theorem on differentiating uniformly convergent derivative series are analysis prerequisites used here; their general proofs remain to be developed in the series chapter.

Absolute convergence permits regrouping the product series. The binomial formula then gives

$$e^{sA}e^{tA} =\sum_{k=0}^{\infty}\left(\sum_{j=0}^k\frac{s^jt^{k-j}}{j!(k-j)!}\right)A^k =e^{(s+t)A}.$$

In particular $e^{-tA}$ is the inverse of $e^{tA}$. For any differentiable homogeneous solution, the product rule gives $(e^{-tA}\mathbf x(t))'=0$, hence $\mathbf x(t)=e^{tA}\mathbf x(0)$. This proves uniqueness as well as existence. Subtracting two forced solutions proves uniqueness there too.

A forced system is particular plus homogeneous

For $\mathbf x'=A\mathbf x+\mathbf f(t)$, if $\mathbf x_p$ is one particular solution, the difference of any two solutions satisfies the homogeneous equation. Hence all solutions have the form

$$\mathbf x(t)=\mathbf x_p(t)+e^{tA}\mathbf c.$$

This is the same structure as particular solution plus kernel. Linearity is essential to the superposition argument.

Stability is decided mode by mode

For a diagonalizable discrete system, every mode decays when all eigenvalues have modulus below $1$. In continuous time, all eigenvalues must have negative real part. Boundary cases and nondiagonalizable matrices require separate analysis because Jordan blocks can introduce factors such as $n\lambda^n$ or $t e^{\lambda t}$.

For a diagonalizable matrix, the finite modal sum proves sufficiency directly, since $|\lambda|^n\to0$ for $|\lambda|<1$ and $|e^{t\lambda}|=e^{t\operatorname{Re}\lambda}\to0$ for negative real part. Necessity follows by choosing the initial state as an eigenvector: a mode outside these strict regions does not tend to zero. For real matrices with complex modes, convergence of every real initial state would imply convergence of its complex linear combinations, so the same necessity holds.

To see the boundary obstruction without invoking a Jordan-form theorem, take $J=\lambda I+N$ with $N^2=0$. Expanding the binomial and exponential series yields

$$J^n=\lambda^n I+n\lambda^{n-1}N\quad(n\ge1), \qquad e^{tJ}=e^{t\lambda}(I+tN).$$

The polynomial factors explain growth on a nontrivial block even when the scalar boundary mode would be bounded. At $\lambda=0$, handle $n=1$ as $J=N$ and $n\ge2$ as $J^n=0$, avoiding an undefined power.

Discrete and continuous stability use different criteria

The scalar update $x_{n+1}=-2x_n$ oscillates and grows, whereas $x'=-2x$ has decaying solution $e^{-2t}x_0$. Discrete models depend on eigenvalue modulus; continuous models depend on real part. Exact sampling of a continuous system with interval $h$ gives transition matrix $e^{hA}$ and eigenvalues $e^{h\lambda_i}$.

Exercises

ExerciseState for a second-order recurrence

Write $u_{n+2}=3u_{n+1}-2u_n$ as a matrix recurrence and find its eigenvalues.

Solution

The state matrix is

$$$$$$\begin{pmatrix}3&-2\\1&0\end{pmatrix}$$$$$$

, with characteristic equation $(\lambda-1)(\lambda-2)=0$.

ExerciseDiscrete stability

A diagonalizable matrix has eigenvalues $1/2$ and $-1/3$. Find the limit of $A^n\mathbf x_0$.

Solution

The two modal coefficients are multiplied by $(1/2)^n$ and $(-1/3)^n$. Both vanish, so every initial state tends to zero.

ExerciseVerify a matrix exponential

Find $e^{tA}$ for $A=\operatorname{diag}(2,-1)$.

Solution

$e^{tA}=\operatorname{diag}(e^{2t},e^{-t})$, since every power of $A$ remains diagonal.