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_{TL}^{-1} \amp 0 \\ \hline - L_{BR}^{-1} L_{BL} L_{TL}^{-1} \amp L_{BR}^{-1} \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_{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*}

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

• 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.)

    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

Should we link the proof to an algorithm in FLAME notation here?

Resources

This exercise reiterates the role of partitioned matrices, abstraction, partitioned matrix-matrix multiplication, and proof by induction.