Homework 10: Eigenvalues and Eigenvectors

due Thursday, June 18th, 2026 at 11:59PM Ann Arbor Time

Write your solutions to the following problems either by writing them on a piece of paper or on a tablet and scanning your answers as a PDF. Note that you are not allowed to use LaTeX, Google Docs, or any other digital document creation software to type your answers. Homeworks are due to Gradescope by 11:59PM on the due date. See the syllabus for details on the slip day policy.

Homework will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain and justify your conclusions, using sound reasoning. Your goal should be to convince the reader of your assertions. If a question does not require explanation, it will be explicitly stated.

Before proceeding, make sure you’re familiar with the collaboration policy.

Problems

Problem 1: Homework 9 Solutions Review
Problem 2: Rank One Projection Matrices
Problem 3: Algebraic and Geometric Multiplicities
Problem 4: Diagonalization
Problem 5: Adjacency Matrices
Problem 6: Regularization
Problem 7: PageRank

Total Points: 10 + 10 + 20 + 14 + 16 + 24 + 12 = 106

Note: Repeatedly, you’ll be asked to find eigenvalues and eigenvectors. As usual, you’re expected to show all of your work. But, you’re encouraged to verify your answers by using np.linalg.eig in Python, as is demonstrated in Chapter 9.1. (Resist the urge to use ChatGPT...)

Problem 1: Homework 9 Solutions Review (10 pts)

Review the solutions to Homework 9. Pick two problem parts (for example, Problem 2a and Problem 5c) from Homework 9 in which your solutions have the most room for improvement, i.e. where they have unsound reasoning, could be significantly more efficient or clearer, etc. Include a screenshot of your solution to each problem part, and in a few sentences, explain what was deficient and how it could be fixed.

Alternatively, if you think one of your solutions is significantly better than the posted one, copy it here and explain why you think it is better. If you didn’t do Homework 9, choose two problem parts from it that look challenging to you, and in a few sentences, explain the key ideas behind their solutions in your own words.

Problem 2: Rank One Projection Matrices (10 pts)

Consider the unit vector $\vec u = \begin{bmatrix} 1/6 \\ 1/6 \\ 3/6 \\ 5/6 \end{bmatrix}$ , and the corresponding rank one projection matrix $P = \vec u \vec u^T$ .

(3 pts) Show that $\vec u$ is an eigenvector of $$P$$ . What is its corresponding eigenvalue?

(3 pts) Show that if $\vec v$ is orthogonal to $\vec u$ , then $\vec v$ is an eigenvector of $$P$$ . What is its corresponding eigenvalue?

(4 pts) Find three different linearly independent eigenvectors of $$P$$ , all corresponding to the eigenvalue 0.

(In the terminology of Problem 4 and Chapter 5.2, these eigenvectors form a basis of the eigenspace of $$P$$ corresponding to eigenvalue 0.)

Problem 3: Algebraic and Geometric Multiplicities (20 pts)

For each matrix below:

Find its characteristic polynomial in factored form.
State all eigenvalues along with their algebraic multiplicities.
For each eigenvalue, find a basis for the eigenspace corresponding to that eigenvalue, and state its geometric multiplicity.

Some advice:

There are multiple examples of what you’re asked to do in Chapter 9.4.
Recall the trace and determinant tricks from Chapter 9.2, and the fact that the determinant of an upper triangular matrix is the product of the diagonal entries.
Work efficiently: this problem is quicker than it seems.

(4 pts) $A = \begin{bmatrix} 3 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 4 \end{bmatrix}$

(4 pts) $A = \begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}$

(4 pts) $A = \begin{bmatrix} 2 & 0 & 1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix}$

(4 pts) $A = \begin{bmatrix} 5 & 0 & 0 & 0 \\ 0 & 3 & 1 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 5 \end{bmatrix}$

(4 pts) $A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$

Problem 4: Diagonalization (14 pts)

Before proceeding, it’s wise to read Chapter 9.4.

(4 pts) In each statement, fill in the blanks and provide a brief justification. Each answer is more than just one word or number.

$$A$$ is diagonalizable if and only if it has ____ eigenvectors.
$$A$$ is diagonalizable if and only if the geometric multiplicity of each eigenvalue is ____.

(10 pts) For each matrix $$A$$ in Problem 3:

if it is diagonalizable, find matrices $$V$$ and $\Lambda$ such that $A = V \Lambda V^{-1}$ . (As we saw in Chapter 9.4, this matrix is constructed by placing the eigenvectors of $$A$$ as the columns of $$V$$ and the eigenvalues of $$A$$ as the diagonal entries of $\Lambda$ . You should have already done most of the work for this; this problem is just a matter of organizing your work.)
if not, explain why it is not diagonalizable.

Problem 5: Adjacency Matrices (16 pts)

Consider the matrix

A = \begin{bmatrix} 0.6 & 0.2 & 0.4 \\\\ 0.3 & 0.7 & 0.2 \\\\ 0.1 & 0.1 & 0.4 \end{bmatrix}

$$A$$ represents the adjacency matrix of a Markov chain with three states; see Chapter 9.3 for details.

(3 pts) Draw the corresponding state diagram for $$A$$ . Label the states 1, 2, and 3.

(4 pts) Diagonalize $$A$$ by finding matrices $$V$$ and $\Lambda$ such that $A = V \Lambda V^{-1}$ . Do this by hand, but then include a screenshot of numpy code that verifies that you found the correct $$V$$ and $\Lambda$ .

(3 pts) Compute $A^{10}$ using the diagonalization you found in part b). Hint: You should not have to multiply ten matrices by hand: only three. State what the three matrices are, and then you can use numpy to actually multiply them. Include a screenshot of any code you write and its output.

(3 pts) Let $\vec x_0 = \begin{bmatrix} 0.6 \\ 0.3 \\ 0.1 \end{bmatrix}$ be an initial state vector. Using numpy, compute $A^{10} \vec x_0$ . Include a screenshot of any code you write and its output.

(3 pts) As $k \to \infty$ , what does $A^k \vec x_0$ converge to, and why? Make sure your answer references the diagonalization you found in part b).

Problem 6: Regularization (24 pts)

Suppose we’d like to perform multiple linear regression using the $n \times (d+1)$ design matrix $$X$$ , observation vector $\vec y \in \mathbb{R}^n$ , and parameter vector $\vec w \in \mathbb{R}^{d+1}$ .

Instead of minimizing mean squared error to find $\vec w^{\ast}$ , suppose we’d like to minimize the following regularized objective function:

R_\text{ridge}(\vec w) = \lVert \vec y - X \vec w \rVert^2 + \lambda \lVert \vec w \rVert^2

where $\lambda \geq 0$ is a constant. The $+ \lambda \lVert \vec w \rVert^2$ term is called the regularization term.

The vector $\vec w_\text{ridge}^{\ast}$ that minimizes $R_\text{ridge}(\vec w)$ will be, in general, different than the vector $\vec w^{\ast}$ that minimizes mean squared error without the added $+ \lambda \lVert \vec w \rVert^2$ term, and will thus have a higher mean squared error on the training data.

But, it turns out that $\vec w_\text{ridge}^{\ast}$ may make better predictions on unseen test data, if we choose $\lambda$ carefully, by forcing the model to be simpler and less overfit to the training data. Let’s explore this idea in more depth.

(6 pts) Find $\nabla R_\text{ridge}(\vec w)$ , the gradient of $R_\text{ridge}(\vec w)$ .

Hint: Most of the steps involved were done in Chapter 8.2, but you’ll need to redo the work yourself and extend it slightly.

(3 pts) Find $\vec w_\text{ridge}^{\ast}$ , the vector that minimizes $R_\text{ridge}(\vec w)$ .

Hint: Your answer should be such that if $\lambda = 0$ , then $\vec w_\text{ridge}^{\ast}$ is the same as the vector $\vec w^{\ast}$ that minimizes mean squared error without the added $+ \lambda \lVert \vec w \rVert^2$ term.

One of the side benefits of adding this regularization term is that a unique solution for $\vec w_\text{ridge}^{\ast}$ exists for all $\lambda > 0$ , even if $$X$$ is not full rank. That’s a bold claim: let’s prove it.

(4 pts) Prove that all of the eigenvalues of $$X^TX$$ are non-negative. (This means that $$X^TX$$ is positive semidefinite.)

Hint: Suppose $\vec v_i$ is an eigenvector of $$X^TX$$ with eigenvalue $\lambda_i$ . From there, if you get stuck, take a look at this seemingly unrelated proof from Chapter 5.4 for inspiration.

(3 pts) Suppose $\vec v_i$ is an eigenvector of $$X^TX$$ with eigenvalue $\lambda_i$ . Show that $\vec v_i$ is also an eigenvector of $X^TX + \lambda I$ . What is its corresponding eigenvalue?

(3 pts) Putting parts c) and d) together, why is it guaranteed that $X^TX+ \lambda I$ is invertible for all $\lambda > 0$ , even if $$X$$ is not full rank? ( $X^TX + \lambda I$ is said to be positive definite for all $\lambda > 0$ .)

(5 pts) Now, let’s explore how adding the regularization term $\lambda \lVert \vec w \rVert^2$ to the objective function affects the shape of the loss surface.

Open the the supplemental Jupyter Notebook we’ve created for Homework 10, which can either be found here in the course GitHub repository or here on DataHub.

This problem is not autograded. Instead,

Read through the entire walkthrough, all the way through the end of Problem 6f).
In this PDF, include a screenshot of the diagram with a slider, showing that you’ve moved it all the way to the right, at $\lambda = 100000$ .
In this PDF, include answers to both of the following questions:

Why is it called ridge regression?
How does the inclusion of the $\lambda \lVert \vec w \rVert^2$ term change the convexity of the loss surface?

If you’d like to read more about regularization, and how we actually choose the value of $\lambda$ in practice, read more from EECS 398 here.

Problem 7: PageRank (12 pts)

This problem involves writing code and submitting it to the Gradescope autograder. The goal of this problem is to allow you to implement Google’s PageRank algorithm in code and think through some of its pitfalls and variants.

There are two ways to access the supplemental Jupyter Notebook:

Option 1: Set up a Jupyter Notebook environment locally, use git to clone our course repository, and open homeworks/hw10/hw10.ipynb. For instructions on how to do this, see the Tech Support page of the course website.
Option 2: Click here to open hw10.ipynb on DataHub. Before doing so, read the instructions on the Tech Support page on how to use the DataHub.

This problem is entirely autograded; to receive credit for Problem 7 of this homework, you’ll need to submit your completed notebook to the autograder on Gradescope. Your submission time for Homework 10 is the latter of your PDF and code submission times.