The Question That Started It
After learning Gaussian elimination, LU factorization can initially look like another matrix technique that has to be learned separately.
But there is a natural question:
If Gaussian elimination already transforms \(A\) into an upper triangular matrix \(U\), haven’t we already done most of LU factorization?
Following that question reveals that \(A=LU\) is not disconnected from elimination at all. It is already hiding inside the elimination process.
Start With Ordinary Gaussian Elimination
Consider
\[A=\begin{bmatrix}\frac32&-1\\1&2\end{bmatrix}.\]
We want to eliminate the \(1\) underneath the first pivot \(\frac32\).
The elimination multiplier is
\[\ell_{21}=\frac{1}{3/2}=\frac23.\]
Therefore the row operation is
\[R_2\leftarrow R_2-\frac23R_1.\]
Since
\[\frac23\begin{bmatrix}\frac32&-1\end{bmatrix}=\begin{bmatrix}1&-\frac23\end{bmatrix},\]
the new second row is
\[\begin{bmatrix}1&2\end{bmatrix}-\begin{bmatrix}1&-\frac23\end{bmatrix}=\begin{bmatrix}0&\frac83\end{bmatrix}.\]
Thus Gaussian elimination gives
\[A\longrightarrow U=\begin{bmatrix}\frac32&-1\\0&\frac83\end{bmatrix}.\]
At this point we have done nothing new. This is ordinary elimination.
But Something Else Was Produced During Elimination
While producing \(U\), we also calculated the multiplier
\[\ell_{21}=\frac23.\]
Normally we might use this number and then forget it.
Instead, suppose we save it in a lower triangular matrix:
\[L=\begin{bmatrix}1&0\\\frac23&1\end{bmatrix}.\]
Now multiply \(L\) and \(U\):
\[LU=\begin{bmatrix}1&0\\\frac23&1\end{bmatrix}\begin{bmatrix}\frac32&-1\\0&\frac83\end{bmatrix}.\]
The result is
\[LU=\begin{bmatrix}\frac32&-1\\1&2\end{bmatrix}=A.\]
Therefore
\[\boxed{A=LU}.\]
Question: Isn’t L Just the Inverse of the Elimination Matrix?
This observation becomes even clearer if we connect LU to elimination matrices.
The row operation
\[R_2\leftarrow R_2-\frac23R_1\]
can be represented by the elimination matrix
\[E=\begin{bmatrix}1&0\\-\frac23&1\end{bmatrix}.\]
Therefore elimination can be written as
\[EA=U.\]
Now multiply both sides from the left by \(E^{-1}\):
\[E^{-1}EA=E^{-1}U.\]
Since \(E^{-1}E=I\),
\[A=E^{-1}U.\]
But LU factorization says
\[A=LU.\]
So in this one-step example,
\[\boxed{L=E^{-1}}.\]
The inverse elimination matrix is
\[E^{-1}=\begin{bmatrix}1&0\\\frac23&1\end{bmatrix},\]
which is exactly the \(L\) obtained by storing the multiplier.
Why Does the Sign Change?
The elimination matrix performs
\[R_2\leftarrow R_2-\frac23R_1.\]
To undo that operation, we must add the same quantity back:
\[R_2\leftarrow R_2+\frac23R_1.\]
That is why
\[E=\begin{bmatrix}1&0\\-\frac23&1\end{bmatrix}\]
while
\[E^{-1}=L=\begin{bmatrix}1&0\\\frac23&1\end{bmatrix}.\]
Conceptually:
\[A\xrightarrow{E}U\]
and going backwards,
\[U\xrightarrow{E^{-1}}A.\]
Therefore
\[A=E^{-1}U=LU.\]
The Next Question: Why Introduce L At All?
At this point another question naturally appears:
If we already knew about \(E^{-1}\), why introduce an extra matrix called \(L\)?
For a \(2\times2\) matrix requiring only one elimination step, there is indeed not much conceptual advantage. We could simply write
\[A=E^{-1}U.\]
The real reason becomes clearer when a larger matrix requires several elimination operations.
If elimination requires matrices \(E_1,E_2,E_3\), then
\[E_3E_2E_1A=U.\]
Undoing those operations gives
\[A=E_1^{-1}E_2^{-1}E_3^{-1}U.\]
Instead of repeatedly carrying this product of inverse elimination matrices, we can collect their effect into one lower triangular matrix \(L\).
Then the entire relationship becomes
\[\boxed{A=LU}.\]
Watching L Emerge From a 3 × 3 Elimination
Consider
\[A=\begin{bmatrix}2&1&1\\4&3&3\\8&7&9\end{bmatrix}.\]
For now, forget about LU. Perform ordinary Gaussian elimination and simply write down every multiplier used.
Step 1: Eliminate the 4 Below the First Pivot
The first pivot is \(2\). To eliminate \(4\),
\[\ell_{21}=\frac42=2.\]
Perform
\[R_2\leftarrow R_2-2R_1.\]
This changes row 2 to
\[\begin{bmatrix}0&1&1\end{bmatrix}.\]
Record:
\[\boxed{\ell_{21}=2}.\]
Step 2: Eliminate the 8 Below the Same Pivot
Now
\[\ell_{31}=\frac82=4.\]
Perform
\[R_3\leftarrow R_3-4R_1.\]
This produces
\[\begin{bmatrix}0&3&5\end{bmatrix}.\]
Now the matrix is
\[\begin{bmatrix}2&1&1\\0&1&1\\0&3&5\end{bmatrix}.\]
Record:
\[\boxed{\ell_{31}=4}.\]
Step 3: Eliminate the 3 Below the Second Pivot
The second pivot is \(1\), so
\[\ell_{32}=\frac31=3.\]
Perform
\[R_3\leftarrow R_3-3R_2.\]
The third row becomes
\[\begin{bmatrix}0&0&2\end{bmatrix}.\]
We have reached
\[\boxed{U=\begin{bmatrix}2&1&1\\0&1&1\\0&0&2\end{bmatrix}}.\]
And along the way we recorded
\[\ell_{21}=2,\qquad \ell_{31}=4,\qquad \ell_{32}=3.\]
Now Look at the Multipliers
Put the three multipliers into their corresponding positions below the diagonal:
\[L=\begin{bmatrix}1&0&0\\\ell_{21}&1&0\\\ell_{31}&\ell_{32}&1\end{bmatrix}.\]
Therefore
\[\boxed{L=\begin{bmatrix}1&0&0\\2&1&0\\4&3&1\end{bmatrix}}.\]
Nothing additional had to be discovered. The numbers \(2,4,3\) had already been calculated during Gaussian elimination.
We simply stopped throwing them away.
Check the Factorization
We now have
\[L=\begin{bmatrix}1&0&0\\2&1&0\\4&3&1\end{bmatrix}\]
and
\[U=\begin{bmatrix}2&1&1\\0&1&1\\0&0&2\end{bmatrix}.\]
Multiplying gives
\[LU=\begin{bmatrix}2&1&1\\4&3&3\\8&7&9\end{bmatrix}=A.\]
Therefore
\[\boxed{A=LU}.\]
The Important Realization
This changes the way LU factorization should be remembered.
It is tempting to memorize it as another formula:
\[A=LU.\]
But the more useful mental model is:
\[\boxed{\text{LU factorization is Gaussian elimination with the multipliers saved.}}\]
During ordinary elimination we were already producing both parts:
\(U\) is where Gaussian elimination ended.
\(L\) records the multipliers that were used to get there.
So before formally learning \(A=LU\), we were already doing much of the work required to create it. LU factorization makes that hidden structure explicit and reusable.
The Flow to Remember
The conceptual path is therefore:
\[A\xrightarrow{\text{Gaussian elimination}}U.\]
Elimination matrices express the same process as
\[EA=U.\]
For one elimination step, reversing it gives
\[A=E^{-1}U,\]
so
\[L=E^{-1}.\]
For larger systems, many elimination operations are performed. Their elimination information is collected into the lower triangular matrix \(L\), while the result of elimination is \(U\).
That is why the original matrix can be reconstructed as
\[\boxed{A=LU}.\]
Question to Carry Forward
We now understand where \(L\) and \(U\) come from. But one important question remains:
If Gaussian elimination already solves \(Ax=b\), what practical advantage do we gain by keeping the factorization \(A=LU\)?
That is the next step in understanding LU factorization.
Note metadata
- Note type: learning-note
- Subject: learning-notes
- Source: Introduction to Linear Algebra, Fifth Edition
- Related notes: 1