Due: Oct 30th in class.
- Let be an matrix with $latex $r$ nonzero singular values, all distinct. Show that the SVD of is unique.
- In class we proved that is a singular vector of the matrix . Define . Show that is also a singular vector of .
- Given a directed graph with a root vertex , 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 ?
- 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 matrix show that exactly one of the following holds: (i) there is a nonzero vector s.t. (ii) there is a vector s.t. . What does this mean geometrically?
- Show that for any compact convex set and any point , either or there is a hyperplane with on one side and all of on the other side.