Advanced Linear Algebra: Are you ready?

• ALWAYS: \(L_{TL}\) and \(L_{BR} \) are nonsingular.

  From an undergraduate level course you may remember that a lower triangular matrix is nonsingular if and only if none of its diagonal elements equal zero. Hence the proof goes something like

  • Clearly \(L_{TL} \) and \(L_{BR} \) are lower triangular.

  • Since \(L \) is nonsingular and lower triangular, none of its diagonal elements equal zero.

  • Hence one of the diagonal elements of \(L_{TL} \) and \(L_{BR} \) equal zero.

  • We conclude that \(L_{TL} \) and \(L_{BR} \) are nonsingular.

  A careful reader may wonder what happens if \(L_{TL} \) or \(L_{BR} \) is \(0 \times 0 \text{.}\) This technical detail is solved by arguing that any \(0 \times 0 \) matrix \(A \) is nonsingular since the solution of \(A x = y \) is unique: only the empty vector (an vector with no elements) satisfies it.

• ALWAYS: \(\left( \begin{array}{c | c} L_{00}^{-1} \amp 0 \\ \hline - l_{10}^T L_{00}^{-1} / \lambda_{11}\amp 1/\lambda_{11} \end{array} \right) \text{.}\)

  One shows that \(B \) is the inverse of a matrix \(A \) by verifying that \(A B = I\) (the identity).

  \begin{equation*} \begin{array}{l} \left( \begin{array}{c | c} L_{00} \amp 0 \\ \hline l_{10}^T \amp \lambda_{11} \end{array} \right) \left( \begin{array}{c | c} L_{00}^{-1} \amp 0 \\ \hline - l_{10}^T L_{00}^{-1} / \lambda_{11}\amp 1/\lambda_{11} \end{array} \right) ~~~ = ~~~~ \lt \mbox{ partitioned matrix-matrix multiplication } \gt \\ \left( \begin{array}{c | c} L_{00} L_{00}^{-1} \amp 0 \\ \hline l_{01}^T L_{00}^{-1} - \lambda_{11} l_{10}^T L_{00}^{-1} / \lambda_{11} \amp \lambda_{11} / \lambda_{11} \end{array} \right) \\ ~~~ = ~~~~ \lt C C^{-1} = I \gt \\ \left( \begin{array}{c | c} I \amp 0 \\ \hline 0 \amp 1 \end{array} \right) \\ ~~~ = ~~~~ \lt \mbox{ partitioned identity } \gt \\ I \end{array} \end{equation*}

  Here \(I \) equals an identity matrix "of appropriate size."

• ALWAYS: \(\left( \begin{array}{c | c} L_{TL}^{-1} \amp 0 \\ \hline - L_{BR}^{-1} L_{BL} L_{TL}^{-1} \amp L_{BR}^{-1} \end{array} \right) \text{.}\)

  \begin{equation*} \begin{array}{l} \left( \begin{array}{c | c} L_{TL} \amp 0 \\ \hline L_{BL} \amp L_{BR} \end{array} \right) \left( \begin{array}{c | c} L_{TL}^{-1} \amp 0 \\ \hline - L_{BR}^{-1} L_{BL} L_{TL}^{-1} \amp L_{BR}^{-1} \end{array} \right) \\ ~~~ = ~~~~ \lt \mbox{ partitioned matrix-matrix multiplication } \gt \\ \left( \begin{array}{c | c} L_{TL} L_{TL}^{-1} \amp 0 \\ \hline L_{BL} L_{TL}^{-1} - L_{BR} L_{BR}^{-1} L_{BL} L_{TL}^{-1} \amp L_{BR} L_{BR}^{-1} \end{array} \right) \\ ~~~ = ~~~~ \lt C C^{-1} = I \gt \\ \left( \begin{array}{c | c} I \amp 0 \\ \hline 0 \amp I \end{array} \right) \\ ~~~ = ~~~~ \lt \mbox{ partitioned identity } \gt \\ I \end{array} \end{equation*}

• Let \(L \) also be unit triangular (meaning it has only ones on its diagonal in addition to being nonsingular and lower triangular).

  ALWAYS: \(L^{-1} \) is unit lower triangular.

  We employ a proof by induction. This time, we are going to look at a number of base cases, since the progression gives insight.

  • Base case 0: \(m = 0 \text{.}\)

    This means \(L \) is a \(0 \times 0 \) unit lower triangular matrix. To make this case work, you have to accept that a \(0 \times 0 \) matrix is automatically unit lower triangular and equal to the identity. If we let \(B \) be a \(0 \times 0 \) matrix with \(L B = I \) (where \(I \) is the \(0 \times 0 \) identity matrix), then \(L^{-1} = B \) and it is unit lower triangular since it is \(0 \times 0 \text{.}\)

  • Base case 1: \(m = 1 \text{.}\) (Not really needed.)

    This means \(L \) is a \(1 \times 1 \) unit lower triangular matrix. Hence \(L = 1 \text{.}\) Clearly, \(L^{-1} = 1 \text{,}\) which is a unit lower triangular matrix.

  • Base case 2: \(m = 2 \text{.}\) (Not really needed, but it provides some insight.)

    This means \(L \) is a \(2 \times 2 \) unit lower triangular matrix. Hence

    \begin{equation*} L = \left( \begin{array}{c c} 1 \amp 0 \\ \lambda_{10} \amp 1 \end{array} \right). \end{equation*}

    It can be easily checked that

    \begin{equation*} L^{-1} = \left( \begin{array}{c c} 1 \amp 0 \\ -\lambda_{10} \amp 1 \end{array} \right), \end{equation*}

    which is a unit lower triangular matrix.

  • Inductive step:

    Assume the Inductive Hypothesis (I.H) that the inverses of all unit lower triangular matrices \(L \in \mathbb R^{m \times m} \) with \(m = k \text{,}\) where \(k \geq 0 \text{,}\) are unit lower triangular.

    Under this assumption, we need to show that the inverse of any unit lower triangular matrix \(L \in \mathbb R^{m \times m} \) with \(m = k+1 \) is unit lower triangular.

    Let \(L \in \mathbb R^{(k+1) \times (k+1)} \text{.}\) Partition

    \begin{equation*} L = \left( \begin{array}{ c | c } L_{00} \amp 0 \\ \hline l_{10}^T \amp 1 \end{array} \right), \end{equation*}

    where \(L_{00} \in \mathbb R^{k \times k}\) is unit lower triangular and \(l_{10}^T \in \mathbb R^{1 \times k} \text{.}\) It can be easily checked that

    \begin{equation*} L^{-1} = \left( \begin{array}{ c | c } L_{00}^{-1} \amp 0 \\ \hline - l_{10}^T L_{00}^{-1} \amp 1 \end{array} \right). \end{equation*}

    By the I.H., \(L_{00}^{-1} \) is unit lower triangular, and hence so is \(L^{-1} \text{.}\)

  • By the Principle of Mathematical Induction, the result holds.

Relevance

We keep hammering on this: understanding how to partition matrices and then multiply with partitioned matrices is key to being able to abstract away from concrete (and small) problems, and generalize to matrices of arbitrary size.

The notation we use, combined with the observation that

allows us to express an algorithm for inverting a nonsingular lower triangular matrix with what we call the FLAME notation that hides indexing into individual entries of a matrix:

Algorithm here?????

Resources

In LAFF, we go through great lengths to help the learner extend their understanding gained from manipulating examples with small matrices and vectors too more general results and algorithms, using the partitioning of matrices and vectors (what we call "slicing and dicing" in that course).