---
title: "Applications: Difference Equations and Markov Chains"
module: Vector Spaces
moduleNumber: 4
lessonNumber: 7
order: 407
summary: >
  The solutions of an nth-order linear difference equation form an
  $n$-dimensional vector space, so finding $n$ independent solutions gives them
  all. A Markov chain evolves a probability distribution by repeated multiplication
  by a stochastic matrix, and a regular chain converges to a unique steady-state
  vector fixed by that matrix. Both applications turn a dynamic process into a
  subspace or a fixed-point question.
topics: [Vector Spaces]
draft: false
sources:
  - book: Lay
    ref: "§4.8 Applications to Difference Equations; §4.9 Applications to Markov Chains"
---

Two recurring processes illustrate the vector-space theory. A **linear
difference equation** governs a signal sampled over time, and its solution set is a
subspace whose dimension is known in advance, so a basis of solutions describes
every solution. A **Markov chain** advances a probability distribution one step at
a time by a fixed matrix, and its long-run behavior is a fixed point of that
matrix. In both cases a process becomes a question about subspaces and
bases.[^lay-diff][^lay-markov]

## Signals and their independence

The space $\mathbb{S}$ of discrete-time signals — doubly infinite sequences
$\{y_k\}$ — was one of the first examples of an abstract vector space. Three basic
signals are the geometric sequences $\{(0.7)^k\}$, $\{1^k\}$, and $\{(-1)^k\}$,
which decay, hold, and alternate.

Testing independence in $\mathbb{S}$ uses a determinant built from consecutive
samples. If $c_1 u_k + c_2 v_k + c_3 w_k = 0$ for all $k$, then the same holds at
$k$, $k+1$, $k+2$, giving a $3 \times 3$ system.

> **Definition (Casorati matrix).** For signals $\{u_k\}, \{v_k\}, \{w_k\}$, the
> Casorati matrix at $k$ is
> $$
> \begin{bmatrix} u_k & v_k & w_k \\ u_{k+1} & v_{k+1} & w_{k+1} \\ u_{k+2} & v_{k+2} & w_{k+2} \end{bmatrix},
> $$
> and its determinant is the Casoratian. If the Casorati matrix is invertible for
> at least one $k$, the signals are linearly independent.

> **Worked example.** Show that the signals $\{1^k\}$, $\{(-2)^k\}$, $\{3^k\}$ are
> linearly independent in $\mathbb{S}$.
>
> Form the Casorati matrix from the samples at $k = 0, 1, 2$:
> $$
> \begin{bmatrix} 1 & 1 & 1 \\ 1 & -2 & 3 \\ 1 & 4 & 9 \end{bmatrix}.
> $$
> Its determinant is $-30 \neq 0$, so the matrix is invertible. A nonzero Casoratian
> at even one $k$ forces $c_1 = c_2 = c_3 = 0$ in
> $c_1 1^k + c_2 (-2)^k + c_3 3^k = 0$, so the three signals are independent.

$$
% caption: The three geometric signals $1^k$, $(-2)^k$, and $3^k$ as stem plots:
% one holds constant, one alternates while growing, one grows monotonically. They
% are linearly independent.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\draw[->, black] (-0.3,0) -- (4.6,0) node[right] {$k$};
\draw[->, black] (0,-1.5) -- (0,1.9);
% 1^k (constant, at height 0.9)
\foreach \k in {0,1,2,3,4} {
  \fill[acc] (\k*1.0+0.15,0.9) circle (1.6pt);
  \draw[acc] (\k*1.0+0.15,0) -- (\k*1.0+0.15,0.9);
}
\node[acc, anchor=west, font=\scriptsize] at (4.3,0.9) {$1^k$};
% (-2)^k scaled/clipped (alternating): heights 0.1, -0.2, 0.4, -0.8, ... clip
\foreach \k/\h in {0/0.1, 1/-0.35, 2/0.7, 3/-1.3} {
  \fill[red] (\k*1.0+0.35,\h) circle (1.6pt);
  \draw[red] (\k*1.0+0.35,0) -- (\k*1.0+0.35,\h);
}
\node[red, anchor=west, font=\scriptsize] at (3.4,-1.35) {(-2)$^{k}$};
% 3^k scaled (monotone growth), heights small then clipped
\foreach \k/\h in {0/0.15, 1/0.45, 2/1.35} {
  \fill[black] (\k*1.0+0.55,\h) circle (1.6pt);
  \draw[black] (\k*1.0+0.55,0) -- (\k*1.0+0.55,\h);
}
\node[black, anchor=west, font=\scriptsize] at (2.7,1.55) {$3^k$};
\end{tikzpicture}
$$

## Linear difference equations

> **Definition (Linear difference equation).** Given scalars $a_0, \dots, a_n$
> with $a_0, a_n$ nonzero, and a signal $\{z_k\}$, the equation
> $$
> a_0 y_{k+n} + a_1 y_{k+n-1} + \cdots + a_{n-1} y_{k+1} + a_n y_k = z_k \quad\text{for all } k
> $$
> is a linear difference equation of order $n$. It is homogeneous if $\{z_k\}$ is
> the zero signal; otherwise nonhomogeneous. Taking $a_0 = 1$ is standard.

Solutions of a homogeneous equation are often geometric, $y_k = r^k$. Substituting
$r^k$ and factoring out $r^k$ shows that $r^k$ is a solution exactly when $r$ solves
the **auxiliary equation**

$$
r^n + a_1 r^{n-1} + \cdots + a_{n-1} r + a_n = 0.
$$

For $y_{k+3} - 2y_{k+2} - 5y_{k+1} + 6y_k = 0$, the auxiliary equation factors as
$(r - 1)(r + 2)(r - 3) = 0$, so $1^k$, $(-2)^k$, and $3^k$ are all solutions.

### The solution set is a subspace of known dimension

Define $T : \mathbb{S} \to \mathbb{S}$ by $T\{y_k\} = \{y_{k+n} + a_1 y_{k+n-1} +
\cdots + a_n y_k\}$. This map is linear, so the solution set of the homogeneous
equation is the kernel of $T$, a subspace of $\mathbb{S}$. Two theorems fix its
size.

> **Theorem (Existence and uniqueness).** If $a_n \neq 0$ and $\{z_k\}$ is
> given, the equation has a unique solution once $y_0, \dots, y_{n-1}$ are
> specified. The recurrence propagates the initial values forward and backward.

> **Theorem (Dimension of the solution space).** The set $H$ of all solutions
> of the $n$th-order homogeneous linear difference equation is an $n$-dimensional
> vector space.

The map sending a solution $\{y_k\}$ to its first $n$ values $(y_0, \dots,
y_{n-1})$ is an isomorphism $H \to \mathbb{R}^n$ by the existence-and-uniqueness theorem, so $\dim H = n$.
The consequence is decisive: any $n$ independent solutions automatically span $H$,
by the [basis theorem](/linear-algebra/vector-spaces/dimension-and-rank). A basis
for $H$ is called a **fundamental set of solutions**.

> **Worked example.** Find the general solution of
> $y_{k+3} - 2y_{k+2} - 5y_{k+1} + 6y_k = 0$.
>
> Substituting $y_k = r^k$ and dividing by $r^k$ gives the auxiliary equation
> $$
> r^3 - 2r^2 - 5r + 6 = 0,
> $$
> which factors as $(r - 1)(r + 2)(r - 3) = 0$. The roots $1, -2, 3$ produce three
> solutions $1^k$, $(-2)^k$, $3^k$, shown independent above. The solution space is
> three-dimensional by the solution-space dimension theorem, so these three form a basis, and every solution is
> $$
> y_k = c_1 \cdot 1^k + c_2 (-2)^k + c_3 \cdot 3^k.
> $$

Spanning never has to be checked directly; it follows from the dimension count.
Complex roots of
the auxiliary equation give solutions $s^k \cos k\omega$ and $s^k \sin k\omega$, and
a repeated root is handled separately.

### Nonhomogeneous equations and first-order form

The general solution of a nonhomogeneous equation is a particular solution plus the
general homogeneous solution, exactly as for $Ax = b$ versus $Ax = 0$, because the
map $\{y_k\} \mapsto \{z_k\}$ is linear. For $y_{k+2} - 4y_{k+1} + 3y_k = -4k$, the
signal $y_k = k^2$ is a particular solution, and the homogeneous equation has roots
$1, 3$, so

$$
y_k = k^2 + c_1 \cdot 1^k + c_2 \cdot 3^k.
$$

A modern treatment rewrites an $n$th-order equation as a first-order system
$x_{k+1} = A x_k$ using the **companion matrix**. Stacking $n$ consecutive values
into $x_k = (y_k, y_{k+1}, \dots, y_{k+n-1})$ turns the recurrence into a single
matrix multiplication, which is the form a Markov chain also takes and which
[discrete dynamical systems](/linear-algebra/eigenvalues/dynamical-systems) analyze
through eigenvalues.

## Markov chains

A Markov chain models a process observed repeatedly, where the next state depends
only on the current one. The state is a distribution over finitely many
possibilities.

> **Definition (Probability vector, stochastic matrix, Markov chain).** A
> probability vector has nonnegative entries summing to $1$. A stochastic matrix is
> a square matrix whose columns are probability vectors. A Markov chain is a
> sequence of probability vectors $x_0, x_1, x_2, \dots$ with a stochastic matrix
> $P$ such that
> $$
> x_{k+1} = P x_k \quad\text{for } k = 0, 1, 2, \dots
> $$

Each $x_k$ is a **state vector**: its entries are the probabilities of the possible
states at step $k$. For a metropolitan region split into city and suburb, with $5\%$
of the city moving to the suburb and $3\%$ of the suburb moving to the city each
year, the migration matrix and one year's update are

$$
M = \begin{bmatrix} 0.95 & 0.03 \\ 0.05 & 0.97 \end{bmatrix},
\qquad
x_1 = M x_0 = \begin{bmatrix} 0.95 & 0.03 \\ 0.05 & 0.97 \end{bmatrix}\begin{bmatrix} 0.60 \\ 0.40 \end{bmatrix} = \begin{bmatrix} 0.582 \\ 0.418 \end{bmatrix}.
$$

$$
% caption: The two-state chain for an urban core and its suburb: each year $5\%$ of
% the urban population moves to the suburb and $3\%$ of the suburb moves back, and
% the arrows leaving each state sum to $1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
\definecolor{acc}{HTML}{2F6DB5}
\node[draw, acc, thick, circle, minimum size=15mm] (C) at (0,0) {Urban};
\node[draw, acc, thick, circle, minimum size=15mm] (S) at (4.5,0) {Suburb};
\draw[->, black] (C) to[bend left=15] node[above, font=\scriptsize] {0.05} (S);
\draw[->, black] (S) to[bend left=15] node[below, font=\scriptsize] {0.03} (C);
\draw[->, black] (C) to[out=140, in=200, looseness=6] node[left, font=\scriptsize] {0.95} (C);
\draw[->, black] (S) to[out=340, in=40, looseness=6] node[right, font=\scriptsize] {0.97} (S);
\end{tikzpicture}
$$

A transition among more states is read off a labelled graph: an edge from state $i$
to state $j$ carries the probability that $i$ becomes $j$, and the edges leaving each
state sum to $1$.

$$
% caption: A three-state transition graph for voting Democratic, Republican, or
% Libertarian; each edge shows the probability of moving between blocs, and the
% probabilities leaving each state sum to 1.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
\definecolor{acc}{HTML}{2F6DB5}
\node[draw, acc, thick, circle, minimum size=13mm] (D) at (0,0) {Dem};
\node[draw, acc, thick, circle, minimum size=13mm] (R) at (5,0) {Rep};
\node[draw, acc, thick, circle, minimum size=13mm] (L) at (2.5,-3) {Lib};
\draw[->, black] (D) to[bend left=12] node[above, font=\scriptsize] {0.20} (R);
\draw[->, black] (R) to[bend left=12] node[below, font=\scriptsize] {0.10} (D);
\draw[->, black] (D) to[bend right=12] node[left, font=\scriptsize] {0.10} (L);
\draw[->, black] (L) to[bend right=12] node[below right, font=\scriptsize] {0.30} (D);
\draw[->, black] (R) to[bend left=12] node[right, font=\scriptsize] {0.10} (L);
\draw[->, black] (L) to[bend left=12] node[above right, font=\scriptsize] {0.30} (R);
\draw[->, black] (D) to[out=120, in=170, looseness=6] node[left, font=\scriptsize] {0.70} (D);
\draw[->, black] (R) to[out=60, in=10, looseness=6] node[right, font=\scriptsize] {0.80} (R);
\draw[->, black] (L) to[out=250, in=290, looseness=6] node[below, font=\scriptsize] {0.40} (L);
\end{tikzpicture}
$$

## Steady-state vectors

The long-run behavior of a chain is governed by a distribution the matrix leaves
unchanged.

> **Definition (Steady-state vector).** A steady-state (or equilibrium) vector for
> a stochastic matrix $P$ is a probability vector $q$ with $Pq = q$.

Every stochastic matrix has one. Finding it is an eigenvector computation at
eigenvalue $1$: rewrite $Pq = q$ as $(P - I)q = 0$ and solve the homogeneous system,
then rescale the solution to sum to $1$.

```algorithm
caption: $\textsc{SteadyState}(P)$ — the equilibrium distribution of a stochastic matrix
form the matrix $P - I$
solve $(P - I)x = 0$ by row reduction // the eigenspace for eigenvalue 1
choose a basis vector $w$ with integer or simple entries
$s \gets$ sum of the entries of $w$
return $q \gets w / s$ // rescale to a probability vector
```

> **Worked example.** Find the steady-state vector of
> $P = \begin{bmatrix} 0.6 & 0.3 \\ 0.4 & 0.7 \end{bmatrix}$.
>
> Solve $(P - I)q = 0$. Form $P - I$ and row reduce:
> $$
> P - I = \begin{bmatrix} -0.4 & 0.3 \\ 0.4 & -0.3 \end{bmatrix}
> \sim
> \begin{bmatrix} 1 & -\tfrac{3}{4} \\ 0 & 0 \end{bmatrix}.
> $$
> So $x_1 = \tfrac{3}{4} x_2$ with $x_2$ free. Choosing $x_2 = 4$ clears fractions:
> $w = (3, 4)$. Rescaling to sum to $1$,
> $$
> q = \frac{1}{7}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 3/7 \\ 4/7 \end{bmatrix}.
> $$
> A check confirms $Pq = q$.

> **Definition (Regular stochastic matrix).** A stochastic matrix $P$ is regular if
> some power $P^k$ has all strictly positive entries.

> **Theorem (Convergence to steady state).** If $P$ is an $n \times n$ regular
> stochastic matrix, then $P$ has a unique steady-state vector $q$, and for any
> initial state $x_0$ the chain $x_{k+1} = P x_k$ converges to $q$ as $k \to
> \infty$.

The initial distribution has no effect on the limit. The city-suburb matrix $M$ has
all positive entries, so it is regular; its steady-state vector is $q = (0.375,
0.625)$, meaning the region tends toward $37.5\%$ city and $62.5\%$ suburb no matter
where it starts.

$$
% caption: State-vector entries of a regular chain converge to the steady-state
% values regardless of the start; here the three components settle to $0.3$,
% $0.6$, and $0.1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\draw[->, black] (-0.2,0) -- (6.2,0) node[right] {$k$};
\draw[->, black] (0,-0.2) -- (0,3.0) node[above] {entry};
\foreach \y/\lab in {0/0, 1.5/0.5, 3.0/1.0} \node[black, anchor=east, font=\scriptsize] at (-0.1,\y) {\lab};
% component -> 0.6 (from 0.9 down): red
\draw[red, thick] plot[smooth] coordinates {(0,2.7) (1,2.05) (2,1.95) (3,1.85) (4,1.82) (5,1.81) (6,1.8)};
\node[red, anchor=west, font=\scriptsize] at (6.0,1.8) {to 0.6};
% component -> 0.3 (from 0 up): acc
\draw[acc, thick] plot[smooth] coordinates {(0,0) (1,0.6) (2,0.78) (3,0.85) (4,0.88) (5,0.89) (6,0.9)};
\node[acc, anchor=west, font=\scriptsize] at (6.0,0.9) {to 0.3};
% component -> 0.1 (from 0.3 down): black
\draw[black, thick] plot[smooth] coordinates {(0,0.9) (1,0.45) (2,0.37) (3,0.33) (4,0.31) (5,0.305) (6,0.3)};
\node[black, anchor=west, font=\scriptsize] at (6.0,0.3) {to 0.1};
\draw[black, dashed] (0,1.8) -- (6,1.8);
\draw[black, dashed] (0,0.9) -- (6,0.9);
\draw[black, dashed] (0,0.3) -- (6,0.3);
\end{tikzpicture}
$$

The reason distinct starting points converge to the same $q$ is that $1$ is the
dominant eigenvalue of a regular stochastic matrix, with every other eigenvalue
smaller in magnitude, so the other components of $x_0$ decay under repeated
multiplication. That explanation is developed in
[eigenvalues and eigenvectors](/linear-algebra/eigenvalues/eigenvectors-and-eigenvalues),
and the rate of convergence is governed by the ratio of the two largest
eigenvalues, the same quantity that drives the
[power method](/linear-algebra/eigenvalues/power-method).

[^lay-diff]: **Lay**, _Linear Algebra and Its Applications_, §4.8 — Applications to Difference Equations: the space $\mathbb{S}$, the Casorati test, the auxiliary equation, Theorem 16 (existence/uniqueness), and Theorem 17 (the solution space is $n$-dimensional).
[^lay-markov]: **Lay**, _Linear Algebra and Its Applications_, §4.9 — Applications to Markov Chains: probability vectors, stochastic matrices, state vectors, steady-state vectors via $(P - I)q = 0$, regular matrices, and Theorem 18 (convergence to a unique steady state).