\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
Math and science::Algebra

LU decomposition

Let \( A \) be a 3x3 square invertible matrix. Elimination on \( A \) by a sequence of elimination matrices \( E_{21}, E_{31} \) and \( E_{32} \) results in an upper triangular matrix \( U \):

\[ E_{32} E_{31} E_{21} A = U \]

We can combine the elimination matrices together:

\[ E = E_{32} E_{31} E_{21} \]

and invert to arrive at the LU decomposition:

\[ A =  E_{21}^{-1} E_{31}^{-1} E_{32}^{-1} U =E^{-1} U = LU \]

The elements of the matrix \( L \) have a very direct interpretation, arguably more interpretable than those of \( E \). If \( l_{21}, l_{31} \) and \( l_{32} \) are the scalars by which the first and second rows are subtracted from the rows below, then we can express \( L \) as:

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \\ \end{bmatrix} \]

Intuition

Operating on the "finished" \( U \) that is outputted by elimination, \( L \) reverses the row operations that were used in the elimination process. As each forward row operation only used "finished" rows to modify subsequent rows, when going in reverse, the building blocks of the row operations are present as-is in \( L \), as the "finished" rows are prepopulated by \( U \). This allows \( L \) to very simply record one number for each row operation.

A combined of rank 1 matrices. Perspective.

\( A \) can be seen to explode into rank 1 matrices through the elimination process. Consider a modified elimination where we try to reduce \( A \) to a matrix of all zeros. The first step is to remove the first row of \( A \) times a unique factor from every row of \( A \) to give zeros in the first column. The factors are

\[ \begin{bmatrix} 1 \\ l_{21} \\ l_{31} \end{bmatrix} \]

and the matrix being removed is:

\[ \begin{bmatrix} 1 \;\;\; (-\text{row 1}-) \\ l_{21} \; (-\text{row 1}-) \\ l_{31}\; (-\text{row 1}-) \end{bmatrix} \]

So, we are removing a rank one matrix, column times row, from \( A \). Repeating this for each column will result in the zero vector. Consequently, these combined rank 1 matrices equal \( A \).

\( A = LU \) decomp and the determinant of \( A \)

\( \operatorname{det}(A) = \operatorname{det}(L) \operatorname{det}(U) \), but as the diagonals of \( L \) are all ones, we have \( \operatorname{det}(A) = \operatorname{det}(U) \), and the determinant can be read off as the product of diagonal entries of \( U \).

Example

Example

The matrix \( T \) is converted to upper triangular form as follows:

\[ \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \\ \end{bmatrix} \to \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & -1 & 2 \\ \end{bmatrix} \to \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \\ \end{bmatrix} \]

This corresponds to the two elimination matricies:

\[ E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}, \quad E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix} \]

Inverting these steps to get \( E_{32}^{-1} E_{21}^{-1} \) gives:

\[ \begin{align*} E_{21}^{-1} E_{32}^{-1} &= \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \\ \end{bmatrix} \\ &= \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \\ \end{bmatrix} \end{align*} \]