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:

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

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

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

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

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

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

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

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

This yields

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

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.