This page is meant to give you quick access to problems and their solutions. Refer to the original exam PDF, linked above, for test-taking instructions and formatting. Note that we’ve kept the problem text identical, which is why you may see things like “write your answer in the box below” despite there not being a box on this page.
Suppose \(k\) is a real number. Let
In each part, you are provided with information about \(A\). Your job is to find the value of \(k\) that satisfies the given condition. Show your work in the space provided, and write your final answer in the bottom-right corner of the box. Your answers should be numbers with no variables.
4 pts \(\text{rank}(A) = 1\)
If \(\text{rank}(A) = 1\), then \(A\) is not invertible, which means \(\text{det}(A) = 0\). So,
4 pts \(\text{det}(A) = 2\)
The determinant of a \(2 \times 2\) matrix \(\begin{bmatrix} a & b \\ c & d \end{bmatrix}\) is \(ad - bc\). So,
We’re told that \(\det(A) = 2\), so
4 pts \(A^{-1} = \begin{bmatrix} 1 & -1/2 \\ -1 & 3/4 \end{bmatrix}\)
The inverse of a \(2 \times 2\) matrix \(\begin{bmatrix} a & b \\ c & d \end{bmatrix}\) is \(\frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\). So,
Since we’re told that
we can match entries. For example, using the bottom-right entry,
Suppose \(A\) is a matrix such that \(A \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 6 \\ 0 \\ 1 \end{bmatrix}\) and \(\left\lbrace \begin{bmatrix} 1 \\ 4 \\ -2 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0\end{bmatrix} \right\rbrace\) is a basis for \(\text{nullsp}(A)\).
Find one possible matrix \(A\). Show your work, and \(\boxed{\text{circle}}\) your final answer, which should be a matrix with no variables.
Let the columns of \(A\) be \(\vec c_1, \vec c_2, \vec c_3, \vec c_4\). Since
we know that the first column of \(A\) must be \(\begin{bmatrix} 6 \\ 0 \\ 1 \end{bmatrix}\).
Now, let’s use the information given about the null space to find the other columns of \(A\). Since
we have
Also, since
we have
Substituting \(\vec c_3 = -\vec c_2\) gives
So,
Finally, \(\text{dim}(\text{nullsp}(A)) = 2\) and \(A\) has 4 columns, so by rank-nullity,
So we should choose \(\vec c_4\) to be linearly independent from \(\vec c_1\). One easy choice is
This gives one possible matrix.
Suppose \(A\) and \(B\) are both non-zero \(6 \times 6\) matrices, such that \(\text{rank}(A) = 4\) and that every column of \(B\) is in \(\text{nullsp}(A)\).
3 pts Fill in the blanks: The third __(i)__ of \(A\) is __(ii)__ to the fourth __(iii)__ of \(B\).
Every column of \(B\) is in \(\text{nullsp}(A)\). From Chapter 5.4 in the notes, the row space of \(A\) and the null space of \(A\) are orthogonal complements. That means every row of \(A\) is orthogonal to every vector in \(\text{nullsp}(A)\), and hence orthogonal to every column of \(B\).
So, the third row of \(A\) is orthogonal to the fourth column of \(B\).
4 pts Select all possible values of \(\text{rank}(AB)\).
Let \(\vec b_1, \vec b_2, \ldots, \vec b_6\) be the columns of \(B\). Since every column of \(B\) is in \(\text{nullsp}(A)\), we have
for every \(j\). But the \(j\)th column of \(AB\) is exactly \(A \vec b_j\), so every column of \(AB\) is \(\vec 0\).
Therefore,
4 pts Select all possible values of \(\text{rank}(B)\).
Since \(A\) is \(6 \times 6\) with rank 4, the rank-nullity theorem gives
Every column of \(B\) lies in \(\text{nullsp}(A)\), so
Therefore,
Also, \(B\) is non-zero, so \(\text{rank}(B) \neq 0\).
So the only possible values are 1 and 2.
Both are achievable: all columns of \(B\) could be multiples of one non-zero vector in \(\text{nullsp}(A)\), or they could span all of \(\text{nullsp}(A)\) (which is a 2-dimensional subspace of \(\mathbb{R}^6\), since \(\text{rank}(A)=4\)).
Suppose \(X\) is some \(3 \times d\) matrix, for some integer \(d\). Let
5 pts Which of the following could be the projection of \(\vec y\) onto \(\text{colsp}(X)\)?
Select an answer, then briefly justify your answer in the space provided using properties of projections. Correct answers without justification may not receive full credit.
\(\begin{bmatrix} 6 \\ -7 \\ 3 \end{bmatrix}\)
If \(\vec p\) is the projection of \(\vec y\) onto \(\text{colsp}(X)\), then the error
must be orthogonal to all vectors in \(\text{colsp}(X)\), and hence orthogonal to \(\vec p\) itself.
For the third option, \(\vec p = \begin{bmatrix} 6 \\ -7 \\ 4 \end{bmatrix}\), we have
The dot product of \(\vec p\) and \(\vec y - \vec p\) is
So \(\vec p = \begin{bmatrix} 6 \\ -7 \\ 4 \end{bmatrix}\) could be the projection of \(\vec y\) onto \(\text{colsp}(X)\). If you repeat this calculation for the other three options, you’ll find that \(\vec p\) and \(\vec y - \vec p\) are not orthogonal.
In each of the remaining parts, identify whether the statement is True or False and justify your answer in the space provided. Correct answers without justification may not receive full credit.
4 pts If the projection of \(\vec y\) onto \(\text{colsp}(X)\) is \(\vec y\) itself, then \(\text{rank}(X)\) must be 3.
This is false. If the projection of \(\vec y\) onto \(\text{colsp}(X)\) is \(\vec y\) itself, that only tells us that \(\vec y \in \text{colsp}(X)\).
But \(\text{colsp}(X)\) could still be a 1-dimensional or 2-dimensional subspace of \(\mathbb{R}^3\) that happens to contain \(\vec y\). For example, if \(\text{colsp}(X) = \text{span}\left(\left\lbrace \vec y \right\rbrace\right)\), then the projection of \(\vec y\) is still \(\vec y\), but \(\text{rank}(X)=1\), not 3.
4 pts If \(\text{rank}(X) = 3\), then the projection of \(\vec y\) onto \(\text{colsp}(X)\) must be \(\vec y\) itself.
This is true. If \(\text{rank}(X)=3\) and \(X\) is a \(3 \times d\) matrix, then \(\text{colsp}(X)\) is a 3-dimensional subspace of \(\mathbb{R}^3\). The only 3-dimensional subspace of \(\mathbb{R}^3\) is all of \(\mathbb{R}^3\).
But, this means every vector in \(\mathbb{R}^3\), including \(\vec y\), is in \(\text{colsp}(X)\). Therefore, the projection of \(\vec y\) onto \(\text{colsp}(X)\) is just \(\vec y\) itself.
Let
5 pts Recall, a CR decomposition of an \(n \times d\) matrix \(A\) is a product \(A = CR\), where \(C\) is an \(n \times r\) matrix with linearly independent columns and \(R\) is an \(r \times d\) matrix with linearly independent rows, and \(r = \text{rank}(A)\).
Provide a CR decomposition of \(A\). Your answers should be matrices with no variables.
\(C = \_\_\_\_\_\_, \quad R = \_\_\_\_\_\_\)
The columns of \(A\) are
Reading left-to-right, columns 1, 2, and 4 are linearly independent, so we place them in \(C\):
Now we need to express each column of \(A\) as a linear combination of the columns of \(C\):
The coefficients in each linear combination are the entries in the corresponding column of \(R\). So,
Thus, one CR decomposition is
3 pts Find \(\text{dim}(\text{nullsp}(A^T))\). Give your answer as an integer with no variables.
\(\text{dim}(\text{nullsp}(A^T)) = \_\_\_\_\_\_\)
The matrix \(A\) has 3 rows and rank 3. Applying rank-nullity to \(A^T\), we get
Since \(\text{rank}(A^T)=\text{rank}(A)=3\),
This means that \(A^T\)’s null space is \(\left\lbrace \vec 0 \right\rbrace\).
(5 pts) Suppose we apply the Gram-Schmidt process to the rows of \(A\), and place the resulting orthonormal vectors into the rows of a new matrix, \(Q\).
Let \(P\) be the matrix that projects vectors in \(\mathbb{R}^5\) onto \(\text{colsp}(Q^T)\) (the row space of \(Q\)). In other words, if \(\vec y \in \mathbb{R}^5\), then \(P\vec y\) is the projection of \(\vec y\) onto \(\text{colsp}(Q^T)\).
Find an expression for \(P\) in terms of \(Q\) and \(Q^T\). Show your work, and \(\boxed{\text{circle}}\) your final answer, which should be an expression in terms of \(Q\) and \(Q^T\). Answers that aren’t fully simplified will not be given credit.
In general, the projection matrix onto \(\text{colsp}(X)\), where \(X\) is any matrix with linearly independent columns, is
Here, we want to project onto \(\text{colsp}(Q^T)\), so we should use \(X = Q^T\):
But, since \(Q\)’s rows are orthonormal, \(QQ^T = I\). This is because \(QQ^T\) is a matrix containing the dot products of the rows of \(Q\) with each other (the same way \(Q^TQ\) is a matrix containing the dot products of the columns of \(Q\) with each other). Since the rows of \(Q\) are orthonormal, the dot products are all 0 except for the diagonal, which is 1.
So,
Suppose we’d like to fit a multiple linear regression model without an intercept term to predict the number of fans in attendance at a Michigan football home game given various features.
For each row in the dataset, the corresponding feature vector is \(\vec x_i = \begin{bmatrix} \text{tempF}_i \\ \text{tempC}_i \\ \text{night}_i \\ \text{day}_i \end{bmatrix}\), where:
\(\text{tempF}_i\) is the temperature, in degrees Fahrenheit, at kickoff for game \(i\)
\(\text{tempC}_i\) is the temperature, in degrees Celsius, at kickoff for game \(i\)
\(\text{night}_i\) is 1 if game \(i\) is a night game and 0 otherwise
\(\text{day}_i\) is 0 if game \(i\) is a night game and 1 otherwise
Important: Note that
So, our model is of the form
We find optimal model parameters, \(\vec w^{\ast} = \begin{bmatrix} w_1^{\ast} \\ w_2^{\ast} \\ w_3^{\ast} \\ w_4^{\ast} \end{bmatrix}\), by solving the normal equation.
4 pts The first two rows of the dataset have the following information:
Game 1: 77 degrees Fahrenheit, 25 degrees Celsius, not night game, 102,111 fans
Game 2: 59 degrees Fahrenheit, 15 degrees Celsius, night game, 101,982 fans
Write the first two rows of the design matrix, \(X\). Your answer should be a matrix with two rows and no variables.
\(X = \_\_\_\_\_\_\)
Each row of the design matrix is just the feature vector for that game:
So,
Therefore, the first two rows of \(X\) are
Recall, our model is of the form
where \(\text{tempC}_i = \frac{5}{9} (\text{tempF}_i - 32)\).
4 pts Suppose \(\vec w’\) is one solution to the normal equation for this model. Which option describes the complete set of solutions to the normal equation?
| \(\left \lbrace \vec w’ + t\begin{bmatrix} 1 \\ -9/5 \\ 32 \\ -32 \end{bmatrix}, t \in \mathbb{R} \right\rbrace\) | \(\left \lbrace \vec w’ + t\begin{bmatrix} 1 \\ -9/5 \\ -32 \\ -32 \end{bmatrix}, t \in \mathbb{R} \right\rbrace\) |
|---|---|
| \(\left \lbrace \vec w’ + t\begin{bmatrix} 1 \\ 9/5 \\ 32 \\ -32 \end{bmatrix}, t \in \mathbb{R} \right\rbrace\) | \(\left \lbrace \vec w’ + t\begin{bmatrix} 1 \\ 9/5 \\ 32 \\ -32 \end{bmatrix}, t \in \mathbb{R} \right\rbrace\) |
\(\left \lbrace \vec w’ + t\begin{bmatrix} 1 \\ 9/5 \\ 32 \\ -32 \end{bmatrix}, t \in \mathbb{R} \right\rbrace\)
If we add any vector in \(\text{nullsp}(X)\) to one solution of the normal equation, we get another solution. So we just need to find a non-zero vector in \(\text{nullsp}(X)\).
For any row of \(X\), the following two statements must be true:
The idea is to use this information to find a linear combination of \(X\)’s columns that equals the zero vector.
Using the first equation, we have
In order to write this as a linear combination of \(X\)’s columns, the 32 needs to come from a vector that is “constant” across all rows. Fortunately, that’s true of the sum of the night and day columns, since \(\text{night}_i + \text{day}_i = 1\) for all rows. So, this means
Meaning that
Therefore, if \(\vec w’\) is one solution, the complete set of solutions is
6 pts First, assume \(h(\vec x_i)\) is the model at the top of the page.
What is the largest possible rank of the design matrix, \(X\)? (Note that we’re asking about the full design matrix, not just its first two rows.)
\(\text{largest possible value of }\text{rank}(X) = \_\_\_\_\_\_\)
True or False: The sum of the errors of the model’s predictions is 0.
True or False: The sum of the errors of the model’s predictions on just the rows of the dataset corresponding to night games is 0.
Let \(\vec e = \vec y - X \vec w^{\ast}\) be the error vector. Since \(\vec w^{\ast}\) satisfies the normal equation, \(\vec e\) is orthogonal to every column of \(X\), and to every linear combination of those columns.
The largest possible rank of \(X\) is 3, which happens when the tempF, tempC, and night columns are linearly independent. When the day column is added, the columns become linearly dependent. (Equivalently, the tempF, night, and day columns are linearly independent, but linearly dependent with the tempC column.)
This is true. Even though there is no explicit intercept term (and thus, no column of all ones), the all-ones vector is still in \(\text{colsp}(X)\), because the night and day columns add up to 1 for each row.
Since \(\vec e\) is orthogonal to every vector in \(\text{colsp}(X)\), it is orthogonal to \(\vec 1\), so
This is also true. The night indicator is itself a column of \(X\), so
But this dot product is exactly the sum of the errors for just the night games, because the night column has 1s on night rows and 0s elsewhere.
6 pts Now, suppose we remove the \(\textbf{day}_i\) feature from our model, meaning our model is
After removing the day column, what is the largest possible rank of the new design matrix?
\(\text{largest possible value of }\text{rank}(\text{new design matrix}) = \_\_\_\_\_\_\)
True or False: The sum of the errors of the new model’s predictions is 0.
True or False: The sum of the errors of the new model’s predictions on just the rows of the dataset corresponding to night games is 0.
Let \(\vec e_{\text{new}}\) be the error vector for the new model.
After removing the day column, the new design matrix has 3 columns, and there is no longer a forced linear dependence among them. So the largest possible rank is still 3. What’s new now is that \(X\)’s columns are all linearly independent, meaning there is a unique solution to the normal equation.
This is false. The normal equations still tell us that \(\vec e_{\text{new}}\) is orthogonal to each column of the new design matrix, but there is no guarantee that the all-ones vector is in the column space anymore. So the errors are not guaranteed to sum to 0.
This is true. The night indicator column is still present in the new design matrix, so \(\vec e_{\text{new}}\) is orthogonal to that column. Therefore, the sum of the errors over the night-game rows is still 0.
6 pts Suppose \(A\) is a \(4 \times 4\) matrix and \(\vec x \in \mathbb{R}^4\). Furthermore, suppose that the gradient of the function \(f(\vec x) = \vec x^T A \vec x\) is given by
Find one possible matrix \(A\). Your answer should be a \(4 \times 4\) matrix with no variables.
\(A = \_\_\_\_\_\_\)
Recall that for
the gradient is
We want
One easy way to make this happen is to choose \(A\) to be diagonal and symmetric. Then \(A + A^T = 2A\), so we want
Thus, one possible choice is
4 pts Suppose \(A\) is an \(n \times n\) matrix, \(\vec b \in \mathbb{R}^n\), and that \(g: \mathbb{R}^n \to \mathbb{R}\) is defined by
Which of the following is \(\nabla g(\vec x)\), the gradient of \(g(\vec x)\)?
\(2 A^T \vec b\)
\((\vec b^T A \vec x) A^T \vec b\)
\(2 (\vec b^T A \vec x) \vec b\)
\(2 (\vec b^T A \vec x) A^T \vec b\)
\(2 (\vec b^T A \vec x) A^T \vec x\)
None of the above
None of the above
Let
Then
The gradient of \(f(\vec x)\) can be computed using the dot product “big three” rule, which tells us that
Applying the chain rule,
Let \(\vec x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\). Consider the function
3 pts Fill in the blanks: The set of all vectors \(\vec x^{\ast}\) that minimize \(f(\vec x)\) form a __(i)__ in \(\mathbb{R}^2\). This set __(ii)__ a subspace of \(\mathbb{R}^2\).
We have
so the minimum value is 0, which happens exactly when
The equation
describes a line in \(\mathbb{R}^2\).
This line is not a subspace, because it does not pass through the origin. For example,
is not a minimizer. Therefore, this set is not a subspace.
8 pts Suppose we use gradient descent to minimize \(f(\vec x)\) using an initial guess of \(\vec x^{(0)} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\).
Find the learning rate/step size \(\alpha\) that will cause gradient descent to converge to a global minimum of \(f(\vec x)\) in one iteration, i.e. such that \(\vec x^{(1)}\) is a minimizer of \(f(\vec x)\).
Show your work in the space provided, and write your final answer in the bottom-right corner of the box. Your answer should be a number with no variables.
First, we need to compute the gradient of \(f(\vec x)\):
At
we have
so
One gradient descent step gives
We want \(\vec x^{(1)}\) to be a minimizer, so it must satisfy
That gives