# Homework 4

Due: Oct 30th in class.

1. Let $A$ be an $m \times n$ matrix with $latex$r\$ nonzero singular values, all distinct. Show that the SVD of $A$ is unique.
2. In class we proved that $v^{(1)} = \arg\max_{v:\|v\|=1} \|Av\|$ is a singular vector of the matrix $A$. Define  $v^{(k)} = \arg\max_{v: \|v\|=1, v \perp v^{(1)}, \ldots, v^{(k-1)}} \|Av\|$. Show that $v^{(k)}$ is also a singular vector of $A$.
3. Given a directed graph $G = (V,E)$ with a root vertex $r \in V$, an arborescence is a subset of edges that contains a directed path from the root to each vertex of the graph. Given nonnegative costs on the edges, write the problem of finding a minimum-cost arborescence as a linear program. What is a short proof that the minimum arborescence has cost at least some value $C$?
4. Give an example of an unbounded LP with 3 or more variables and write its dual. What can you argue about the dual?
5. Given an $n \times n$ matrix $A$ show that exactly one of the following holds: (i) there is a nonzero vector $x\ge 0$ s.t. $Ax=0$ (ii) there is a vector $y$ s.t. $A^Ty < 0$. What does this mean geometrically?
6. Show that for any compact convex set $K$ and any point $x$, either $x \in K$ or there is a hyperplane with $x$ on one side and all of $K$ on the other side.