Elementary Matrices and LU Factorization

Elementary Matrices Revisited

Reviewing the concept of elementary matrices, which are associated with elementary row operations. These operations include:

  1. Adding a multiple of one row to another (Type 1).

  2. Interchanging two rows.

  3. Multiplying a row by a non-zero constant.

An elementary matrix is derived by performing the corresponding row operation on the identity matrix. For example, swapping rows 1 and 3 of the identity matrix results in an elementary matrix that swaps rows 1 and 3 of any matrix when multiplied on the left.

Properties and Invertibility

Elementary matrices enact row operations via left multiplication. They are invertible because row operations are reversible. The inverse of an elementary matrix corresponds to the inverse row operation. For instance, the inverse of multiplying a row by a constant k is multiplying by 1/k. Swapping rows is its own inverse. Adding a multiple of one row to another can be undone by subtracting the same multiple of that row from the other.

Example:

To subtract two copies of row one from row two using an elementary matrix, first construct the elementary matrix by performing that operation on the 3x3 identity matrix, resulting in:

\begin{bmatrix} 1 & 0 & 0 \ -2 & 1 & 0 \ 0 & 0 & 1 \end{bmatrix}

Multiplying this matrix on the left by any 3xN matrix will subtract two copies of row one from row two.

Row Equivalence and Reduced Row Echelon Form

Row equivalent matrices can be transformed into each other via elementary row operations. A key concept is the reduced row echelon form, which is unique for any given matrix. This means regardless of the sequence of row operations used, the reduced row echelon form will be the same.

Representation Using Elementary Matrices

Transforming a matrix A into its reduced row echelon form r can be expressed as a series of left multiplications by elementary matrices: Ep \dots E2 E_1 A = r. This implies r can be written as a product of elementary matrices acting on A.

To reverse this process and obtain A from r, apply the inverse row operations in reverse order, which corresponds to multiplying by the inverse elementary matrices in the opposite order.

Invertibility Theorems

  • A matrix A is row equivalent to its reduced row echelon form.

  • A square matrix is invertible if and only if its reduced row echelon form is invertible.

The inverse of a product of matrices is the product of their inverses in reverse order. Given A = E1^{-1}E2^{-1}…Ep^{-1}r, then A^{-1} = r^{-1}Ep…E2E1.

Thus, A is invertible if and only if its reduced row echelon form is the identity matrix. This is because a matrix in reduced row echelon form is invertible if and only if it is the identity matrix.

Example: Applying Row Operations

Consider a 3xN matrix A and three row operations with corresponding elementary matrices E1, E2, and E3. Applying these operations in order means multiplying A on the left:E3E2E1A. Matrix multiplication is associative but not commutative, so the order matters. If A is chosen such that these operations transform it into the identity matrix, then E3E2E1A = I, and E3E2E1 is the inverse of A.

Algorithm for Finding the Inverse

Starting with [A | I] and performing row operations to get [I | A^{-1}] illustrates that the product of elementary matrices that transforms A to I also transforms I to A^{-1}.

Gauss-Jordan Elimination

The Gauss-Jordan elimination algorithm can be used to reduce a matrix to its reduced row echelon form. If the reduced row echelon form is the identity matrix, the original matrix is invertible. The algorithm involves finding the leftmost column with a non-zero entry, swapping the row to bring that entry to the top, and then using that entry to eliminate all entries below it. The order is essential for a standard application, but the reduced row echelon form will be the same regardless.

LU Factorization

LU factorization involves expressing a matrix A as the product of a lower triangular matrix (L) and an upper triangular matrix (U), such that A = LU. A matrix is lower triangular if all entries above the main diagonal are zero, and upper triangular if all entries below the main diagonal are zero. Echelon form is a special case of being upper triangular.

Solving Ax = b Using LU Factorization

If A = LU, then solving Ax = b is equivalent to solving LUx = b. Let Ux = y, then first solve Ly = b for y, and then solve Ux = y for x. This simplifies solving the system because forward substitution can be used when matrix is lower triangular, starting solving for y1, then y2, etc. backward substitution can be used to solve for x, starting for solving for xn, then x{n-1}, etc.

Algorithm for LU Factorization

To find the LU factorization, reduce A to an echelon form U using only Type 1 row operations (adding a multiple of one row to another). The matrix L is constructed such that the same sequence of row operations would reduce L to the identity matrix. The entries in L are the negatives of the factors used in the Type 1 row operations to get from A to U. Following the standard ordering of the Gauss Jordan algorithm is important.

Example

For a matrix A, perform row operations to eliminate entries below the diagonal. The negatives of the coefficients used in these row operations are placed in the corresponding positions in the L matrix. For instance, if adding two copies of row one to row two eliminates an entry, then -2 is placed in the (2,1) position of L.

Computational Efficiency

LU factorization is computationally more efficient and less prone to round-off errors than directly computing A^{-1} and solving Ax = b. While having a lower triangular matrix is valuable, a permuted lower triangular matrix can also be used and that results in PLU factorisation.