MATH 1554 Course Notes - Fall 2026

 

We have learned several techniques for solving the equation \(A\vec x = \vec b\text{.}\) We could solve \(A\vec x=\vec b\) using \(\vec x=A^{-1}\vec b\text{,}\) but this requires computing the inverse of an \(n\times n\) matrix, which becomes difficult for large \(n\text{.}\) Gaussian elimination is better, but still inefficient for large systems.

More efficient and numerically stable methods rely on matrix factorizations. A matrix factorization (or matrix decomposition) is a factorization of a matrix into a product of matrices. Such factorizations help solve \(A\vec x=\vec b\) and reveal matrix structure. Several matrix factorizations appear throughout this course. In this section, we factor a matrix into lower and upper triangular matrices.

A rectangular matrix \(A\) is upper triangular if \(a_{i,j}=0\) whenever \(i>j\text{.}\)

A rectangular matrix \(A\) is lower triangular if \(a_{i,j}=0\) whenever \(i<j\text{.}\)

Can you have a matrix that is both upper and lower triangular?

 

 

How do we find \(L \) and \(U\text{?}\) Suppose \(A\) can be row reduced to echelon form \(U\) without interchanging rows. Then

where the \(E_j\) are elementary row-operation matrices. These matrices are lower triangular and invertible. For example,

 

Note, in MATH 1554, the only allowed row replacement operation can be written in the form \(R_i - kR_j \rightarrow R_i\text{.}\) The number \(k\) is what should go into the \(i^\text{th}\) row and \(j^\text{th}\) column of \(L\text{,}\) so \(\ell_{i,j} = k\text{.}\)

Caution 1: Note that \(\ell_{i,j}\) is the opposite of the scalar used in the row replacement. This is because the formula \(R_i - kR_j \rightarrow R_i\) has a negative sign built in.

Caution 2: Note that you are only guaranteed to find the correct \(\ell_{i,j}\) if you are working from left to right and from top to bottom. So, start with the leftmost pivot column and use its pivot row to elimnate all nonzero entries below it. Then move to the next pivot column (from the left) and repeat.

 

 

 

How do we use \(LU\) factorization to help us solve \(A\vec x=\vec b\text{?}\)

If \(A = LU\text{,}\) then the equation \(A \vec x = \vec b \) can be written \(LU \vec x = \vec b \text{,}\) or equivalently, \(L (U\vec x) = \vec b \text{.}\) Setting \(\vec y = U\vec x \text{,}\) we do the following:

Since \(L\) is an invertible matrix, the system \(L\vec y = \vec b\) will always be consistent and have a unique solution. The system \(U\vec x = \vec y\) may be inconsistent. Since \(U\) is in echelon form, we can quickly determine whether \(U\vec x = \vec y\) is inconsistent by checking if there is a nonzero entry in \(\vec y\) that corresponds to a row of zeros in \(U\text{.}\)