#### Allowable row operations:

Multiply row       by    /

Add    /    times row       to row

#### History of Elementary Matrices Applied:

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.