Problem Set 3. Due Wed, Oct 11th at the beginning of class.

- Show how to compute the inverse of a matrix efficiently using Gaussian elimination. Show this for the matrix . What is the arithmetic complexity of inverting an integer matrix? What is the bit complexity if each entry of the matrix uses at most bits?
- Suppose that A is a symmetric matrix with eigenvalues strictly between 0 and 1. Show that . What is the error if we truncate after terms, i.e., give a bound on where ?
- To solve , consider the iteration: . What is the rate of convergence, provided has singular values ?
- Consider the continued fraction expansion of a real number . Let the successive approximations be . Show that satisfy the following recurrences . What are the base values?
- Regression. For an matrix , what is the optimal solution to ? Show that it is unique for any nonzero .