# Exams and solutions¶

## Exam 1¶

1. (10) Solve the following system of linear equations (use any technique you like but show all work):

$\begin{eqnarray*} x_1 + 2x_2 + 3x_3 &=& 5,\\ x_1 - 2 x_2 + 3x_3 &=& 1,\\ x_1 + x_2 + x_3 &=& 2. \end{eqnarray*}$

Solution

1. Write the problem in augmented matrix form:

$$$\left( \begin{array}{ccc|c} 1 & 2 & 3 & 5\\ 1 & -2 & 3 & 1\\ 1 & 1 & 1 & 2 \end{array} \right)$$$
2. Simplify

$$$\left( \begin{array}{ccc|c} 1 & 2 & 3 & 5\\ 0 & -4 & 0 & -4\\ 0 & -1 & -2 & -3 \end{array} \right)$$$
3. Simplify

$$$\left( \begin{array}{ccc|c} 1 & 2 & 3 & 5\\ 0 & 1 & 0 & 1\\ 0 & -1 & -2 & -3 \end{array} \right)$$$
4. Simplify

$$$\left( \begin{array}{ccc|c} 1 & 2 & 3 & 5\\ 0 & 1 & 0 & 1\\ 0 & 0 & -2 & -2 \end{array} \right)$$$
5. Simplify

$$$\left( \begin{array}{ccc|c} 1 & 2 & 3 & 5\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 \end{array} \right)$$$
6. Simplify

$$$\left( \begin{array}{ccc|c} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 \end{array} \right)$$$

Thus the solution is $$(0,1,1)^T$$.

2. (25) Let $${\bf u} = [1,\, 2,\, 3]^T$$ and $${\bf v} = [1,\, 0,\, -1]^T$$ be column vectors and let $$A = I + {\bf u}{\bf v}^T$$, with $$I$$ being the identity matrix.

1. Compute $$A^{-1}$$ by any technique (don’t use the formula in (1)). Show all work.
2. Check your computation by using the formula $$A^{-1} = I^{-1} - \frac{{\bf u}{\bf v}^T}{1+{\bf v}^T {\bf u}}$$. Show all work.
3. The formula holds in general, assuming $$A$$ is invertible. Prove that the formula is correct by a direct computation. Show all work.

Solution

For 1. you can for example use the elimination method with an augmented matrix. For 2. We note that $$1+{\bf v}^T {\bf u} = -1$$ and

$$${\bf u} {\bf v}^T = \left( \begin{array}{ccc} 1 & 0 & -1 \\ 2 & 0 & -2 \\ 3 & 0 & -3 \end{array} \right)$$$

This yields

$$$A^{-1} = \left( \begin{array}{ccc} 2 & 0 & -1 \\ 2 & 1 & -2 \\ 3 & 0 & -2 \end{array} \right).$$$

For 3. we simply check that $$A A^{-1} = I$$.

$\begin{eqnarray*} A A^{-1} & = & (I + {\bf u}{\bf v}^T)(I^{-1} - \frac{{\bf u}{\bf v}^T}{1+{\bf v}^T {\bf u}}) \\ & = & I + {\bf u}{\bf v}^T - \frac{{\bf u}{\bf v}^T}{1+{\bf v}^T {\bf u}} - {\bf u}{\bf v}^T \frac{{\bf u}{\bf v}^T}{1+{\bf v}^T {\bf u}} \\ & = & I + {\bf u}{\bf v}^T \frac{1+{\bf v}^T {\bf u}}{1+{\bf v}^T {\bf u}} - \frac{{\bf u}{\bf v}^T}{1+{\bf v}^T {\bf u}}- \frac{{\bf u}{\bf v}^T{\bf u}{\bf v}^T}{1+{\bf v}^T {\bf u}} \\ & = & I. \end{eqnarray*}$

3. (25) Find the $$LU$$-factorization of the matrix $$A = LU$$. Calculate the determinant of $$A$$ using the $$LU$$-factorization and compare to the value you get if you perform cofactor expansion (both calculations are required).

$\begin{equation*} A = \left( \begin{array}{rrr} \displaystyle 4 & 3 & -5\\ \displaystyle -4 & -5 & 7\\ \displaystyle 8 & 6 & -8 \end{array} \right). \end{equation*}$

Solution

The two pivots to cancel the elements below the diagonal in the first column are 1 and -2. This reduces $$A$$ to

$\begin{equation*} U = \left( \begin{array}{rrr} \displaystyle 4 & 3 & -5\\ \displaystyle 0 & -2 & 2\\ \displaystyle 0 & 0 & 2 \end{array} \right). \end{equation*}$

This is already in upper triangular form so we are done, $$L$$ is

$\begin{equation*} L = \left( \begin{array}{rrr} \displaystyle 1 & 0 & 0\\ \displaystyle -1 & 1 & 0\\ \displaystyle 2 & 0 & 1 \end{array} \right). \end{equation*}$

As $$\det (A) = \det(L) \det(U)$$ we see that $$\det (A)=-16$$. The cofactor expansion yields

$\begin{eqnarray*} \det (A) = 4 \left| \begin{array}{rr} -5 & 7\\ 6 & -8\\ \end{array} \right| -3 \left| \begin{array}{rr} -4 & 7\\ 8 & -8\\ \end{array} \right| -5 \left| \begin{array}{rr} -4 & -5\\ 8 & 6\\ \end{array} \right| =\\ 4*(-2) -3*(-24) -5*16 = -16. \end{eqnarray*}$

4. (20) Explain why the columns of an $$n \times n$$ matrix $$A$$ are linearly independent when $$A$$ is invertible.

Solution

There are many options for this one. If $$A$$ is invertible we know that there is a unique solution to $$A{\bf x}={\bf b}$$ for any $${\bf b} \in \mathbb{R}^n$$. This solutions is just the right linear combination to combine into $${\bf b} = x_1 {\bf a}_1 + \ldots + x_n {\bf a}_n$$ but as $${\bf b}$$ was arbitrary the columns must form a spanning set. The only chance for $$n$$ vectors to form a spanning set for $$\mathbb{R}^n$$ is if they are linearly independent.

5. (20)

1. Find the null space of the matrix:

$\begin{equation*} A = \left( \begin{array}{ccc} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\\ \end{array} \right). \end{equation*}$

Show all work.

2. Let $${\bf x_1}$$ and $${\bf x_2}$$ be the Null vectors solving $$A {\bf x_1} = A {\bf x_2} = {\bf 0}$$. Find a vector $${\bf x_3}$$ so that the set $$\{{\bf x_1},{\bf x_2},{\bf x_3} \}$$ spans $$\mathbb{R}^3$$. Show all work.

Solution

By inspection we may choose $${\bf x_1} = (1,-1,0)^T$$ and $${\bf x_2} = (1,0,-1)^T$$. An example of a vector that is linearly independent of the null vectors is $${\bf x_3} = (1,1,1)^T$$.

6. (20 extra points) Choose either (1) or (2). Show all work.

1. Suppose you write a program for your telephone that computes the determinant of an $$n \times n$$ matrix. Assuming your telephone can perform $$10^6$$ multiplications / additions per second, estimate how large your matrix can be if you need the answer within one hour when your program is based on: (i) co-factor expansion, (ii) elimination. State clearly your assumptions.

Hint: Note that $$\ln 3.6 \approx 1.28 ,\, \ln 10 \approx 2.3$$, recall Stirling’s formula and use the attached graph.

2. Prove by induction that for any integer \$:math:n ge 1, (2^{2n} - 1) is divisible by 3.

Solution

1. The telephone can perform $$3.6 \cdot 10^{9}$$ per hour. Using elimination the cost of computing the determinant is, to leading order, $$2n^3/3$$ so the biggest matrix we can handle has $$n = (3/2 \cdot 3.6 \cdot 10^{9})^{1/3} \approx 1750$$. The complexity using co-factor expansion is $$n!$$ as you multiply the $$n$$ elements of a row with the minor, i.e., the determinant of an $$(n-1) \times (n-1)$$ matrix, etc. Stirling’s formula is $$\ln (n!) \approx n \ln (n) - n$$ which should be equal to $$\ln (3.6 \cdot 10^{9}) \approx 1.28 + 9 \cdot 2.3 \approx 22$$ From the graph we find that $$14 \ln (14) \approx 37$$ and $$13 \ln (13) \approx 33$$ so $$\ln(14!) \approx 23$$ and $$\ln(13!) \approx 20$$. Thus we can perhaps handle an $$13 \times 13$$ but not an $$14 \times 14$$.
2. The base case $$n = 1$$ hold as $$2^2-1 = 4-1 = 3$$. Now assuming that $$(2^{2n} - 1)$$ is divisible by 3 we note that $$(2^{2(n+1)} - 1) = (2^2\,2^{2n} - 1)= 3\,2^{2n} + (2^{2n}- 1)$$ which are both divisible by 3.