Notes on Strang Lecture - 4

Lecture link

LU Transformation

A matrix $A$ as the product of a lower triangular matrix $L$ and an upper triangular matrix $U$:

$A = LU$

Basic example

Consider the matrix: $A = \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$

We can factorize this as: $A = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} = LU$

Where:

• $L = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}$ is the lower triangular matrix
• $U = \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}$ is the upper triangular matrix

Key property: multipliers in L

Important observation: If no row exchange is required during Gaussian elimination, the multipliers used in the elimination process go directly into the lower triangular matrix $L$.

In the example above:

• To eliminate the entry $A_{21} = 8$, we use the multiplier $m_{21} = \frac{8}{2} = 4$
• This multiplier appears directly in position $(2,1)$ of matrix $L$
• The diagonal entries of $L$ are always 1

General form

For an $n \times n$ matrix $A$, the LU decomposition has the form:

• $L$ is lower triangular with ones on the diagonal (the inverse of the elimination matrix)
• $U$ is upper triangular (the result from Gaussian elimination)