#### Allowable row operations:

Multiply row       by    /

Add    /    times row       to row

## About LU Factorization

An $$n \times n$$ system of equations $$Ax = b$$ can be solved via Gaussian elimination, the application of a series of elementary row operations. However, this can be difficult for large values of $$n$$; even systems of only three equations can be challenging to solve by hand. A simplified approach is to factor $$A = LU$$ as a product of matrices, where $$L$$ is a lower triangular matrix and $$U$$ is upper triangular. The system then becomes $$LUx=b$$, which is solved in two steps. First, we find the solution $$y$$ of the system $$Ly=b$$, and then find our required solution by solving $$Ux=y$$. These systems are simpler to solve; since $$L$$ and $$U$$ are triangular, back substitution can be used to quickly find $$y$$ and $$x$$.

Each of these row operations can be represented by an elementary matrix $$E$$. The matrix $$A$$ can be reduced to an upper triangular matrix $$U$$ by multiplication on the left by a particular sequence of these elementary matrices: $E_kE_{k-1} \cdots E_3E_2E_1A = U$ Multiplying both sides by the appropriate inverse of these elementary matrices results in the decomposition $A = E_1^{-1}E_2^{-1}E_3^{-1} \cdots E_{k-1}^{-1}E_k^{-1}U$ Since we've restricted the types of row operations allowed, the resulting product $$E_1^{-1}E_2^{-1}E_3^{-1} \cdots E_{k-1}^{-1}E_k^{-1}$$ will be lower triangular, and is our required matrix $$L$$.

Not all matrices have an $$LU$$ factorization. Any square matrix can be written as a product $$LUP$$ where $$P$$ is a permutation matrix. If $$A$$ is a square, invertible matrix whose leading principal minors are all non-zero, then it has an $$LU$$ factorization. Any matrix generated by this applet will satisfy this property.

In addition to its usefulness in solving linear systems, the $$LU$$ factorization can also be used to rapidly compute the determinant of $$A$$. The determinant of a triangular matrix is the product of its diagonal entries, and so the determinant of $$A$$ is the product of the diagonal entries of $$L$$ and $$U$$.

## Using the Applet

The purpose of this applet is to find the decomposition $$LU$$ of a provided $$4 \times 4$$ matrix $$A$$. Only two row operations are allowed: the addition of a multiple of one row to a row below it, and scalar multiplication of a row. Swapping two rows is not a valid step in finding the $$LU$$ decomposition (though it is permitted when finding the $$LUP$$ decomposition of square matrices).

The process begins with the equation $$LU=A$$, where $$U = A$$ and $$L$$ is the identity matrix. Use the menu to apply permitted elementary operations, transforming $$U$$ into an upper triangular matrix. As each operation is performed, the matrix $$L$$ is recalculated by being multiplied (on the right) by the inverse of the corresponding elementary matrix. The process is complete when $$U$$ is upper triangular. Note that the decomposition is not unique. The elementary matrix is recorded in the history box.

## About this Applet

This applet was created using JavaScript and the Raphael library. If you are unable to see the applet, make sure you have JavaScript enabled in your browser. This applet may not be supported by older browsers.