Applied Linear Algebra - Practice Problems

Practice problems

Penrose quasi-inverse: smallest LLS solution

Given an LLS problem with $A$ and $𝐛$, show that the Penrose quasi-inverse solution $A^{+}𝐛$ is the LLS solution of smallest length. Show that this solution lies in the cokernal of $A$. (Hint: use the SVD of $A$.)

Problem 13-04

Optimizing $|A𝐱|$ to find singular vectors

Show that the second largest singular value of $A$ is equal to the maximum of $|A𝐱|$ where $𝐱$ varies over all unit vectors which are orthogonal to $𝐯$, where $𝐯$ is a right singular vector corresponding to the largest singular value of $A$.

(Notation clarification: if the singular values are listed in order of size ${\sigma }_1\ge {\sigma }_2\ge {\sigma }_3\ge \cdots \ge {\sigma }_{\ell }$, then the largest singular value is ${\sigma }_1$, the second largest is ${\sigma }_2$, and the right singular vector in the problem is ${𝐯}_1$ satisfying $A{𝐯}_1={\sigma }_1{𝐮}_1$.)

Problem 14-05

Penrose quasi-inverse

For this problem, use the definition of $A^{+}$ based on the SVD of $A$.

• (a) Verify that $A{A}^{+}A=A$ and that $A^{+}A{A}^{+}=A^{+}$ for the example $A=\left(\begin{array}{cc}-3& 1\\ 6& -2\\ 6& -2\end{array}\right)$ studied in the section on quasi-inverse. Think about how and why this happens in terms of the SVD.
• (b) Show that for any $A$ matrix, $A{A}^{+}𝐯$ is the projection of $𝐯$ onto the image of $A$.
• (c) Show that for any $A$ matrix, $A{A}^{+}A=A$ and $A^{+}A{A}^{+}=A^{+}$.

It may be helpful (though not required) for this problem to use the presentation of SVD in the form $A={\sigma }_1{𝐮}_1{𝐯}_1^{𝖳}+{\sigma }_2{𝐮}_2{𝐯}_2^{𝖳}+\cdots$ as in Packet 13. In order to use this, figure out what the corresponding presentation of the SVD of $A^{+}$ should be.

Problem 14-06

LLS uniqueness

• (a) Show that: $A𝐱=\mathrm{𝟎}$ if and only if $A^{𝖳}A𝐱=\mathrm{𝟎}$. (Hint: use the fact that ${𝐱}^{𝖳}{A}^{𝖳}A𝐱=|A𝐱{|}^2$.)
• (b) Show that: $A^{𝖳}A$ is invertible if and only if $A$ has independent columns. (Warning: $A$ need not be square. Hint: consider the dimensions of kernels, and use (a) as well as the rank-nullity theorem.)
• (c) Explain why the LLS problem for $A$ and $𝐛$ has a unique solution if and only if the columns of $A$ are independent. (Use (b).)
• (d) Continuing from (b), show that: $\mathrm{rank}(A)=\mathrm{rank}(A^{𝖳}A)$. (Hint: apply rank-nullity to both matrices. Notice that $A$ and $A^{𝖳}A$ have the same number of columns.)

You may observe that (a) implies $\dim \mathrm{Ker}(A)=\dim \mathrm{Ker}(A^{𝖳}A)$, while (d) means $\dim \mathrm{Im}(A)=\dim \mathrm{Im}(A^{𝖳}A)$. In other words, $A$ and $A^{𝖳}A$ always have the same size kernels and the same size images. This makes sense in terms of the SVD if you think about kernels, cokernels, and images generated by the orthonormal basis vectors ${𝐮}_i$’s and ${𝐯}_i$’s, writing $A={\sigma }_1{𝐮}_1{𝐯}_1^{𝖳}+{\sigma }_2{𝐮}_2{𝐯}_2^{𝖳}+\cdots$ as in the previous problem (keeping careful track of which ${\sigma }_i$’s are zero or nonzero!).

Finding a projection to the space perpendicular to given vectors

Let:

$${𝐯}_1=\left(\begin{array}{c}1\\ -1\\ 0\\ 0\\ 0\\ 0\end{array}\right),{𝐯}_2=\left(\begin{array}{c}-1\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right),{𝐯}_3=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\\ 0\\ 1\end{array}\right),{𝐯}_4=\left(\begin{array}{c}0\\ 0\\ 0\\ -1\\ 1\\ -1\end{array}\right).$$

• Find the orthogonal complement of the span $⟨{𝐯}_1,{𝐯}_2,{𝐯}_3,{𝐯}_4⟩$, written as a span.
• Find the projection of $𝐮=(\mathrm{1,1,1,1,1,1})$ to that complement using normal equations.
• Find a matrix that performs the projection to this orthogonal complement using an augmented matrix.

Problem 14-03

Fitting a plane to four points

Consider the four data points in $3$D space:

$$(x,y,z)=(\mathrm{1,0,0}),(\mathrm{0,1,1}),(-\mathrm{1,0,3}),(0,-\mathrm{1,4}).$$

Find the parameters $a,b,c$ for which the plane defined by $z=a+bx+cy$ best fits these data points.

You may notice that the data points correspond to heights $z=\mathrm{0,1,3,4}$ at the four corners of a square. Normally a plane is defined by 3 points (non-colinear) through which it passes. No plane passes through these four given points. But there is a plane that minimizes the sum of squares of vertical errors.

LLS uniqueness

Suppose we are given data $(x,y)=(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)$. The linear least squares problem has a unique solution if and only if the design matrix column vectors are independent. (You may use this fact from the previous problem.)

• (a) Suppose we are finding the line of best fit for the given data. (Model: $y=b+mx$.) Show that as long as we can find $i$ and $j$ with $x_i\ne x_j$, then there is a unique best fit line for this data.
• (b) Suppose we are finding the parabola of best fit for the given data. (Model: $y=a+bx+c{x}^2$.) Suppose that $x_1$, $x_2$, and $x_3$ are all distinct values. Show that there is a unique best fit parabola for this data.

LLS summation curve model

Consider the data points:

$$(x,y)=(\mathrm{1,1.8}),(\mathrm{2,2.6}),(\mathrm{3,3.3}),(\mathrm{4,3.8}),(\mathrm{5,4.1}).$$

Find the parameters of best fit for the model $y=ax+b{x}^2$. Clearly identify your design matrix, observation vector, and parameter vector. Compute the error vector and the total error.