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.