Advanced Linear Algebra: Are you ready?

Solution

• \begin{equation*} \begin{array}{r r r r} 2 \chi_0 + \amp \chi_1 + \amp \chi_2 = \amp 1 \\ -2 \chi_0 - \amp 2 \chi_1 + \amp \chi_2 = \amp -4 \\ 4 \chi_0 + \amp 4 \chi_1 + \amp \chi_2 = \amp 2 \\ \end{array} \end{equation*}

  can be represented by the appended system

  \begin{equation*} \left( \begin{array}{r r r | r} 2 \amp 1 \amp \phantom{-}1 \amp 1 \\ -2 \amp -2 \amp 1 \amp -4 \\ 4 \amp 4 \amp 1 \amp 2 \\ \end{array} \right). \end{equation*}

  Subtracting \(-1 \) times the first row from the second row and subtracting \(2 \) times the first row from the third row yields

  \begin{equation*} \left( \begin{array}{r r r | r} 2 \amp 1 \amp 1 \amp 1 \\ 0 \amp -1 \amp 2 \amp -3 \\ 0 \amp 2 \amp -1 \amp 0 \\ \end{array} \right). \end{equation*}

  Subtracting \(-2 \) times the second row from the third row yields

  \begin{equation*} \left( \begin{array}{r r r | r} 2 \amp 1 \amp 1 \amp 1 \\ 0 \amp -1 \amp 2 \amp -3 \\ 0 \amp 0 \amp 3 \amp -6 \\ \end{array} \right). \end{equation*}

  This translates to

  \begin{equation*} \begin{array}{r r r r} 2 \chi_0 + \amp \chi_1 + \amp \chi_2 = \amp 1 \\ \amp - \chi_1 + \amp 2 \chi_2 = \amp -3 \\ \amp \amp 3 \chi_2 = \amp -6 \end{array} \end{equation*}

  Solving this upper triangular system yields \(\chi_2 = -2 \text{,}\) \(\chi_1 = -1 \text{,}\) and \(\chi_0 = 2 \text{.}\)

• The LU factorization can be read off from the above "Gaussian elimination" process for reduction the system of linear equations to an upper triangular system of linear equations:

  \begin{equation*} \begin{array}[t]{c} \underbrace{ \left( \begin{array}{r r r} 2 \amp 1 \amp 1 \\ -2 \amp -2 \amp 1 \\ 4 \amp 4 \amp 1 \end{array} \right) } \\ A \end{array} = \begin{array}[t]{c} \underbrace{ \left( \begin{array}{r r r} 1 \amp 0 \amp 0 \\ -1 \amp 1 \amp 0 \\ 2 \amp -2 \amp 1 \end{array} \right) } \\ L \end{array} \begin{array}[t]{c} \underbrace{ \left( \begin{array}{r r r} 2 \amp 1 \amp 1 \\ 0 \amp -1 \amp 2 \\ 0 \amp 0 \amp 3 \end{array} \right) } \\ U \end{array} \end{equation*}

• If \(A = L U \) then

  \begin{equation*} A x = b \end{equation*}

  can be rewritten as

  \begin{equation*} ( L U ) x = b . \end{equation*}

  Associativity of multiplication yields

  \begin{equation*} L ( U x )x = b . \end{equation*}

  If we introduce the variable \(z = U x \) we get that

  \begin{equation*} L z = b. \end{equation*}

  Thus, we can first solve the lower triangular system \(L z = b \) and then \(U x = z \text{,}\) which yields the desired solution \(x \text{.}\)

• TRUE

  We saw in the first part of this question that

  \begin{equation*} x = \left( \begin{array}{r} 2 \\ -1 \\ -2 \end{array} \right) \end{equation*}

  solves \(A x = b \text{.}\) Hence \(b \) can be written as a linear combination of the columns of \(A \text{:}\)

  \begin{equation*} \left( \begin{array}{r} 1 \\ -4 \\ 2 \end{array} \right) = (2) \left( \begin{array}{r} 2 \\ -2 \\ 4 \end{array} \right) + (-1) \left( \begin{array}{r} 1 \\ -2 \\ 4 \end{array} \right) + (-2) \left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right) \end{equation*}

  which means that \(b \) is in the column space of \(A \text{.}\)

Relevance

Solving linear systems is fundamental to scientific computing and data sciences. While (Gaussian) elimination is a technique taught already in high school algebra, it is by presenting it as a factorization of matrices that it can be made systematic and implemented. Viewing it this way is also fundamental to being able to analyze how computer arithmetic and algorithms interact, which is at the core of the numerical linear algebra covered in an advanced linear algebra courrse.

Solving "dense" linear systems is also a convenient vehicle for discussing how to achieve high performance on current computer architectures.

Resources

In Week 6 and Week 7 of LAFF solvinig linear systems via Gaussian elimination is linked to LU factorization.