Applications: Difference Equations and 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.¹²

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.

Linear difference equations

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

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.

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. A basis for $H$ is called a fundamental set of solutions.

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

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 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.

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

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$.

Steady-state vectors

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

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$.

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.

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, and the rate of convergence is governed by the ratio of the two largest eigenvalues, the same quantity that drives the power method.