Homework 6: Rank and Inverses

due Sunday, May 31st, 2026 at 11:59PM Ann Arbor Time

View as PDF ✏️

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

Total Points: 10 + 9 + 16 + 12 + 12 + 5 + 5 + 22 = 91

Problem 1: Homework 5 Solutions Review (10 pts)

Review the solutions to Homework 5. Pick two problem parts (for example, Problem 2a and Problem 4b) from Homework 5 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 5, 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-Nullity Practice (9 pts)

Recall from Chapter 5.4 that the rank-nullity theorem states that for any \(n \times d\) matrix \(A\),

$$ \text{rank}(A) + \text{dim}(\text{nullsp}(A)) = \underbrace{\text{number of columns in } A}_{d} $$

In each part, identify whether the statement is true or false, and explain why.

a)

(3 pts) There exists a \(4 \times 5\) matrix \(A\) with \(\text{rank}(A) = 4\) and \(\text{dim}(\text{colsp}(A)) = 3\).

b)

(3 pts) There exists a \(4 \times 5\) matrix \(B\) with \(\text{rank}(B) = 3\) and \(\text{dim}(\text{nullsp}(B)) = 2\).

c)

(3 pts) There exists a \(4 \times 5\) matrix \(C\) with \(\text{dim}(\text{nullsp}(C)) = 4\) and \(\text{dim}(\text{nullsp}(C^T)) = 1\).

Problem 3: Spaces (16 pts)

a)

(4 pts) Find a matrix \(A\) such that

$$ \text{nullsp}(A) = \text{span}\left(\left\{\begin{bmatrix} 2 \\\\ 1 \\\\ 0 \\\\ 1 \end{bmatrix}\right\}\right) $$

What is \(\text{rank}(A)\)?

b)

(4 pts) Find a matrix \(A\) such that

$$ \text{nullsp}(A) = \text{span}\left(\left\{\begin{bmatrix} 2 \\\\ 2 \\\\ 1 \\\\ 0 \end{bmatrix}, \begin{bmatrix} 3 \\\\ 1 \\\\ 0 \\\\ 1 \end{bmatrix}\right\}\right) $$

What is \(\text{rank}(A)\)?

c)

(4 pts) Find a matrix \(A\) such that

$$ \begin{bmatrix} 1 \\\\ 1 \\\\ 5 \end{bmatrix} \in \text{colsp}(A), \quad \begin{bmatrix} 0 \\\\ 3 \\\\ 1 \end{bmatrix} \in \text{colsp}(A), \quad \begin{bmatrix} 1 \\\\ 1 \\\\ 2 \end{bmatrix} \in \text{nullsp}(A) $$

What is \(\text{rank}(A)\)?

d)

(4 pts) Let \(\vec u = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix}\) and \(\vec v = \begin{bmatrix} 8 \\ -2 \\ 3 \end{bmatrix}\). Explain why there does not exist a matrix \(A\) such that

$$ \vec u \in \text{colsp}(A), \quad \vec v \in \text{nullsp}(A^T) $$

and propose one change we could make to \(\vec v\) that would allow such an \(A\) to exist.

Hint: In the Orthogonal Complements example in Chapter 5.4, and in this video, we discuss a fact related to this question. If you want to make a claim about the required relationship between \(\vec u\) and \(\vec v\), you need to re-prove it here. This shouldn’t take too many lines of work.

Problem 4: Numbers of Solutions (12 pts)

Recall that if \(A\) is an \(n \times d\) matrix, \(\vec x \in \mathbb{R}^d\), and \(\vec b \in \mathbb{R}^n\), then

$$ A \vec x = \vec b $$

is a system of \(n\) equations in \(d\) unknowns, where the unknowns are the components of \(\vec x\), i.e. \(x_1\), \(x_2\), \(\ldots\), \(x_d\). Solving this system is equivalent to writing \(\vec b\) as a linear combination of the columns of \(A\).

In each part, do two things:

  1. Construct a matrix \(A\) for which the number of solutions (that is, number of valid \(\vec x\)’s) to the system \(A \vec x = \vec b\) is the number provided.

  2. Determine whether the function \(f(\vec x) = A \vec x\) is one-to-one, onto, both, or neither. (See Chapter 6.2 for a refresher on the definitions.)

The first part has been done for you as an example.

a)

\(0\) or \(1\), depending on \(\vec b\)

b)

(4 pts) \(\infty\), no matter what \(\vec b\) is

c)

(4 pts) \(0\) or \(\infty\), depending on what \(\vec b\) is

d)

(4 pts) \(1\), no matter what \(\vec b\) is

Problem 5: Projecting onto a Single Vector (12 pts)

In Homework 6, Problem 3, you found that the \(2 \times 2\) matrix \(P\) that projects \(\vec u \in \mathbb{R}^2\) onto the unit vector \(\vec v \in \mathbb{R}^2\) was

$$ P = \begin{bmatrix} v_1^2 & v_1v_2 \\\\ v_1v_2 & v_2^2 \end{bmatrix} $$
a)

(6 pts) Find:

  1. \(\text{rank}(P)\)

  2. A basis for \(\text{colsp}(P)\)

  3. A basis for \(\text{nullsp}(P)\)

  4. A basis for \(\text{colsp}(P^T)\)

b)

(3 pts) Explain why \(P\) is not invertible, and then explain why the transformation \(f(\vec u) = P \vec u\) can’t be reversed.

c)

(3 pts) As mentioned in Homework 6, Problem 3, \(P\) is an idempotent matrix, meaning that

$$ P^2 = P $$

In general, if \(P^2 = P\) and \(P\) is invertible, what must \(P\) be?

Hint: Multiply both sides of \(P^2 = P\) by \(P^{-1}\).

Problem 6: Invertibility of \(XX^T\) (5 pts)

In Chapter 5.4, and in this video, we proved that \(\text{rank}(X) = \text{rank}(X^TX)\).

Here, we’ll ask you to prove something similar involving \(XX^T\). Note that \(X^TX\) is a matrix containing the dot products of all pairs of \(X\)’s columns, while \(XX^T\) is a matrix containing the dot products of all pairs of \(X\)’s rows. (This has fact had something to do with Homework 6, Problem 4!)

Suppose \(X\) is an \(n \times d\) matrix, and \(XX^T\) is invertible. Find and explain all inequalities that must be true between \(n\), \(d\), and \(r = \text{rank}(X)\).

Problem 7: Trickster (5 pts)

Find a matrix \(A\) that is not equal to the identity matrix, but where \(A^6 = I\).

Once you think of your answer, you should explain how you found it, and should use Python to verify that \(A^6 = I\) holds. Include a screenshot of your Python code.

Hint: This problem has a trick to it, and to think of it, I’d suggest reading the Rotations and Orthogonal Matrices section of Chapter 6.2.

Problem 8: Sherman-Morrison Inverse (22 pts)

In EECS 280 or EECS 281, you may have learned about memoization, which involves storing results of an earlier calculation to help speed up future calculations. This problem involves something similar.

Suppose we have an \(n \times n\) matrix \(A\) whose inverse, \(A^{-1}\), we already know. Remember that finding inverses in general is a difficult task, so once we’ve found one, we’d like to avoid having to invert again.

And, suppose that we need to know the inverse of

$$ B = A + \vec u \vec v^T $$

which is the sum of \(A\) and a rank 1 matrix created by taking the “outer product” of \(\vec u, \vec v \in \mathbb{R}^n\) (as discussed in Chapter 5.3). Think of \(B\) as a small update to \(A\).

The Sherman-Morrison formula states that

$$ B^{-1} = (A + \vec u \vec v^T)^{-1} = A^{-1} - \frac{A^{-1} \vec u \vec v^T A^{-1}}{1 + \vec v^T A^{-1} \vec u} $$

The formula allows us to find the inverse of \(A + \vec u \vec v^T\) just by knowing \(\vec u\), \(\vec v\), and \(A^{-1}\), meaning we don’t need to recompute the inverse!

a)

(3 pts) To start, we’ll consider a simpler case of the Sherman-Morrison formula, where \(A = I\), the identity matrix. Then, since \(I = I^{-1}\), the matrix we’re inverting is

$$ B = A + \vec u \vec v^T $$

and its inverse is

$$ B^{-1} = (I + \vec u \vec v^T)^{-1} = I - \frac{\vec u \vec v^T}{1 + \vec v^T \vec u} $$

\(B\) is invertible, except when the denominator of the fraction above is 0, i.e. \(1 + \vec v^T \vec u = 0\).

When \(1 + \vec v^T \vec u = 0\), what is true about \(B\)?

Hint: Evaluate \(B \vec u\). What does the result tell you about \(\text{nullsp}(B)\)?

b)

(4 pts) Prove that as long as \(1 + \vec v^T \vec u \neq 0\), that

$$ (I + \vec u \vec v^T) \left( I - \frac{\vec u \vec v^T}{1 + \vec v^T \vec u} \right) = I $$

(Yes, this involves a fair bit of algebra.)

c)

(8 pts) Now, let’s return to the full-fledged Sherman-Morrison formula, where

$$ B = A + \vec u \vec v^T, \qquad B^{-1} = (A + \vec u \vec v^T)^{-1} = A^{-1} - \frac{A^{-1} \vec u \vec v^T A^{-1}}{1 + \vec v^T A^{-1} \vec u} $$

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

There, you’re asked to implement the Sherman-Morrison formula, and run some experiments to quantify how much quicker using the formula is than computing the inverse of \(B\) from scratch.

This problem is not autograded. Rather, in your submission to this part, include screenshots of your implementations of functions generate_random_data, invert_B_directly,

invert_B_with_sherman_morrison, run_one_experiment, and many_experiments_mean_sd, along with their outputs on the provided examples.

d)

(4 pts) Include screenshots of the code you used to call many_experiments_mean_sd for the values provided in the question, the outputs of the print statements you were asked to add, and the plotly line chart you were asked to create.

e)

(3 pts) Answer the question posed at the end of the supplemental Jupyter Notebook. (This shouldn’t be a screenshot; just write your answer in this PDF the same way you answered Problems 1-7.)

If you’re curious, look into Low-Rank Adaptions (LoRA), a relatively recent development in large language model research! The general idea is the same as we’ve worked with here.