# Homework 3

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

1. Show how to compute the inverse of a matrix efficiently using Gaussian elimination. Show this for the matrix $\begin{bmatrix} 1 & -1 & 2 \\ 3 & 1 & 0 \\ 2 & 1 & -1 \end{bmatrix}$. What is the arithmetic complexity of inverting an $n \times n$ integer matrix? What is the bit complexity if each entry of the matrix uses at most $b$ bits?
2. Suppose that A is a symmetric matrix with eigenvalues strictly between 0 and 1. Show that $(I-A)^{-1} = I+\sum_{i=1}^\infty A^i$.  What is the error if we truncate after $k$ terms, i.e., give a bound on $\|(I-A)^{-1} - B\|$ where $B = I+\sum_{i=1}^k A^i$?
3. To solve $Ax=b$, consider the iteration: $x^{i+1}= A^Tb + (I-A^TA)x^i, x^0 = 0$. What is the rate of convergence, provided $A$ has singular values $0<\lambda_n \le \lambda_{n-1} \le \ldots \le \lambda_1 < 1$?
4. Consider the continued fraction expansion of a real number $r = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \ldots}}$. Let the successive approximations be $p_k/q_k$. Show that $p_k, q_k$ satisfy the following recurrences $p_{k+1} = a_kp_k + p_{k-1}, q_{k+1}= a_k q_k + q_{k-1}$. What are the base values?
5. Regression. For an $m \times n$ matrix $A$, what is the optimal solution to $min_x \|Ax-b\|$? Show that it is unique for any nonzero $A$.