Question

Let $$ A=\left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 3 & 0 \\ -.5 & 0 & -.2 & 1 \\ -.5 & -.3 & 1 & 0 \end{array}\right) $$ Decompose \(A\) using partial pivoting as $$ P A=L U $$ where \(U\) is upper triangular, \(L\) is unit lower triangular and \(P\) is a permutation matrix. Record all the elementary matrices, \(P^{(i)}\), and \(M^{(i)}\) along the way. (You can use MATLAB to help you with these small, annoying calculations.) Show that \(L\) relates to \(\left[M^{(3)}\right]^{-1}\left[M^{(2)}\right]^{-1}\left[M^{(1)}\right]^{-1}\) in the way explained in Section \(5.3\), and find \(\tilde{M}^{(1)}, \bar{M}^{(2)}\), and \(\tilde{M}^{(3)}\).

Short answer

#Answer# L = $\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0 \\\ 1/2 & 0 & 1 & 0 \\\ 1/2 & 0 & -\frac{8}{9} & 1 \end{array}\right)$

Step-by-step solution

Find the first pivot and interchange rows

First, identify the largest element in the first column as the pivot element. The largest element is 1, which is in the second row. So we need to swap the first and second rows using the permutation matrix \(P^{(1)}\): $$ P^{(1)}= \begin{bmatrix} 0 & 1 & 0 & 0 \\\ 1 & 0 & 0 & 0 \\\ 0 & 0 & 1 & 0 \\\ 0 & 0 & 0 & 1 \end{bmatrix} $$ Now, apply the permutation matrix to A: $$ P^{(1)} A=\left(\begin{array}{cccc} 1 & 0 & 3 & 0 \\\ 0 & 1 & 0 & 0 \\\ -.5 & 0 & -.2 & 1 \\\ -.5 & -.3 & 1 & 0 \end{array}\right) $$

Eliminate first column elements below the pivot

To eliminate the elements in the first column below the first pivot element, apply the following elementary matrix \(M^{(1)}\): $$ M^{(1)} =\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0 \\\ 1/2 & 0 & 1 & 0 \\\ 1/2 & 0 & 0 & 1 \end{array}\right) $$ Resulting matrix after applying \(M^{(1)}\) is: $$ M^{(1)} P^{(1)} A=\left(\begin{array}{cccc} 1 & 0 & 3 & 0 \\\ 0 & 1 & 0 & 0 \\\ 0 & 0 & 2.8 & 1 \\\ 0 & -.3 & 1.5 & 0 \end{array}\right) $$

Find the second pivot and interchange rows

For the second pivot, focus on the submatrix starting from the second row and the second column. The pivot element is -.3, which is in the fourth row. Swap the third and fourth rows using the permutation matrix \(P^{(2)}\): $$ P^{(2)} = \begin{bmatrix} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0 \\\ 0 & 0 & 0 & 1 \\\ 0 & 0 & 1 & 0 \end{bmatrix} $$ Applying the permutation matrix gives: $$ P^{(2)} M^{(1)} P^{(1)} A=\left(\begin{array}{cccc} 1 & 0 & 3 & 0 \\\ 0 & 1 & 0 & 0 \\\ 0 & -.3 & 1.5 & 0 \\\ 0 & 0 & 2.8 & 1 \end{array}\right) $$

Eliminate second column element below the pivot

Eliminate the element in the second column below the second pivot element by applying the following elementary matrix \(M^{(2)}\): $$ M^{(2)} = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0 \\\ 0 & 0 & 1 & 0 \\\ 0 & -\frac{8}{9} & 0 & 1 \end{array}\right) $$ Applying \(M^{(2)}\) gives the resulting matrix: $$ M^{(2)} P^{(2)} M^{(1)} P^{(1)} A=\left(\begin{array}{cccc} 1 & 0 & 3 & 0 \\\ 0 & 1 & 0 & 0 \\\ 0 & 0 & 1.5 & 0 \\\ 0 & 0 & 0 & 1 \end{array}\right) $$

Compute L using inverse elementary matrices

Compute L by using the relation $$L=\left[M^{(3)}\right]^{-1}\left[M^{(2)}\right]^{-1}\left[M^{(1)}\right]^{-1},$$ where \(M^{(3)}=I\), since we don't need a third multiplier matrix. $$ L = M^{(1)} P^{(2)} M^{(2)} =\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0 \\\ 1/2 & 0 & 1 & 0 \\\ 1/2 & 0 & -\frac{8}{9} & 1 \end{array}\right) $$

Compute \(\tilde{M}^{(1)}, \bar{M}^{(2)},\) and \(\tilde{M}^{(3)}\) matrices

# Finally, we find the modified elementary matrices: $$ \tilde{M}^{(1)} = P^{(1)}M^{(1)} $$ $$ \bar{M}^{(2)} = P^{(2)} M^{(2)} $$ $$ \tilde{M}^{(3)} = I $$

Key concepts

LU Decomposition

The LU decomposition is a method used in numerical analysis to factor a given square matrix into two matrices: a lower triangular matrix (L) and an upper triangular matrix (U). The main idea behind LU decomposition is to simplify complex matrix operations by breaking them into manageable pieces. This is particularly useful in solving systems of linear equations, inverting matrices, and computing determinants.

The process starts with a matrix A and transforms it step by step using elementary row operations until the matrix is in upper triangular form, which will be the matrix U. Simultaneously, we record the row operations with elementary matrices, and the inverse of these products gives us the matrix L. Partial pivoting, as seen in the example, is a strategy that provides numerical stability to the decomposition, where rows of the matrix are interchanged to position the largest absolute value (pivot) as the leading coefficient of the working submatrix.

LU decomposition can be performed manually on smaller matrices or with the computer aid for larger and more complex matrices, as suggested by the step-by-step solution using MATLAB software. This reduces the risk of calculation errors and saves time.

Permutation Matrix

A permutation matrix is a square matrix that results from permuting the rows of an identity matrix. In the context of LU decomposition with partial pivoting, permutation matrices are used to swap rows of the original matrix to bring the largest pivot into position. These matrices are a key part of ensuring the numerical stability of the decomposition process.

Permutation matrices are orthogonal and their inverse is equal to their transpose. This means that applying permutation matrices to a given matrix does not alter the determinant of the original matrix. In the solution you saw, P⁽¹⁾ and P⁽²⁾ were applied to matrix A to swap rows for the first and second pivots, respectively.

The property that permutation matrices are binary—containing only zeros and ones—and each row and column have exactly one entry of 1 makes their use in calculations particularly straightforward and easy to interpret, emphasizing their convenient role in matrix algebra operations.

Elementary Matrices

Elementary matrices represent the simplest form of row operations that can be performed on a matrix. These include row swapping, row multiplication, and row addition, or a combination of these. In the LU decomposition process, we use a series of elementary matrices to transform the original matrix A step by step until it becomes an upper triangular matrix U.

In the example provided, the matrices M⁽¹⁾, M⁽²⁾, and M⁽³⁾ (which turned out to be the identity matrix in this case, indicating no third operation was needed) were used to eliminate the elements below the pivots. These elementary matrices, when multiplied with the permutation matrices and applied to A, gave the form M⁽ⁱ⁾P⁽ⁱ⁾A at each step.

A crucial aspect to remember is that to find matrix L, we use the inverses of these elementary matrices, demonstrating a fundamental property: an elementary matrix's inverse is also an elementary matrix, but representing the opposite row operation.