Homework 4

Due: Oct 30th in class.

Let $A$ be an $m \times n$ matrix with $latex $r$ nonzero singular values, all distinct. Show that the SVD of $A$ is unique.
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$ .
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$ ?
Give an example of an unbounded LP with 3 or more variables and write its dual. What can you argue about the dual?
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?
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.