Pset A Solution

Pset A (Required More Substantial Pset, not droppable) Due Wednesday April 22. You may use all available materials. Some collaboration allowed but do your own work.

(1) Compute the projection matrices $\frac{aa^T}{a^Ta}$ onto the lines through $a_1=(-1,2,2)\in R^3$ and $a_2=(2,2,-1)\in R^3$. Multiply those projection matrices and explain why their product $P_1P_2$ is what it is.

Ans: $P_1=1/9 \left( \begin{matrix} 1 & -2 & -2 \\ -2 & 4 & 4 \\ -2 & 4 & 4 \end{matrix} \right) $. $P_2=1/9 \left( \begin{matrix} 4 & 4 & -2 \\ 4 & 4 & -2 \\ -2 & -2 & 1 \end{matrix} \right) $. $P_1P_2$ is the zero matrix. It is because $a_1$, $a_2$ are perpendicular to each other, i.e. $a_1^Ta_2=0$.

(2) A is an $m$ by $n$ matrix of rank $r$. Suppose there are right hand sides $b$ for which $Ax=b$ has no solution.

(a) What are all inequalities ($<$ or $\le$) that must be true between $m,n$ and $r$?
(b) How do you know that $A^T y=0$ has solutions other than $y=0$?

Ans:(a) $r<m$, $r \le n$. It is clear that both $m$ and $n$ is not less than $r$ by definition. The condition implies $m$ cannot be $r$. There are no other inequalities because $A$ can be taken as $\left( \begin{matrix} 1 \\ 0 \end{matrix}\right)$ and $\left( \begin{matrix} 1 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}\right)$.

(b) We know that the number of columns of $A^T$ is strictly larger than the rank by (a), which implies the columns of $A^T$ are linearly dependent. Therefore there is a non-trivial linear combinations of columns expressing zero. Equivalently, $A^T y=0$ has solutions other than $y=0$.

(3) Show that if $Q$ is nxn orthogonal, $\det(Q)=\pm 1$

Ans: Notice that $\det(Q)=\det(Q^T)$. $1=\det(QQ^T)=\det(Q)\det(Q^T)=\det(Q)^2$. Hence $\det(Q)=\pm 1$.

In [3]:

using LinearAlgebra
U, = qr(rand(3,3))
V, = qr(rand(3,3))
D  = Diagonal([3,2,1])
A = U*D*V'

Out[3]:

3×3 Array{Float64,2}:
  0.91466   -0.712155  1.27469
  1.08352    1.81051   1.09546
 -0.145023  -0.147505  2.31012

We have $\det(A)=\pm$(what number?) Why?

Ans: $\det(A)=\pm 6$. By the previous problem, $\det(U)=\det(V)= \pm 1$. $\det(A)=\det(U)\det(D)\det(V)=\pm \det(D)$. Since the determinant of a diagonal matrix is simply the product of its diagonal entries, $\det(D)=3*2*1=6$.

(5) $Q$ is a tall skinny 3x2 matrix. ($Q^TQ=I$) A picture of a corgi sits on the unit square in $R^2$. Describe carefully but briefly the image of this picture under $Q$. (What is the shape? What is the area? Where are the vertices?)

Ans: The image is a square in $R^3$ of area 1. Let the columns of $Q$ be $v$ and $w$. The vertices are the origin, $v$, $w$, $v+w$, which correspond to the image of vertices of the unit square under $Q$. To see it is a square of area 1, we only need to note that $v$ and $w$ are unit vectors which are perpendicular to each other.

(6) A solid box has volume 10 cubic meters. What is the shape of the image of the box under the transformation $A$ in question (4) above. What is the volume of this image?

Ans: The image is a solid parallelepiped of volume 10*6=60 cubic meters. Since $U$ and $V$ are orthogonal matrices, they won't change the shape and area of anything. Hence $D$ matters only, and it sends a solid box to a solid parallelepiped. The volume is scaled by a factor of 6.

(7) Suppose $A=U\Sigma V^T$ is the rank-r svd of an mxn matrix $A$. Write $x_r=$ the projection of x onto the row space of $A$ in terms of possibly $x$, $U$, or $V$.

Ans: $x_r=VV^Tx$. It is because the row space of $A$ coincides with that of $V^T$, which is the same as column space of $V$. The general projection formula states that $x_r=V(V^TV)^{-1}V^Tx=VV^Tx$ as $V^TV$ is the identity matrix.

(8) As in (7), write $x_n$=projection of $x$ on the nullspace of $A$ in terms of possibly $x$,$U$,$V$.

Ans: By definition we have $(x-x_n) \perp \text{null}(A)$. Notice that $\text{null}(A)^{\perp}=\text{row}(A)$, so $x-x_n \in \text{row}(A)$. Because $x_r \in \text{row}(A)$, so $x-x_n-x_r \in \text{row}(A)$. The same reason gives us $x-x_n-x_r \in \text{null}(A)$. Notice $\text{row}(A) \cap \text{null}(A) = 0$, so $x-x_r-x_n=0$, i.e. $x_r+x_n=x$. By (7) we know $x_r=VV^Tx$. So $x_n=x-VV^Tx$.

(9) As above, what is $x_r+x_n$ in simple terms?

Ans: By the above discussion we know $x_r+x_n=x$.

(10) As above, suppose $Ax_r=b$, what is $Ax$ in simplest form?

Ans: As above, $x=x_r+x_n$, so $Ax_r=A(x-x_n)=Ax-Ax_n$. But we know that $x_n \in \text{null}(A)$, so $Ax_n=0$ by definition. So $Ax=Ax_r=b$.

(11) As above, if $Ax_r=b$, is $b$ in the column space of $U$? Why or why not?

Ans: By (10) we know $Ax=b$. So $x \in \text{col}(A)$. We know $\text{col}(A)=\text{col}(U)$. So $b$ lies in the column space of $U$.

(12) Using the rank-r SVD, if $b$ is in col($A$), what is the unique solution in row($A$) to $Ax=b$?

Ans: We know the least-squares, least norm solution is $y=V\Sigma^{-1}U^T b$. If $b \in \text{col}(A)$, then this $y$ should be a real solution, i.e. $Ay=b$ holds.

Now we show $y \in \text{row}(A)$. Consider projecting $y$ on the row space of $A$. This is $VV^Ty$, then we have $VV^Ty=VV^TV\Sigma^{-1}U^Tb=V(V^TV)\Sigma^{-1}U^Tb=V\Sigma^{-1}U^Tb=y$. So projecting $y$ on the row space of $A$ gives us exactly $y$ itself. In other words, $y$ lies in $\text{row}(A)$.

So $V\Sigma^{-1}U^T b$ is the answer.

(13) Use the fact that swapping two rows of a matrix $A$ flips the sign of a determinant to show that det($A$)=0 if $A$ has two equal rows.

Ans: Suppose $A$ has two equal rows, say the i-th row and the j-th row. Swapping these two rows, we get the same matrix $A$. By the property of the determinant, we know $\det(A)=-\det(A)$. Hence $\det(A)=0$.

(14) Am I a linear transformation? (A linear transformation is a function $f$ from one vector space to another that satisfies $f(c_1x_1+c_2x_2)=c_1f(x_1)+c_2 f(x_2)$.

(14a) $f(A)=trace(A)$ from $n\times n$ A to $R$
(14b) $f(A)=\det(A)$
(14c) $f(x)=c^Tx$ for $x \in R^n$ (c constant in $R^n$)
(14d) $f(A)=M^TA$, for $m \times n$ $A$ and constant $M$ with $n$ columns.
(14e) $f(A)=X^T A Y$ for $m \times n$ $A$ and compatible constant matrices $X$ and $Y$
(14f) $f(A) = A^TA$ for $m \times n$ $A$
(14g) $f(A)= A+A^T$ for $n \times n$ $A$

Ans:

(a) Yes. $\text{trace}(c_1A_1+c_2A_2)=c_1\text{trace}(A_1)+c_2\text{trace}(A_2)$.

(b) No. (as long as $n \geq 2$, when $n=1$, obvious it is). Notice that $\det(2A)=2^n\det(A) \neq 2\det(A)$.

(d) Yes. $M^T(c_1A_1+c_2A_2)=c_1M^TA_1+c_2M^TA_2$.

(e) Yes. $X^T(c_1A_1+c_2A_2)Y=c_1X^TA_1Y+c_2X^TA_2Y$.

(f) No. Notice that $f(2A)=(2A)^T(2A)=4A^TA \neq 2 A^TA=2f(A)$.

(g) Yes. $(c_1A_1+c_2A_2)+(c_1A_1+c_2A_2)^T=c_1(A_1^T+A_1)+c_2(A_2^T+A_2)$.

(15) Suppose $m \times n$ $B$ has rank $m$. Let $B = U\Sigma V^T$ be the rank-r svd. What is $(BB^T)^{-1}?$

Ans: $B^T=V\Sigma U^T$, so we have $BB^T=U\Sigma V^TV\Sigma U^T=U\Sigma (V^TV)\Sigma U^T=U\Sigma^2U^T$.

Since $B$ has rank $m$, so that $U$ is an $m \times m$ orthogonal matrix, so $U^T=U^{-1}$, and $U\Sigma^2U^T$ is a product of three $m \times m$ matrices. So we have $(BB^T)^{-1}=(U\Sigma^2U^T)^{-1}=U(\Sigma^{-1})^2U^T$