Factorizations

LU Decomposition

The LU Decomposition factors a matrix as the product of a lower triangular matrix and an upper triangular matrix .
We use the LU decomposition in solving linear equations. In particular, it is a matrix form of Gaussian Elimination.
- We do this as follows. Start with . The goal is to use Row Elementary Operations (using Elementary Matrices) to obtain .
- The Elementary Matrices we use to do this are lower triangular matrices.
Not all matrices have a LU decomposition. However, we can obtain a proper one if we allow for either partial pivoting or full pivoting.

LU Decomposition with Partial Pivoting involves using a permutation matrix

LU Decomposition with Full Pivoting involves both row and column permutations. We have permutation matrices and
We can also obtain a Lower-Diagonal-Upper (LDU) decomposition of the form

Where is diagonal, and and are lower and upper triangular matrices with the diagonal entries set to .
Consider the system expressed as .
- The vector is easily solved using forward substitution. Start with the first entry, substitute the corresponding value in and repeat
- Observe that can be solved easily using back substitution. Start with the last entry, substitute the value in and repeat.

The QR Decomposition factors a matrix into the product of orthonormal matrix and upper triangular matrix
One way to compute this is to use the Gram-Schmidt process. Let be the -th basis vector obtained from the Gram-Schmidt process and the -th column. Then
- Note however, that the Gram-Scmidt process is numerically unstable.
The rationale for this is that a solution to the system written as , we can solve this as follows
- Solve by observing that .
- Solve using back substitution.

The Power Method allows us to find the dominant eigenvector and eigenvalue of a matrix, that is, the eigenvalue with the largest absolute value and its associated normalized eigenvector.
Suppose that the matrix is diagonalizable with eigenbasis . First, it can be shown that if , that

Where is the unique largest eigenvalue.

Consider what happens at the limit. We have
The algorithm proceeds as follows.
- Start with an approximation for the dominant eigenvector.
- Proceed by computing
To get the associated eigenvalue, use the Rayleigh Quotient computed as follows

(Sullivan 4.3) If is an overdetermined system (that is, has more rows than columns), then we can opt to instead solve the system

The answer to this system is interpreted as the vector which solves exactly for the projection of onto the column space of .

We call this the Normal Equation.