Skip to main content

MATH 345: Linear Algebra and Optimization

Sebastien Roch with Jacob Denson and Kaitlyn Phillipson

Section 6.7 Exercises

Learning outcomes. The labels below identify the learning outcomes for each exercise group. Individual problems may also involve earlier outcomes.
🔗

Subsection Lagrange multipliers

Learning outcomes. U6-LO1, U6-LO2.
🔗
🔗

Subsection Singular value decomposition

Learning outcomes. U6-LO4, U6-LO6, U6-LO7.
🔗
  • Nicholson 8.6.9(b)
     19 
    math.libretexts.org/Bookshelves/Linear_Algebra/Linear_Algebra_with_Applications_(Nicholson)/08%3A_Orthogonality/8.06%3A_The_Singular_Value_Decomposition/8.6E%3A_The_Singular_Value_Decomposition_Exercises
    🔗
    🔗
🔗

Subsection Additional exercises

These exercises connect absolute extrema, Lagrange multipliers with one and several constraints, quadratic forms, maximum stretch, PCA, SVD, rank, and the four fundamental subspaces. Solution sketches are collected in Appendix C.6.
🔗

Additional exercise 6.7.1. Choosing candidates and equations.

For each problem below, state the equations used to find candidates and say which candidates must be compared. Do not solve the equations.
🔗
  1. Find the absolute extrema of a differentiable function \(f(x,y)\) on the rectangle \(D=[a,b]\times[c,d]\text{.}\)
    🔗
    🔗
  2. Find extrema of \(f(\mathbf{x})\) subject to
    \begin{equation*} g(\mathbf{x})=k, \end{equation*}
    assuming \(\nabla g\ne\mathbf{0}\) on the feasible set.
    🔗
    🔗
  3. Find extrema of \(f(\mathbf{x})\) subject to
    \begin{equation*} g_1(\mathbf{x})=k_1, \qquad g_2(\mathbf{x})=k_2, \end{equation*}
    assuming the two constraint gradients are linearly independent on the feasible set.
    🔗
    🔗
  4. Find the absolute extrema of \(f(\mathbf{x})\) on the closed bounded region
    \begin{equation*} D=\{\mathbf{x}:g(\mathbf{x})\leq k\}, \end{equation*}
    assuming \(\nabla g\ne\mathbf{0}\) on its boundary.
    🔗
    🔗
Learning outcomes. U6-LO1, U6-LO2, U6-LO3.
🔗
🔗

Additional exercise 6.7.2. One quadratic form, three readings.

Let
\begin{equation*} B= \begin{bmatrix} 5 \amp 4\\ 4 \amp 5 \end{bmatrix}, \qquad A= \begin{bmatrix} 1 \amp 2\\ 2 \amp 1 \end{bmatrix}, \qquad C=\frac12B. \end{equation*}
🔗
  1. Find the eigenvalues of \(B\) and an orthonormal basis of eigenvectors.
    🔗
    🔗
  2. Find the absolute maximum and minimum values of
    \begin{equation*} q_B(\mathbf{x})=\mathbf{x}^TB\mathbf{x} \end{equation*}
    subject to
    \begin{equation*} \|\mathbf{x}\|=1. \end{equation*}
    🔗
    🔗
  3. Check that
    \begin{equation*} A^TA=B. \end{equation*}
    Find the singular values and right singular directions of \(A\text{.}\) What is
    \begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|? \end{equation*}
    🔗
    🔗
  4. Suppose \(C\) is the covariance matrix from the activity “Principal directions of a small data set”. Find the first and second principal directions and their captured variations.
    🔗
    🔗
  5. What fraction of the total centered variation is captured by the first principal direction?
    🔗
    🔗
  6. Why do the same two directions appear in all three readings?
    🔗
    🔗
Learning outcomes. U6-LO4, U6-LO5, U6-LO6, U5-LO4.
🔗
🔗

Additional exercise 6.7.3. Candidate table on a rectangle.

Let
\begin{equation*} f(x,y)=x^2+y^2-2x+4y \end{equation*}
on the rectangle
\begin{equation*} D=\{(x,y):0\leq x\leq 3,\ -3\leq y\leq 1\}. \end{equation*}
🔗
  1. Find the critical point of \(f\) in the interior of \(D\text{.}\)
    🔗
    🔗
  2. Find the boundary candidates on each of the four edges.
    🔗
    🔗
  3. Include the four corner points.
    🔗
    🔗
  4. Make a candidate table with the source of each candidate and the value of \(f\text{.}\)
    🔗
    🔗
  5. Find the absolute maximum and absolute minimum of \(f\) on \(D\text{.}\)
    🔗
    🔗
Learning outcomes. U6-LO1.
🔗
🔗

Additional exercise 6.7.4. Parallel gradients on a circle.

Let
\begin{equation*} f(x,y)=3x+4y \end{equation*}
and constrain the input to the circle
\begin{equation*} x^2+y^2=25. \end{equation*}
🔗
  1. Write the constraint as \(g(x,y)=25\text{.}\)
    🔗
    🔗
  2. Solve
    \begin{equation*} \nabla f=\lambda\nabla g. \end{equation*}
    🔗
    🔗
  3. Find the constrained critical points.
    🔗
    🔗
  4. Evaluate \(f\) at the constrained critical points.
    🔗
    🔗
  5. Which point gives the absolute maximum? Which point gives the absolute minimum?
    🔗
    🔗
  6. Explain geometrically why \(\nabla f\) is parallel to \(\nabla g\) at those points.
    🔗
    🔗
Learning outcomes. U6-LO2.
🔗
🔗

Additional exercise 6.7.5. Quadratic form on the unit circle.

Let
\begin{equation*} B= \begin{bmatrix} 5\amp 0\\ 0\amp 2 \end{bmatrix} \end{equation*}
and
\begin{equation*} q(\mathbf{x})=\mathbf{x}^TB\mathbf{x}. \end{equation*}
Write
\begin{equation*} \mathbf{x}= \begin{bmatrix} x\\ y \end{bmatrix}. \end{equation*}
🔗
  1. Write \(q(\mathbf{x})\) in terms of \(x\) and \(y\text{.}\)
    🔗
    🔗
  2. Maximize \(q(\mathbf{x})\) subject to
    \begin{equation*} \|\mathbf{x}\|=1. \end{equation*}
    🔗
    🔗
  3. Minimize \(q(\mathbf{x})\) subject to
    \begin{equation*} \|\mathbf{x}\|=1. \end{equation*}
    🔗
    🔗
  4. Which unit vectors give the extreme values?
    🔗
    🔗
  5. How do the answers relate to eigenvalues and eigenvectors of \(B\text{?}\)
    🔗
    🔗
Learning outcomes. U6-LO4.
🔗
🔗

Additional exercise 6.7.6. Maximum stretch of a matrix.

Let
\begin{equation*} A= \begin{bmatrix} 1\amp 2\\ 2\amp 1 \end{bmatrix}. \end{equation*}
🔗
  1. Compute \(A^TA\text{.}\)
    🔗
    🔗
  2. Find the eigenvalues of \(A^TA\text{.}\)
    🔗
    🔗
  3. Find the singular values of \(A\text{.}\)
    🔗
    🔗
  4. Find a unit right singular vector corresponding to the largest singular value.
    🔗
    🔗
  5. What is
    \begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|? \end{equation*}
    🔗
    🔗
  6. Which input direction is stretched most?
    🔗
    🔗
Learning outcomes. U6-LO4.
🔗
🔗

Additional exercise 6.7.7. Reading an SVD.

Suppose
\begin{equation*} A=U\Sigma V^T, \end{equation*}
where
\begin{equation*} U= \begin{bmatrix} 1\amp 0\\ 0\amp 1 \end{bmatrix}, \qquad \Sigma= \begin{bmatrix} 5\amp 0\amp 0\\ 0\amp 2\amp 0 \end{bmatrix}, \end{equation*}
and
\begin{equation*} V= \begin{bmatrix} 1/\sqrt2\amp 0\amp 1/\sqrt2\\ 1/\sqrt2\amp 0\amp -1/\sqrt2\\ 0\amp 1\amp 0 \end{bmatrix}. \end{equation*}
Thus the right singular vectors are
\begin{equation*} \mathbf{v}_1= \frac{1}{\sqrt2} \begin{bmatrix} 1\\ 1\\ 0 \end{bmatrix}, \qquad \mathbf{v}_2= \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}, \qquad \mathbf{v}_3= \frac{1}{\sqrt2} \begin{bmatrix} 1\\ -1\\ 0 \end{bmatrix}. \end{equation*}
🔗
  1. What are the singular values of \(A\text{?}\)
    🔗
    🔗
  2. What is \(\operatorname{rank}(A)\text{?}\)
    🔗
    🔗
  3. Compute \(A\mathbf{v}_1\text{,}\) \(A\mathbf{v}_2\text{,}\) and \(A\mathbf{v}_3\) using the SVD.
    🔗
    🔗
  4. Which input direction is forgotten?
    🔗
    🔗
  5. Which input directions are transmitted?
    🔗
    🔗
Learning outcomes. U6-LO6, U6-LO7.
🔗
🔗

Additional exercise 6.7.8. Fundamental subspaces from an SVD.

Use the SVD data from the previous checkpoint.
🔗
  1. Give an orthonormal basis for \(\operatorname{row}(A)\text{.}\)
    🔗
    🔗
  2. Give an orthonormal basis for \(\operatorname{null}(A)\text{.}\)
    🔗
    🔗
  3. Give an orthonormal basis for \(\operatorname{col}(A)\text{.}\)
    🔗
    🔗
  4. Give an orthonormal basis for \(\operatorname{null}(A^T)\text{.}\)
    🔗
    🔗
  5. Check that the dimensions agree with rank-nullity.
    🔗
    🔗
Learning outcomes. U6-LO7.
🔗
🔗

Additional exercise 6.7.9. Two constraints on a sphere.

Let
\begin{equation*} f(x,y,z)=x-y. \end{equation*}
🔗
Find the absolute extrema of \(f\) subject to
\begin{equation*} x^2+y^2+z^2=1 \end{equation*}
and
\begin{equation*} x+y+z=0. \end{equation*}
🔗
  1. Describe the feasible set geometrically. Why do absolute extrema exist?
    🔗
    🔗
  2. Show that the gradients of the two constraints are linearly independent at every feasible point.
    🔗
    🔗
  3. Form the Lagrangian using multipliers \(\lambda\) and \(\mu\text{.}\)
    🔗
    🔗
  4. Write and solve the Lagrange equations.
    🔗
    🔗
  5. Evaluate \(f\) at the candidates and identify the absolute maximum and minimum.
    🔗
    🔗
Learning outcomes. U6-LO3.
🔗
🔗

Additional exercise 6.7.10. Principal directions of a centered data set.

The rows of
\begin{equation*} X= \begin{bmatrix} 4\amp2\\ 2\amp4\\ -2\amp0\\ 0\amp-2 \end{bmatrix} \end{equation*}
are four data points in \(\R^2\text{.}\)
🔗
  1. Compute the mean \(\bar{\mathbf{x}}\) and the centered data matrix \(Z\text{.}\)
    🔗
    🔗
  2. Compute the covariance matrix
    \begin{equation*} C=\frac14Z^TZ. \end{equation*}
    🔗
    🔗
  3. Find the eigenvalues of \(C\) and corresponding orthonormal eigenvectors. Choose \(\mathbf{v}_1\) for the larger eigenvalue and \(\mathbf{v}_2\) for the smaller eigenvalue.
    🔗
    🔗
  4. Form
    \begin{equation*} V= \begin{bmatrix} \mathbf{v}_1\amp\mathbf{v}_2 \end{bmatrix} \end{equation*}
    and compute the principal-coordinate matrix
    \begin{equation*} T=ZV. \end{equation*}
    🔗
    🔗
  5. Compute
    \begin{equation*} V^TCV. \end{equation*}
    🔗
    🔗
  6. What fraction of the total centered variation is captured by the first principal direction?
    🔗
    🔗
Learning outcomes. U6-LO5.
🔗
🔗

Additional exercise 6.7.11. PCA reconstruction and regression.

Use the data and principal directions from the checkpoint “Principal directions of a centered data set”. The first centered data vector is
\begin{equation*} \mathbf{z}_1= \begin{bmatrix} 3\\ 1 \end{bmatrix}, \end{equation*}
and
\begin{equation*} \mathbf{v}_1 = \frac1{\sqrt2} \begin{bmatrix} 1\\ 1 \end{bmatrix}. \end{equation*}
🔗
  1. Compute the first principal-component score
    \begin{equation*} t_1=\mathbf{v}_1^T\mathbf{z}_1. \end{equation*}
    🔗
    🔗
  2. Compute the projected centered vector
    \begin{equation*} \widehat{\mathbf{z}}_1=t_1\mathbf{v}_1 \end{equation*}
    and the reconstruction residual
    \begin{equation*} \mathbf{r}_1 = \mathbf{z}_1-\widehat{\mathbf{z}}_1. \end{equation*}
    🔗
    🔗
  3. Check that
    \begin{equation*} \mathbf{r}_1\cdot\mathbf{v}_1=0. \end{equation*}
    🔗
    🔗
  4. Find the reconstructed original data point
    \begin{equation*} \widehat{\mathbf{x}}_1 = \bar{\mathbf{x}}+\widehat{\mathbf{z}}_1. \end{equation*}
    🔗
    🔗
  5. Give an equation for the PCA line
    \begin{equation*} \bar{\mathbf{x}}+\spans\{\mathbf{v}_1\}. \end{equation*}
    🔗
    🔗
  6. For the regression of \(y\) on \(x\text{,}\) use
    \begin{equation*} m=\frac{C_{12}}{C_{11}}, \qquad b=\bar y-m\bar x \end{equation*}
    to find the regression line.
    🔗
    🔗
  7. Why are the PCA and regression lines different? Describe the residual direction minimized by each method.
    🔗
    🔗
Learning outcomes. U6-LO5, U4-LO5.
🔗
🔗

Additional exercise 6.7.12. Redundant features revisited by singular values.

Return to the Unit 2 redundant-feature matrix
\begin{equation*} X= \begin{bmatrix} 1\amp 2\amp 3\\ 2\amp 4\amp 6\\ 0\amp 1\amp 1\\ 1\amp -1\amp 0 \end{bmatrix}. \end{equation*}
The third column is the sum of the first two columns.
🔗
  1. Verify that
    \begin{equation*} X \begin{bmatrix} 1\\ 1\\ -1 \end{bmatrix} = \mathbf{0}. \end{equation*}
    🔗
    🔗
  2. What does this say about \(\operatorname{null}(X)\text{?}\)
    🔗
    🔗
  3. What does this say about the rank of \(X\text{?}\)
    🔗
    🔗
  4. What singular value should appear because of this redundancy?
    🔗
    🔗
  5. If \(X\mathbf{c}=\mathbf{y}\text{,}\) what is
    \begin{equation*} X\left(\mathbf{c}+t \begin{bmatrix} 1\\ 1\\ -1 \end{bmatrix}\right)? \end{equation*}
    🔗
    🔗
  6. Explain how this revisits the Unit 2 idea of nonunique coefficient vectors.
    🔗
    🔗
Learning outcomes. U2-LO6, U6-LO7.
🔗
🔗

Additional exercise 6.7.13. PCA from an SVD.

Return to the centered data matrix from the checkpoint “Principal directions of a centered data set”. Suppose
\begin{equation*} Z=U_2\Sigma_2V^T, \end{equation*}
where
\begin{equation*} \mathbf{u}_1 = \frac12 \begin{bmatrix} 1\\ 1\\ -1\\ -1 \end{bmatrix}, \qquad \mathbf{u}_2 = \frac12 \begin{bmatrix} 1\\ -1\\ -1\\ 1 \end{bmatrix}, \end{equation*}
\begin{equation*} U_2= \begin{bmatrix} \mathbf{u}_1\amp\mathbf{u}_2 \end{bmatrix}, \qquad \Sigma_2= \begin{bmatrix} 4\sqrt2\amp0\\ 0\amp2\sqrt2 \end{bmatrix}, \end{equation*}
and
\begin{equation*} V= \frac1{\sqrt2} \begin{bmatrix} 1\amp1\\ 1\amp-1 \end{bmatrix}. \end{equation*}
🔗
  1. Use
    \begin{equation*} \lambda_j=\frac{\sigma_j^2}{4} \end{equation*}
    to recover the two covariance eigenvalues.
    🔗
    🔗
  2. Which columns of \(V\) are the first and second principal directions?
    🔗
    🔗
  3. Compute the principal-coordinate matrix
    \begin{equation*} T=U_2\Sigma_2. \end{equation*}
    🔗
    🔗
  4. Compute the reconstruction using only the first principal direction:
    \begin{equation*} \widehat Z_1 = \sigma_1\mathbf{u}_1\mathbf{v}_1^T. \end{equation*}
    🔗
    🔗
  5. What fraction of the total centered variation is captured by the first principal direction?
    🔗
    🔗
  6. What do the two columns of \(T\) represent?
    🔗
    🔗
Learning outcomes. U6-LO5, U6-LO7.
🔗
🔗
🔗
🔗
PrevTopNext