Markov Matrices; Fourier Series

What makes a matrix Markov

This lecture is about applications of eigenvalues, and the star is the Markov matrix. Strang just invents one:

$$A = \begin{bmatrix} .1 & .01 & .3 \\ .2 & .99 & .3 \\ .7 & 0 & .4 \end{bmatrix}$$

Why those two properties? Markov matrices are connected to probability, and probabilities are never negative; the columns add to one because probabilities of all the possibilities add to one. And since we’ll be interested in the powers $A^k$, it matters that the properties persist.

The question that drives everything is steady state. Last time, with differential equations, a steady state came from an eigenvalue $\lambda = 0$ — the $e^{0t}$ term sat still while the others moved. With powers of a matrix it’s different: a zero eigenvalue dies immediately. For powers, it’s an eigenvalue of one that’s all-important. The two key facts about Markov matrices:

1. $\lambda = 1$ is an eigenvalue — always, and you can know it without computing a single determinant.
2. All other eigenvalues have $|\lambda| \lt 1$ (with possible exceptional cases where another eigenvalue has magnitude equal to one — but never larger).

Recall the general formula for powers. If $u_{k} = A^k u_0$ and $A$ has a complete set of eigenvectors (Strang: “my conscience always makes me say at least once per lecture” that this is required), then

$$u_k = A^k u_0 = c_1 \lambda_1^k \mathbf{x}_1 + c_2 \lambda_2^k \mathbf{x}_2 + \cdots$$

Now watch what the two key facts do. Take $\lambda_1 = 1$: the first term is $c_1 \mathbf{x}_1$ forever. Every other $\lambda_i$ is smaller than one in magnitude, so $\lambda_i^k \to 0$ — those terms die as we iterate. The steady state is $c_1 \mathbf{x}_1$: the steady state is the eigenvector for $\lambda = 1$, scaled by however much of it was in the initial condition. And there’s one more special fact: that eigenvector $\mathbf{x}_1$ has all components $\geq 0$ — no negative components — so the steady state is positive if the start was. (Strang states this without proof.)

Why one is an eigenvalue

If $1$ is an eigenvalue of $A$, then $A - I$ should be singular — the eigenvalues are exactly the shifts that make the matrix singular. Subtract the identity from the example:

$$A - I = \begin{bmatrix} -.9 & .01 & .3 \\ .2 & -.01 & .3 \\ .7 & 0 & -.6 \end{bmatrix}$$

What happened to the columns? They added to one; now all columns of $A - I$ add to zero. Why does that force singularity? This could be a theoretical quiz question, and we’re at a point in the course with several ways to see it. We don’t want the determinant. Singular means the columns are dependent — but it’s the rows that are easier here. What combination of the three rows gives the zero row? Just add them: one times each row, and every column sums to zero. So the rows are dependent, the matrix is singular, done.

That combination $(1, 1, 1)$ is multiplying the rows, so it lives in the left null space: $(1,1,1)$ is in $N(A^T - I)$ — it’s an eigenvector of $A^T$ with eigenvalue 1. And who is in the null space of $A - I$ itself? Some combination of the columns gives zero, and the three numbers in that combination are exactly the eigenvector $\mathbf{x}_1$ — the steady state.

So the reasoning chain: columns of $A$ add to one $\Rightarrow$ columns of $A - I$ add to zero $\Rightarrow$ $(1,1,1)$ kills the rows $\Rightarrow$ $A^T$ has eigenvalue 1 $\Rightarrow$ so does $A$.

Where Markov matrices come from: California and Massachusetts

The equation being studied is $u_{k+1} = A u_k$ with $A$ Markov. Strang’s example: two states — literally, California and Massachusetts — and the populations in each. Every year, some fraction of each population stays and some fraction moves:

$$\begin{bmatrix} u_{\text{Cal}} \\ u_{\text{Mass}} \end{bmatrix}_{k+1} = \begin{bmatrix} .9 & .2 \\ .1 & .8 \end{bmatrix} \begin{bmatrix} u_{\text{Cal}} \\ u_{\text{Mass}} \end{bmatrix}_{k}$$

Read column one: of the people in California at time $k$, nine tenths stay and one tenth move to Massachusetts — the column adds to one because all Californians are accounted for. Column two: after the Red Sox fail again, only 80 percent of Massachusetts stays and 20 percent moves to California. Entries $\geq 0$ because they’re probabilities; columns summing to one because nobody is gained or lost. The Markov chain conserves total population. (One severe limitation of the model: the same matrix, the same probabilities, act at every time step, forever.)

Start everyone in Massachusetts: $u_0 = (0, 1000)$. After one step, multiply once by $A$: a thousand times column two gives $(200, 800)$. Next step, more move west, twenty come back — California ends up above 200, the total still 1000. What about step 100? For any question like that, we need eigenvalues and eigenvectors.

Eigenvalues. One of them is $\lambda_1 = 1$ — free of charge, it’s a Markov matrix. The trace is $.9 + .8 = 1.7$, so $\lambda_2 = .7$. (Check with the determinant: $.72 - .02 = .7$.) Notice $|\lambda_2| \lt 1$, as promised.

Eigenvectors. For $\lambda_1 = 1$: the null space of $A - I = \begin{bmatrix} -.1 & .2 \\ .1 & -.2 \end{bmatrix}$ is spanned by $\mathbf{x}_1 = \begin{bmatrix} 2 \\ 1 \end{bmatrix}$ — positive, as the theory says. For $\lambda_2 = .7$: subtract $.7$ from the diagonal to get $\begin{bmatrix} .2 & .2 \\ .1 & .1 \end{bmatrix}$ — certainly singular, so the calculation checks — with null space $\mathbf{x}_2 = \begin{bmatrix} -1 \\ 1 \end{bmatrix}$.

We can jump to infinity right now. The steady state is a multiple of $(2, 1)$, and the multiple is decided by the thousand people: the components must add to 1000, so the populations approach $\left(\tfrac{2000}{3}, \tfrac{1000}{3}\right)$ — two thirds of everyone in California, one third in Massachusetts, forever.

For finite times, write out the full solution and match $u_0$:

$$u_k = c_1 (1)^k \begin{bmatrix} 2 \\ 1 \end{bmatrix} + c_2 (.7)^k \begin{bmatrix} -1 \\ 1 \end{bmatrix}, \qquad u_0 = \begin{bmatrix} 0 \\ 1000 \end{bmatrix} \;\Rightarrow\; c_1 = \frac{1000}{3},\; c_2 = \frac{2000}{3}$$

Check $k = 0$: $\tfrac{2000}{3} - \tfrac{2000}{3} = 0$ and $\tfrac{1000}{3} + \tfrac{2000}{3} = 1000$. The $(.7)^k$ term is the part that’s disappearing; what’s left is the steady state.

One comment for other courses: many applications (you’ll meet Markov matrices in electrical engineering) prefer row vectors, multiplying vector times matrix from the left. That uses the transpose of our matrix, so in other textbooks you’ll see rows adding to one instead of columns. Same theory, transposed conventions.

Projection onto an orthonormal basis

Now the bridge to Fourier. Suppose $\mathbf{q}_1, \ldots, \mathbf{q}_n$ is an orthonormal basis for $\mathbb{R}^n$. Any vector $\mathbf{v}$ can be expanded in the basis:

$$\mathbf{v} = x_1 \mathbf{q}_1 + x_2 \mathbf{q}_2 + \cdots + x_n \mathbf{q}_n$$

What are the amounts $x_1, x_2, \ldots$? We could grind through the normal equations, but orthonormality gives the answer instantly. To get $x_1$, take the inner product of the whole equation with $\mathbf{q}_1$. Every term $\mathbf{q}_1^T \mathbf{q}_i$ with $i \neq 1$ is zero; the term $\mathbf{q}_1^T \mathbf{q}_1$ is one. A bunch of zeros and a single survivor:

$$\mathbf{q}_1^T \mathbf{v} = x_1$$

In matrix language the expansion says $Q\mathbf{x} = \mathbf{v}$, so $\mathbf{x} = Q^{-1}\mathbf{v}$ — and the whole point of the letter $Q$ is that no work is needed to invert it: $Q^{-1} = Q^T$. The first component of $\mathbf{x} = Q^T\mathbf{v}$ is the first row of $Q^T$ times $\mathbf{v}$, which is exactly $\mathbf{q}_1^T \mathbf{v}$. Same conclusion, seen twice.

Fourier series: an orthonormal basis for functions

Joseph Fourier realized: I could work in function space. Instead of a vector $\mathbf{v}$, a function $f(x)$; instead of orthogonal vectors $\mathbf{q}_1, \mathbf{q}_2, \ldots$, orthogonal functions — and infinitely many, because the space is infinite-dimensional:

$$f(x) = a_0 + a_1 \cos x + b_1 \sin x + a_2 \cos 2x + b_2 \sin 2x + \cdots$$

This is the moment the course leaves finite-dimensional vector spaces. The vectors are now functions; the basis is $1, \cos x, \sin x, \cos 2x, \sin 2x, \ldots$ And the reason Fourier series is a success is that this basis is orthogonal. But orthogonal in what sense? We know $\mathbf{v}^T\mathbf{w} = v_1 w_1 + \cdots + v_n w_n$ for vectors. A function doesn’t have $n$ components — it has a whole continuum of values.

Check one orthogonality: $\int_0^{2\pi} \sin x \cos x \, dx = \tfrac{1}{2}\sin^2 x \big|_0^{2\pi} = 0$. The same holds — with some trig identities to help out — for every other pair in the list. So we have an orthogonal infinite basis for function space, and all we want to do is expand a function in that basis.

How much $\cos x$ is in $f$? Exactly as in the vector case: take the inner product of everything with $\cos x$ — in ordinary calculus words, multiply by $\cos x$ and integrate. On the right, a whole lot of zeros; the only term that survives is the $a_1$ term:

$$\int_0^{2\pi} f(x) \cos x \, dx = a_1 \int_0^{2\pi} \cos^2 x \, dx = a_1 \pi \qquad\Longrightarrow\qquad a_1 = \frac{1}{\pi} \int_0^{2\pi} f(x)\cos x \, dx$$

The $\cos^2$ integral is not zero, of course — it’s the squared length of the basis function — and an easy calculation gives $\pi$. That is Euler’s famous formula (or maybe Fourier found it) for the coefficients of a Fourier series, and you can now see it for what it is: exactly an expansion in an orthonormal basis. (The constant term is even easier: $a_0$ comes out to be the average value of $f$.)

Problems

Everything here runs on the lecture’s two engines: the eigenvalue 1 of a Markov matrix, and coefficients by inner products.

Problem 24.1 Steady state of a Markov chain

Rain follows sun: if today is sunny, tomorrow is sunny with probability $.8$ and rainy with probability $.2$; if today is rainy, tomorrow is sunny with probability $.4$ and rainy with probability $.6$. Write the Markov matrix, find both eigenvalues, and find the long-run fraction of sunny days.

Show solution

With $u_k = (\text{sunny}, \text{rainy})$ probabilities,

$$A = \begin{bmatrix} .8 & .4 \\ .2 & .6 \end{bmatrix}$$

(columns add to one). One eigenvalue is $\lambda_1 = 1$ automatically; the trace is $1.4$, so $\lambda_2 = .4$.

Steady state: null space of $A - I = \begin{bmatrix} -.2 & .4 \\ .2 & -.4 \end{bmatrix}$, which is spanned by $\begin{bmatrix} 2 \\ 1 \end{bmatrix}$. Scale so the components add to $1$: the steady state is $\left(\tfrac{2}{3}, \tfrac{1}{3}\right)$. In the long run, two thirds of days are sunny — regardless of today’s weather, since the $(.4)^k$ term dies.

Problem 24.2 Powers of a Markov matrix

For the lecture’s matrix $A = \begin{bmatrix} .9 & .2 \\ .1 & .8 \end{bmatrix}$, with eigenvalues $1, .7$ and eigenvectors $(2,1)$ and $(-1,1)$, start from $u_0 = \begin{bmatrix} 300 \\ 0 \end{bmatrix}$. Find $u_k$ exactly, and give the populations at $k = \infty$.

Show solution

Expand $u_0 = c_1 \begin{bmatrix} 2 \\ 1 \end{bmatrix} + c_2 \begin{bmatrix} -1 \\ 1 \end{bmatrix}$: the components give $2c_1 - c_2 = 300$ and $c_1 + c_2 = 0$, so $c_2 = -c_1$ and $3c_1 = 300$: $c_1 = 100$, $c_2 = -100$.

$$u_k = 100 \begin{bmatrix} 2 \\ 1 \end{bmatrix} - 100\,(.7)^k \begin{bmatrix} -1 \\ 1 \end{bmatrix} = \begin{bmatrix} 200 + 100(.7)^k \\ 100 - 100(.7)^k \end{bmatrix}$$

Check $k=0$: $(300, 0)$. ✓ The total is $300$ at every step (conserved). As $k \to \infty$, the $(.7)^k$ term vanishes: $u_\infty = (200, 100)$ — the multiple of the eigenvector $(2,1)$ that accounts for all $300$ people.

Problem 24.3 Columns add to zero, so singular

Suppose $M$ is any $n \times n$ matrix in which every column adds to zero. Without using determinants, prove that $M$ is singular, and explain where the eigenvector for the eigenvalue $0$ of $M$ lives.

Show solution

Add all the rows of $M$: since each column sums to zero, the sum is the zero row. So the combination $1 \cdot (\text{row}_1) + \cdots + 1 \cdot (\text{row}_n) = \mathbf{0}$ — the rows are linearly dependent, hence $M$ is singular. Equivalently, $(1, 1, \ldots, 1)$ is in the left null space: $M^T$ has $(1,\ldots,1)$ as an eigenvector with eigenvalue $0$.

Since $M$ is singular, its own null space is nonzero: some combination of the columns gives the zero column, and that combination is an eigenvector of $M$ with eigenvalue $0$. It lives in $N(M)$, which is generally a different space from $N(M^T)$ — $M$ and $M^T$ share eigenvalues, not eigenvectors. (Applied to $M = A - I$ with $A$ Markov, this eigenvector is the steady state.)

Problem 24.4 Coefficients from orthonormality

Let $\mathbf{q}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ and $\mathbf{q}_2 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \end{bmatrix}$, an orthonormal basis for $\mathbb{R}^2$. Expand $\mathbf{v} = \begin{bmatrix} 5 \\ 1 \end{bmatrix}$ as $x_1 \mathbf{q}_1 + x_2 \mathbf{q}_2$ using inner products only — no elimination.

Show solution

Orthonormality gives each coefficient directly:

$$x_1 = \mathbf{q}_1^T \mathbf{v} = \frac{5 + 1}{\sqrt{2}} = \frac{6}{\sqrt{2}} = 3\sqrt{2}, \qquad x_2 = \mathbf{q}_2^T \mathbf{v} = \frac{5 - 1}{\sqrt{2}} = 2\sqrt{2}$$

Check: $3\sqrt{2} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix} + 2\sqrt{2} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 3 \\ 3 \end{bmatrix} + \begin{bmatrix} 2 \\ -2 \end{bmatrix} = \begin{bmatrix} 5 \\ 1 \end{bmatrix}$. ✓ This is $\mathbf{x} = Q^T\mathbf{v}$ in action.

Problem 24.5 A Fourier coefficient

Using the inner product $\int_0^{2\pi} f(x) g(x)\, dx$, find the coefficient $b_1$ of $\sin x$ in the Fourier series of a $2\pi$-periodic function $f$, following the lecture’s method. Then compute $b_1$ for the square wave $f(x) = 1$ on $(0, \pi)$ and $f(x) = -1$ on $(\pi, 2\pi)$.

Show solution

Multiply the series $f(x) = a_0 + a_1 \cos x + b_1 \sin x + \cdots$ by $\sin x$ and integrate over $[0, 2\pi]$. By orthogonality every term on the right integrates to zero except the $b_1$ term:

$$\int_0^{2\pi} f(x) \sin x \, dx = b_1 \int_0^{2\pi} \sin^2 x \, dx = b_1 \pi \quad\Longrightarrow\quad b_1 = \frac{1}{\pi} \int_0^{2\pi} f(x) \sin x \, dx$$

For the square wave:

$$b_1 = \frac{1}{\pi}\left( \int_0^{\pi} \sin x \, dx - \int_{\pi}^{2\pi} \sin x \, dx \right) = \frac{1}{\pi}\left( [-\cos x]_0^{\pi} - [-\cos x]_{\pi}^{2\pi} \right) = \frac{1}{\pi}(2 - (-2)) = \frac{4}{\pi}$$

So the square wave contains $\frac{4}{\pi} \sin x$ as its first harmonic.