Lab 11: Adjacency Matrices and Diagonalization

due for completion at 11:59PM Ann Arbor Time on Wednesday, June 17th, 2026

Each lab worksheet will contain several activities, some of which will involve writing code and others that will involve writing math on paper. To receive credit for a lab, you must complete as many of the activities as you can in 2 hours and submit a PDF of your work to Gradescope. We will provide specific instructions on how to submit programming activities (e.g. submitting the notebook or including a screenshot of some output).

Feel free to work with others in the course, but you must submit individually.

Recap: Diagonalization (Chapter 9.4)

Since $$A$$ has two linearly independent eigenvectors, it is diagonalizable, meaning we can write

A = V \Lambda V^{-1} = \underbrace{\begin{bmatrix} 2 & 3 \\\\ -6 & 1 \end{bmatrix}}_{V} \underbrace{\begin{bmatrix} -3 & 0 \\\\ 0 & 7 \end{bmatrix}}_{\Lambda} \underbrace{\begin{bmatrix} 0.05 & -0.15 \\\\ 0.3 & 0.1 \end{bmatrix}}_{V^{-1}}

where $$V$$ is an invertible matrix whose columns are the eigenvectors of $$A$$ and $\Lambda$ is a diagonal matrix with the eigenvalues of $$A$$ on the diagonal.

The algebraic multiplicity of an eigenvalue, $\text{AM}(\lambda_i)$ , is the number of times it appears as a root of the characteristic polynomial.

p(\lambda) = (\lambda - \lambda_1)^{\text{AM}(\lambda_1)} (\lambda - \lambda_2)^{\text{AM}(\lambda_2)} \cdots (\lambda - \lambda_k)^{\text{AM}(\lambda_k)}

The geometric multiplicity of an eigenvalue, $\text{GM}(\lambda_i)$ , is the dimension of the eigenspace corresponding to $\lambda_i$ .

\text{GM}(\lambda_i) = \text{dim}(\text{nullsp}(A - \lambda_i I)) = \text{number of linearly independent eigenvectors corresponding to } \lambda_i

For any $\lambda_i$ , $1 \leq \text{GM}(\lambda_i) \leq \text{AM}(\lambda_i)$ .
$$A$$ is diagonalizable if and only if $\text{AM}(\lambda_i) = \text{GM}(\lambda_i)$ for all eigenvalues $\lambda_i$ . This ensures that $$A$$ ’s eigenvectors form a basis of $\mathbb{R}^n$ .
$A = \begin{bmatrix} 3 & -1 \\ 1 & 1 \end{bmatrix}$ has characteristic polynomial $p(\lambda) = (2 - \lambda)^2$ . The eigenvalue $\lambda = 2$ has algebraic multiplicity 2, but the corresponding eigenspace is only 1-dimensional:

\text{nullsp}(A - 2I) = \text{nullsp}\left(\begin{bmatrix} 1 & -1 \\\\ 1 & -1 \end{bmatrix}\right) = \text{span}\left(\begin{bmatrix} 1 \\\\ 1 \end{bmatrix}\right)

so, $\lambda = 2$ has geometric multiplicity 1. Since $\text{AM}(2) \neq \text{GM}(2)$ , $$A$$ is not diagonalizable.

$A = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 2 & 1 \\ -1 & 1 & 2 \end{bmatrix}$ has characteristic polynomial $p(\lambda) = (1 - \lambda)^2(3 - \lambda)$ , so $\lambda_1 = 1$ has $\text{AM}(\lambda_1) = 2$ and $\lambda_2 = 3$ has $\text{AM}(\lambda_2) = 1$ . The eigenspace for $\lambda_1 = 1$ is 2-dimensional,

\text{nullsp}(A - 1 I) = \text{nullsp}\left(\begin{bmatrix} 0 & 0 & 0 \\\\ -1 & 1 & 1 \\\\ -1 & 1 & 1 \end{bmatrix}\right) = \text{span}\left(\begin{bmatrix} 1 \\\\ 1 \\\\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\\\ 0 \\\\ 1 \end{bmatrix}\right)

so $\text{GM}(\lambda_1) = 2$ . Since $\text{AM}(\lambda_i) = \text{GM}(\lambda_i)$ for all eigenvalues $\lambda_i$ , $$A$$ is diagonalizable.

A = V \Lambda V^{-1} = \underbrace{\begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 1 & 1 \end{bmatrix}}_{V} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 3 \end{bmatrix}}_{\Lambda} \underbrace{\begin{bmatrix} 0.5 & 0.5 & -0.5 \\\\ 0.5 & -0.5 & 0.5 \\\\ -0.5 & 0.5 & 0.5 \end{bmatrix}}_{V^{-1}}

Diagonalizability is not the same as invertibility!

Activity 1: Rapid Fire

The goal here is to answer the problems quickly without working out the details.

Let $A = \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}$ . What are the eigenvalues of $$A$$ ? Is $$A$$ diagonalizable?

Hint: Use the fact that $$A$$ is an upper triangular matrix. What is $\det(A - \lambda I)$ ?

A $5 \times 5$ matrix has an eigenvalue of 0 with geometric multiplicity 2. What is its rank?

Activity 2: Fundamentals

Let $A = \begin{bmatrix} 3 & 2 & 0 \\ 2 & 3 & 0 \\ 0 & 0 & 5 \end{bmatrix}$ .

Find the characteristic polynomial of $$A$$ , and use it to find the eigenvalues of $$A$$ and their algebraic multiplicities.

Find a basis for the eigenspace corresponding to each eigenvalue.

This particular $$A$$ is diagonalizable. Diagonalize $$A$$ by finding a matrix $$V$$ and a diagonal matrix $\Lambda$ such that $A = V \Lambda V^{-1}$ .

Activity 3: Adjacency Matrices

Suppose that each night, a Wolverine moves between three classic Ann Arbor spots: the Diag, Zingerman’s, and the Big House.

From the Diag, $\frac{2}{3}$ of the time it stays at the Diag, $\frac{1}{6}$ of the time it walks to Zingerman’s, and $\frac{1}{6}$ of the time it walks to the Big House.
From the Big House, it always walks to Zingerman’s.
From Zingerman’s, it is equally likely to walk to the Diag or the Big House.

Draw a state diagram for this Markov chain. Make sure to clearly label the edges with their transition probabilities. (For help, see Chapter 9.3.)

Find the adjacency matrix, $$A$$ , of this Markov chain.

Show that the long-run distribution of the Wolverine’s locations is $\begin{bmatrix} p(\text{Diag}) \\ p(\text{Big House}) \\ p(\text{Zingerman’s}) \end{bmatrix} = \begin{bmatrix} 6/13 \\ 3/13 \\ 4/13 \end{bmatrix}$ . Hint: Do this by finding the eigenvector of $$A$$ corresponding to the eigenvalue 1. Since there are infinitely many such eigenvectors, find the one that satisfies the constraint that the components sum to 1.

Open a new Jupyter Notebook or interactive Python session in the Terminal. In it, run:

import numpy as np
A = np.array(...) # Replace with the adjacency matrix you found in b)
eigvals, eigvecs = np.linalg.eig(A)

Now, if you run eigvals, you should see

array([ 1.        ,  0.36037961, -0.69371294])

If you run eigvecs[:, 0] to access the eigenvector corresponding to the first eigenvalue in the array above, you should see

array([0.76822128, 0.38411064, 0.51214752])

This is not the eigenvector you found in the previous part. Why not? What did it return, and what expression can you run in code to find the exact answer you found in the previous part?

Run both of the following commands:

np.linalg.matrix_power(A, 20) @ np.array([[1/3], [1/3], [1/3]])
np.linalg.matrix_power(A, 21) @ np.array([[1/3], [1/3], [1/3]])

What do you see? Why?

Now, consider the adjacency matrix

B = \begin{bmatrix} 0 & 0 & 1/2 \\\\ 0 & 0 & 1/2 \\\\ 1 & 1 & 0 \end{bmatrix}

Using numpy, find the eigenvalues of $$B$$ . Then, run all of the following commands:

np.linalg.matrix_power(B, 20) @ np.array([[1/3], [1/3], [1/3]])
np.linalg.matrix_power(B, 21) @ np.array([[1/3], [1/3], [1/3]])
np.linalg.matrix_power(B, 22) @ np.array([[1/3], [1/3], [1/3]])
np.linalg.matrix_power(B, 23) @ np.array([[1/3], [1/3], [1/3]])

This Markov chain appears not to converge. Why not? Relate your answer to the discussion of “the dominant eigenvalue” in Chapter 9.3.

Activity 4: Symmetric Matrices

Suppose $$A$$ is a symmetric $n \times n$ matrix, meaning $$A = A^T$$ . Symmetric matrices have a special property, described by the spectral theorem: the eigenvectors corresponding to different eigenvalues are orthogonal. Below, we provide a proof of this fact.

1. Let $\vec v_i$ be an eigenvector of $$A$$ with eigenvalue $\lambda_i$ , so $A \vec v_i = \lambda_i \vec v_i$ .

2. Let $\vec v_j$ be an eigenvector of $$A$$ with eigenvalue $\lambda_j$ , where $\lambda_i \neq \lambda_j$ , so $A \vec v_j = \lambda_j \vec v_j$ .

3. The dot product of $\vec v_i$ and $A \vec v_j$ is $\vec v_i \cdot (A \vec v_j) = \vec v_i \cdot (\lambda_j \vec v_j) = \lambda_j (\vec v_i \cdot \vec v_j)$ .

4. But also, $\vec v_i \cdot (A \vec v_j) = \vec v_i^T A \vec v_j = \vec v_i^T A^T \vec v_j = (A \vec v_i)^T \vec v_j = \lambda_i \vec v_i^T \vec v_j = \lambda_i (\vec v_i \cdot \vec v_j)$ .

5. The final expressions in both cases are equal, so $\lambda_j (\vec v_i \cdot \vec v_j) = \lambda_i (\vec v_i \cdot \vec v_j)$ .

6. Equivalently, $(\lambda_j - \lambda_i) (\vec v_i \cdot \vec v_j) = 0$ . But since $\lambda_i \neq \lambda_j$ , we must have $\vec v_i \cdot \vec v_j = 0$ .

In which line did we use the fact that $$A$$ is symmetric? Select the line below, and then in that line, circle the specific part of the equation that uses the fact that $$A = A^T$$ .

1 2 3 4 5 6

The spectral theorem states that any symmetric $n \times n$ matrix $$A$$ can be diagonalized by an orthogonal matrix $$Q$$ through

A = Q \Lambda Q^T

Explain how this relates to the “regular” diagonalization $A = V \Lambda V^{-1}$ . Why does the equation above contain $$Q^T$$ instead of $Q^{-1}$ ?

Symmetric matrices play a big role in solving optimization problems in machine learning. You’ll get a taste of this in Homework 10, Problem 6, which discusses ridge regression and regularization, ideas that we use to make sure that our models are not overfitting to training data.

Here, we’ll prove a related fact: if $$A$$ is an $n \times n$ symmetric matrix and all of its eigenvalues are non-negative, then $$A$$ is positive semidefinite. A symmetric matrix $$A$$ is positive semidefinite if and only if $\boxed{\vec v^T A \vec v \geq 0}$ for all $\vec v \in \mathbb{R}^n$ . One interpretation: this means the quadratic form $f(\vec v) = \vec v^T A \vec v$ is always greater than or equal to 0, no matter what $\vec v$ is.

Let’s work through the proof step-by-step: we will do some of it for you, and you’ll complete the rest. (To be precise, we’re only proving one direction of the “if and only if” statement; the other direction is in Homework 10!) First, since $$A$$ is symmetric, the spectral theorem tells us that $$A$$ can be written as

A = Q \Lambda Q^T

where $$Q$$ is an orthogonal matrix and $\Lambda$ is a diagonal matrix with the eigenvalues of $$A$$ on the diagonal. This is the eigenvector decomposition of $$A$$ .

On top of that, suppose that all of $$A$$ ’s eigenvalues, $\lambda_1, \lambda_2, \ldots, \lambda_n$ , are non-negative.

Now, let $\vec v$ be some arbitrary vector (not necessarily an eigenvector of $$A$$ ) in $\mathbb{R}^n$ . Then, eventually we need to show that $\vec v^T A \vec v \geq 0$ , regardless of what $\vec v$ is. Let’s start by expanding $\vec v^T A \vec v$ using the fact that $A = Q \Lambda Q^T$ .

\vec v^T A \vec v = \vec v^T (Q \Lambda Q^T) \vec v = (\vec v^T Q) \Lambda (Q^T \vec v)

Suppose that $\vec y = Q^T \vec v$ . Then, $\vec y^T = (Q^T \vec v)^T = \vec v^T Q$ . This seems like an arbitrary maneuver, but it will be useful in a moment.

\begin{align*} \vec v^T A \vec v &= \vec y^T \Lambda \vec y =\begin{bmatrix} y_1 & y_2 & \ldots & y_n \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & \ldots & 0 \\\\ 0 & \lambda_2 & \ldots & 0 \\\\ \vdots & \vdots & \ddots & \vdots \\\\ 0 & 0 & \ldots & \lambda_n \end{bmatrix} \begin{bmatrix} y_1 \\\\ y_2 \\\\ \vdots \\\\ y_n \end{bmatrix} \end{align*}

Your job is to complete the rest of the proof. Show that if $$A$$ is an $n \times n$ symmetric matrix and all of its eigenvalues are non-negative, then $\vec v^T A \vec v \geq 0$ for all $\vec v \in \mathbb{R}^n$ .

Activity 5: More Practice (Optional)

Let $$A$$ be a $3 \times 3$ with:

eigenvalue $\lambda_1 = 3$ with eigenvector $\vec v_1 = \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix}$ .
eigenvalue $\lambda_2 = -2$ with the 2-dimensional eigenspace: $\text{span}\left(\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}\right)$ .

Find $$A$$ . Feel free to use numpy to find an inverse for you and verify your answer.

Let $$V$$ be the matrix whose columns are the eigenvectors of $$A$$ and $\Lambda$ be the diagonal matrix with the eigenvalues of $$A$$ on the diagonal. In terms of $$V$$ and $\Lambda$ , what is $A^{8}$ ?

Suppose $\vec x \in \mathbb{R}^3$ is some vector. As $k \to \infty$ , what does $A^k \vec x$ approach? Explain your answer in English.