Explainer: LDU and PLU Decomposition

In this explainer, we will learn how to find the LDU and PLU decompositions of a matrix.

Often, we choose to describe matrices as being of one or more β€œtypes,” which are typically determined by the order of the matrix as well as other additional features. For example, one of the simplest types of matrix is the square matrix, which has an equal number of rows and columns. Square matrices are the only types of matrix for which we can define the determinant or the multiplicative inverse matrix, which are two reasons why they are interesting to mathematicians. A subgroup of the square matrices are the lower-triangular and upper-triangular matrices, which are even more attractive because their determinant is easy to calculate (being simply the product of the diagonal entries) and any calculation involving them is easier due to the large number of entries that are zero.

Given that triangular matrices have many desirable algebraic properties, one common aim is to split or β€œdecompose” a matrix 𝐴 into a lower-triangular matrix L and an upper-triangular matrix U such that 𝐴=LU, which is known as the β€œ LU ” decomposition. As well as offering an attractive recipe for the matrix, writing a square matrix as the product of two triangular matrices can make subsequent calculations much easier to complete. The drawback of such an expression is that it is not always possible to derive, which some might consider to be a very significant drawback!

In this explainer, we will assume knowledge of elementary matrices and the LU decomposition method using Doolittle’s algorithm (or any other valid method), as there are separate explainers for these. Instead, this explainer will focus on demonstrating how to complete PLU decomposition in several examples. In practice, the completion of a PLU decomposition is very similar to the process used for LU decomposition, only with the possibility of having to use the row-swap operation and the associated elementary matrix (which is also a permutation matrix, in this case). We will first explain several examples where only one row swap is necessary and later we will give examples where more than one is needed.

Consider the following square matrix, which has the pivot entries highlighted: 𝐴=01βˆ’2301122.

To complete the LU decomposition of 𝐴, we would ordinarily choose to use a nonzero pivot entry in the first row to eliminate any pivot entries in the rows below. However, this is not possible with the matrix above because the entry in the first row and first column is zero. The remedial step is simply to use an elementary row matrix of the first type, which corresponds to a row-swap operation. In this case, we use the row-swap operation π‘Ÿβ†”π‘ŸοŠ§οŠ© which has the corresponding elementary matrix P=001010100.

Suppose that we were to create a new, row-equivalent matrix 𝐴 by multiplying the elementary matrix P on the left-hand side with the original matrix 𝐴. Then, the effect would be 𝐴=𝐴=00101010001βˆ’2301122=12230101βˆ’2.P

The pivots are now aligned in a way that is much more favorable, meaning that we could now operate with the new, row-equivalent matrix 𝐴 to complete the LU decomposition (of this new matrix and not the original matrix 𝐴, which does not have an LU decomposition). There is still the chance, of course, that we might need to use another elementary row operation of the first type, although we will only do so if absolutely necessary, preferring to use elementary row operations of the second and third types.

Focusing on the pivot entries of the matrix above, we see that to achieve upper-triangular form we need to at least eliminate the pivot entry in the second row of the matrix. This can be completed with the elementary row operation π‘Ÿβ†’π‘Ÿβˆ’3π‘ŸοŠ¨οŠ¨οŠ§. The corresponding elementary matrix and the inverse are as follows: 𝐸(βˆ’3)=100βˆ’310001,𝐸(βˆ’3)=𝐸(3)=100310001.

Given that these two matrices are inverses of each other, we have that 𝐸(3)𝐸(βˆ’3)=𝐼, meaning that we can inject this pairing on the left-hand side of the trivial equation 𝐴=𝐴. This gives the matrix equation 100310001100βˆ’31000112230101βˆ’2=12230101βˆ’2.

The leftmost matrix is in lower-triangular form, as we would expect. The second and third matrices can be combined using matrix multiplication to give 1003100011220βˆ’6βˆ’501βˆ’2=12230101βˆ’2.

The middle matrix is not yet in upper-triangular form, which means that we have not yet solved the problem properly. That being said, the only entry that is preventing the middle matrix from being in the required form is the pivot in the third row. If we can eliminate this, then we will have solved the problem. As is often the way in linear algebra, we are now faced with a choice as to how we proceed, as there are infinitely many combinations of elementary matrices that will achieve what we need. We choose first to multiply every entry in the third row by 6 using the row operation π‘Ÿβ†’6π‘ŸοŠ©οŠ©. The corresponding elementary matrix and inverse are 𝐷(6)=100010006,𝐷(6)=𝐷16=⎑⎒⎒⎣1000100016⎀βŽ₯βŽ₯⎦.

Given that these two matrices are each other’s multiplicative inverse, we can insert them between the left and middle matrices in the previous step: 100310001⎑⎒⎒⎣1000100016⎀βŽ₯βŽ₯⎦1000100061220βˆ’6βˆ’501βˆ’2=12230101βˆ’2.

By multiplying together the first pair of matrices and then separately multiplying together the second set of matrices, we obtain ⎑⎒⎒⎣1003100016⎀βŽ₯βŽ₯⎦1220βˆ’6βˆ’506βˆ’12=12230101βˆ’2.

The leftmost matrix is in lower-triangular form, as required, but the middle matrix is not yet in upper-triangular form. Thanks to the previous preparatory step, we can eliminate the pivot in the third row using the row operation π‘Ÿβ†’π‘Ÿ+π‘ŸοŠ©οŠ©οŠ¨, for which the corresponding elementary matrices are 𝐸(1)=100010011,𝐸(1)=𝐸(βˆ’1)=1000100βˆ’11.

Following the established method, we insert this pairing between the left and middle matrices of the previous step, giving ⎑⎒⎒⎣1003100016⎀βŽ₯βŽ₯⎦1000100βˆ’111000100111220βˆ’6βˆ’506βˆ’12=12230101βˆ’2.

By taking the product between the first pair of matrices and then taking the product between the second pair of matrices, we obtain the desired form: ⎑⎒⎒⎣1003100βˆ’1616⎀βŽ₯βŽ₯⎦1220βˆ’6βˆ’500βˆ’17=12230101βˆ’2.

The leftmost matrix is in lower-triangular form and the middle matrix is in upper-triangular form. We have therefore decomposed the row-equivalent matrix 𝐴 by the expression LU=𝐴, where LU=⎑⎒⎒⎣1003100βˆ’1616⎀βŽ₯βŽ₯⎦,=1220βˆ’6βˆ’500βˆ’17.

Since we originally defined the matrix 𝐴 as being equal to a permutation matrix multiplied by the original matrix as 𝐴=𝐴P, we can write the full expression as LUP=𝐴. This is known as the PLU decomposition of 𝐴.

Suppose we had obtained the general expression LUP=𝐴, where P was the product of elementary matrices of the first type. This means that P is a product of permutation matrices and, given that all permutation matrices are equal to their own multiplicative inverse, this means that P itself is equal to its own inverse. Therefore, the expression LUP=𝐴 can just as easily be written PLU=𝐴 if this is considered preferable.

Example 1: PLU Decomposition of a 3 Γ— 3 Matrix

Find the PLU factoring of the matrix 𝐴=121122211.

Answer

We begin by highlighting the pivots in each row. As we can see, there are two pivot entries below the pivot in the first row, both of which will need to be removed in order to achieve upper-triangular form: 𝐴=121122211.

The pivot in the second row can be removed using the row operation π‘Ÿβ†’π‘Ÿβˆ’π‘ŸοŠ¨οŠ¨οŠ§, for which the corresponding elementary matrices are 𝐸(βˆ’1)=100βˆ’110001,𝐸(βˆ’1)=𝐸(1)=100110001.

Now the trivial equation 𝐴=𝐴 can be multiplied on the left-hand side by this elementary matrix and its inverse, the product of which must be the identity matrix 𝐼 (hence why this does not affect the truth of the statement 𝐴=𝐴). The result is 100110001100βˆ’110001121122211=121122211, and taking the product of the two leftmost matrices gives the new matrix equation 100110001121001211=121122211.

The pivot entry in the second row now looks as though it may cause some complications, given that we would ideally want the pivot to appear in the second entry to help achieve upper-triangular form. Nonetheless, we do not have to focus on this yet, as we still need to remove the pivot entry in the third row. The obvious row operation is π‘Ÿβ†’π‘Ÿβˆ’2π‘ŸοŠ©οŠ©οŠ§, which has the elementary matrices 𝐸(βˆ’2)=100010βˆ’201,𝐸(βˆ’2)=𝐸(2)=100010201.

Taking the previous step and injecting the elementary matrix and inverse in between the first and second matrices give 100110001100010201100010βˆ’201121001211=121122211.

Combining the first pair of matrices and the second pair of matrices gives the simplified expression 1001102011210010βˆ’3βˆ’1=121122211.

The leftmost matrix is in lower-triangular form, as it should be, although the middle matrix is not in upper-triangular form. Indeed, we see now that it will be impossible to achieve upper-triangular form unless we swap the second and third rows in the middle matrix in the previous step. We can naively use the row operation π‘Ÿβ†”π‘ŸοŠ¨οŠ© and the elementary matrices PPP=100001010,==100001010.

Injecting into the previous step in the normal way gives the matrix equation 1001102011000010101000010101210010βˆ’3βˆ’1=121122211, which can be simplified by taking the product of the first pair of matrices and then separately doing the same with the second pair of matrices. The outcome is 1001012101210βˆ’3βˆ’1001=121122211.

The middle matrix is in upper-triangular form, as we were hoping to achieve. But something has gone terribly wrong, in that the leftmost matrix is now not in lower-triangular form. This is because we multiplied by one of the elementary matrices. However, we can actually take this equation and multiply both sides, on the left, by the permutation matrix P. This gives 1000010101001012101210βˆ’3βˆ’1001=100001010121122211.

We can take the product of the first and second matrices on the left-hand side, which will thankfully return a leftmost matrix with lower-triangular form. We also take the product of the two matrices on the right-hand side of the equation, giving 1002101011210βˆ’3βˆ’1001=100001010121122211.

We have therefore achieved the form LUP=𝐴, where LUP=100210101,=1210βˆ’3βˆ’1001,=100001010.

The magic of this trick is that we can temporarily break the β€œlower-triangular-ness” of the leftmost matrix in order to move closer to an upper-triangular form in the middle matrix. The leftmost matrix can then be moved back into upper-triangular form by applying the permutation matrix on the left-hand side. It is necessary that this be the case, as otherwise we would not be able to obtain upper-triangular form.

In the following example, we will demonstrate this technique, without applying it to a square matrix as we did in the previous two examples. It can be a matter of tedious debate among mathematics as to whether or not nonsquare matrices can be considered as either lower or upper triangular. For our well-being, we will not engage in such debates and will instead assume that it is acceptable for a nonsquare matrix to be either lower or upper triangular. As we will see, this changes our method very little, if it all, and it is still possible to find the PLU decomposition of a matrix 𝐴 whether or not it is square.

Example 2: PLU Decomposition of a 3 Γ— 5 Matrix

Find the PLU factoring of the matrix 𝐴=121212424112132.

Answer

We begin by highlighting the pivot entries of the matrix. We need to remove the pivots in the second and third rows with reference to the pivot in the first row: 𝐴=121212424112132.

An obvious choice for the first row operation is π‘Ÿβ†’π‘Ÿβˆ’2π‘ŸοŠ¨οŠ¨οŠ§, which will eliminate the pivot in the second row. The elementary matrices for this row operation are 𝐸(βˆ’2)=100βˆ’210001,𝐸(βˆ’2)=𝐸(2)=100210001.

Given that these two matrices are inverses of each other, we can multiply the trivial equation 𝐴=𝐴 on the left-hand side by this pair of matrices, which overall will change nothing but will begin moving towards the LU form that we require. The full equation is 100210001100βˆ’210001121212424112132=121212424112132, and we can take the product of the second and third matrices to give the simplified equation 100210001121210000βˆ’112132=121212424112132.

The left-hand matrix is in lower-triangular form but the middle matrix is not yet in upper-triangular form. Given that the pivot in the second row is in the final entry, we are likely to require a permutation matrix at some point in order to achieve upper-triangular form for the middle matrix. For the time being, we will continue by eliminating the pivot in the third row using the elementary row operation π‘Ÿβ†’π‘Ÿβˆ’π‘ŸοŠ©οŠ©οŠ§, for which the elementary matrices are 𝐸(βˆ’1)=100010βˆ’101,𝐸(βˆ’1)=𝐸(1)=100010101.

By inserting this into the previous step, we have 100210001100010101100010βˆ’101121210000βˆ’112132=121212424112132.

By taking the product of the first pair of matrices and then the product of the second pair of matrices, we find the much simplified form 100210101121210000βˆ’100011=121212424112132.

The leftmost matrix is in lower-triangular form but we are yet to manipulate the middle matrix into upper triangular form. We will be unable to achieve this without using the row-swap operation π‘Ÿβ†”π‘ŸοŠ¨οŠ©, which has the elementary matrices PPP=100001010,==100001010.

By inserting these matrices in the normal way, we have the expanded and yet equivalent equation 100210101100001010100001010121210000βˆ’100011=121212424112132.

We again take the product of the first pair of matrices and then the product of the second pair of matrices, giving the equation 10020111012121000110000βˆ’1=121212424112132.

The middle matrix is now in upper-triangular form but the left-hand matrix is no longer in lower-triangular form, which is a problem that we must fix. Fortunately, the fix is very easy and we just apply the permutation matrix P to both sides of the previous equation. This gives 10000101010020111012121000110000βˆ’1=100001010121212424112132.

The β€œlower-triangular-ness” can then be restored by taking the product of the first and second matrices, giving 10011020112121000110000βˆ’1=100001010121212424112132.

We have therefore obtained the PLU decomposition for the matrix 𝐴, with the full specification being encapsulated by the equation LUP=𝐴, where LUP=100110201,=12121000110000βˆ’1,=100001010.

Calculating the PLU decomposition of a matrix is a little different to finding the LU decomposition. The difference between the two is that the former is always possible whereas the latter is not. Once we understand how to proceed with calculating the LU decomposition of a matrix (if possible), there is only a touch of extra effort required to understand how to find the PLU decomposition. The situation becomes only slightly more complicated if more than one permutation matrix is required, which is a situation that we will explore later on in this explainer. For the moment, we will give one further example to practice this method.

Example 3: PLU Decomposition of a 4 Γ— 3 Matrix

Find the PLU factoring of the matrix 𝐴=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

Answer

Our approach begins by highlighting the pivot entries, all of which are in the first column of the matrix: 𝐴=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

To manipulate this matrix into upper-triangular form, we would first need to remove all of the pivot entries that are below the pivot entry in the first row. There are three of these entries to remove and we initially target the pivot in the second row. This can be turned into a zero entry with the row operation π‘Ÿβ†’π‘Ÿβˆ’π‘ŸοŠ¨οŠ¨οŠ§, for which the elementary matrices are 𝐸(βˆ’1)=⎑⎒⎒⎣1000βˆ’110000100001⎀βŽ₯βŽ₯⎦,𝐸(βˆ’1)=𝐸(1)=⎑⎒⎒⎣1000110000100001⎀βŽ₯βŽ₯⎦.

Although it is not particularly inspiring to state, it is nevertheless true that 𝐴=𝐴. Given that the two elementary matrices are inverses of each other, we could equally write 𝐸(1)𝐸(βˆ’1)𝐴=𝐴 since the product of the two leftmost matrices is the identity matrix 𝐼οŠͺ. Written out in full, this is ⎑⎒⎒⎣1000110000100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000βˆ’110000100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

Now, we take the product of the second and third matrices to find ⎑⎒⎒⎣1000110000100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣121001241321⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

The leftmost matrix is in lower-triangular form, which we will need to maintain to find either an LU or a PLU decomposition. This must be done while manipulating the middle matrix further toward upper-triangular form. We now choose to remove the pivot entry in the third row using the row operation π‘Ÿβ†’π‘Ÿβˆ’2π‘ŸοŠ©οŠ©οŠ§. The elementary matrices that we will need are 𝐸(βˆ’2)=⎑⎒⎒⎣10000100βˆ’20100001⎀βŽ₯βŽ₯⎦,𝐸(βˆ’2)=𝐸(2)=⎑⎒⎒⎣1000010020100001⎀βŽ₯βŽ₯⎦.

By slotting this pair of matrices into the previous step, we obtain the matrix equation ⎑⎒⎒⎣1000110000100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000010020100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10000100βˆ’20100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣121001241321⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

By taking the product of the first pair of matrices and then taking the product of the second pair of matrices, we obtain the simplified expression ⎑⎒⎒⎣1000110020100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣12100100βˆ’1321⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

The leftmost matrix remains in lower-triangular form and the middle matrix is getting closer to upper-triangular form. We can get closer to this with the row operation π‘Ÿβ†’π‘Ÿβˆ’3π‘ŸοŠͺοŠͺ, which has the corresponding elementary matrices 𝐸(βˆ’3)=⎑⎒⎒⎣100001000010βˆ’3001⎀βŽ₯βŽ₯⎦,𝐸(βˆ’3)=𝐸(3)=⎑⎒⎒⎣1000010000103001⎀βŽ₯βŽ₯⎦.οŠͺοŠͺοŠͺ

Placing these matrices into the previous step gives ⎑⎒⎒⎣1000110020100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000010000103001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣100001000010βˆ’3001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣12100100βˆ’1321⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

Taking the product of the first pair of matrices and then the product of the second pair of matrices gives ⎑⎒⎒⎣1000110020103001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣12100100βˆ’10βˆ’4βˆ’2⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

The leftmost matrix is still in lower-triangular form and the middle matrix is very close to upper-triangular form. That being said, there is no possible way of getting the middle matrix into upper-triangular form without having to use the first type of elementary row operation, in this particular case the row-swap operation π‘Ÿβ†”π‘ŸοŠ¨οŠͺ. The elementary matrices that we need are PPPοŠͺοŠͺοŠͺ=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦,==⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦.

Although it will temporarily change the leftmost matrix into being non-lower triangular, we insert this pair of matrices in the previous step in the normal way: ⎑⎒⎒⎣1000110020103001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣12100100βˆ’10βˆ’4βˆ’2⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

Taking the two matrix products gives ⎑⎒⎒⎣1000100120103100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1210βˆ’4βˆ’200βˆ’1001⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

The middle matrix is only one step away from being put into upper-triangular form. The difficulty is that now the leftmost matrix is not in lower-triangular form, which we will need to remedy before we continue with our method. This can be done by taking the equation in the step above and multiplying both sides, on the left, by the permutation matrix PοŠͺ: ⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000100120103100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1210βˆ’4βˆ’200βˆ’1001⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

If we take the product of the first pair of matrices, then we obtain an equation with a left-hand side that is in exactly the form we require: ⎑⎒⎒⎣1000310020101001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1210βˆ’4βˆ’200βˆ’1001⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

Now that the leftmost matrix is once again in lower-triangular form, we can proceed with our method in the normal way. There is one more pivot to eliminate in the fourth row before the middle matrix is in upper-triangular form. The final row operation is π‘Ÿβ†’π‘Ÿ+π‘ŸοŠͺοŠͺ and the elementary matrices for this are 𝐸(1)=⎑⎒⎒⎣1000010000100011⎀βŽ₯βŽ₯⎦,𝐸(1)=𝐸(βˆ’1)=⎑⎒⎒⎣10000100001000βˆ’11⎀βŽ₯βŽ₯⎦.οŠͺοŠͺοŠͺ

These elementary matrices are pumped into the previous step in the normal way: ⎑⎒⎒⎣1000310020101001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10000100001000βˆ’11⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000010000100011⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1210βˆ’4βˆ’200βˆ’1001⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

Taking the product between the two pairs of matrices now reveals the final solution to be ⎑⎒⎒⎣10003100201010βˆ’11⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1210βˆ’4βˆ’2001000⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣121122241321⎀βŽ₯βŽ₯⎦.

The leftmost matrix is in lower-triangular form and the second matrix is in upper-triangular form. Therefore, we have found the matrices LUP=⎑⎒⎒⎣10003100201010βˆ’11⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣1210βˆ’4βˆ’200βˆ’1000⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦ such that LUP=𝐴, hence achieving a PLU decomposition for the original matrix 𝐴.

We have now seen a range of examples that, while not being without challenge, have only required us to utilize one permutation matrix to achieve a PLU decomposition. Believably, it could be the case that we require more than one permutation matrix to achieve this form, so the question must be asked about how we manage this situation. In fact, the remedy for this is hardly more complicated than in any of the previous examples. The simplicity of our working will hinge on the fact that the product of two permutation matrices is another permutation matrix, which means that any two such matrices P and P can be lumped together as PPP=, where P is also a permutation matrix.

We will demonstrate this with the example matrix 𝐴=5101122βˆ’347.

Although it is not necessary, it is usually more pragmatic to have a 1 in the top left entry if possible. We can achieve this with the row-swap operation π‘Ÿβ†”π‘ŸοŠ§οŠ¨, which has the elementary matrices PPP=010100001,==010100001.

Although it will be slightly gratuitous, we will write the matrix equation 𝐴=𝐴 in full but with the above pair of matrices taken as a product to the left-hand side: 0101000010101000015101122βˆ’347=5101122βˆ’347.

By taking the product of the second and third matrices, we obtain 0101000011225101βˆ’347=5101122βˆ’347.

The problem with this expression is that the leftmost matrix is not in lower-triangular form, which we must remedy before we continue. Fortunately, the solution is very simple and we only have to multiply both sides of the equation on the left by the matrix P. Since this matrix is equal to its own inverse, we obtain 0101000010101000011225101βˆ’347=0101000015101122βˆ’347.

Taking the product of the first and second matrices will return the identity matrix 𝐼, given that P is equal to its own inverse. This gives the simplified equation 1225101βˆ’347=0101000015101122βˆ’347.

Now that the pivot entry in the top left is equal to 1, we can use this to eliminate the pivots in the second and third rows. Focusing on the second row, we can use the row operation π‘Ÿβ†’π‘Ÿβˆ’5π‘ŸοŠ¨οŠ¨οŠ§ and the corresponding elementary matrices 𝐸(βˆ’5)=100βˆ’510001,𝐸(βˆ’5)=𝐸(5)=100510001.

Inserting these into the previous step gives the equation 100510001100βˆ’5100011225101βˆ’347=0101000015101122βˆ’347.

By taking the product of the second and third matrices, we find that 10051000112200βˆ’9βˆ’347=0101000015101122βˆ’347.

This looks much more promising, because the leftmost matrix is now in lower-triangular form, which we will certainly try to preserve. We need to eliminate the remaining pivot in the third row of the second matrix, for which we employ the row operation π‘Ÿβ†’π‘Ÿ+3π‘ŸοŠ©οŠ©οŠ§. The elementary matrices are 𝐸(3)=100010301,𝐸(3)=𝐸(βˆ’3)=100010βˆ’301, and these are placed into the previous step in the usual way: 100510001100010βˆ’30110001030112200βˆ’9βˆ’347=0101000015101122βˆ’347.

We take the product of the first pair of matrices and the second pair of matrices in the normal way: 100510βˆ’30112200βˆ’901013=0101000015101122βˆ’347.

The leftmost matrix is in lower-triangular form, as required, although the second matrix is not yet in the upper-triangular form that we need. In fact, the only way to achieve this is with recourse to another row operation of the first type, in this case the row-swap operation π‘Ÿβ†”π‘ŸοŠ¨οŠ©. The permutation matrices for this step are PPP=100001010,==100001010.

Completing the usual step gives the equation 100510βˆ’30110000101010000101012200βˆ’901013=0101000015101122βˆ’347.

We then take the product of the first pair of matrices and the second pair of matrices, giving 100501βˆ’3101220101300βˆ’9=0101000015101122βˆ’347.

Although the second matrix is now in upper-triangular form, we have unfortunately broken the lower-triangular form that was previously held by the leftmost matrix. We can fix this by multiplying the equation above on both sides, on the left, by the permutation matrix P. This gives 100001010100501βˆ’3101220101300βˆ’9=1000010100101000015101122βˆ’347.

We have nearly completed our working. All that we need to do now is to take the product of the first two matrices on the left-hand side of the equation as well as the product of the first two matrices on the right-hand side of the equation. This gives 100βˆ’3105011220101300βˆ’9=0100011005101122βˆ’347.

The glory of our method is shown in full. The leftmost matrix is in lower-triangular form and the second matrix is in upper-triangular form. If we define LUP=100βˆ’310501,=1220101300βˆ’9,=010001100, then we have LUP=𝐴 and this means that we have found the correct PLU decomposition.

For the final example of this explainer, we will give another example where more than one permutation matrix is needed in order to complete the PLU decomposition. Ordinarily, when using row operations to complete any process (typically Gauss–Jordan elimination), it would be expected that several row-swap operations may be needed to shift the pivot variables into favorable positions. This technique is normally known as β€œpartial pivoting,” with full β€œpivoting” referring to column operations as well as row operations.

Example 4: PLU Decomposition of a 4 Γ— 5 Matrix

Which of the following is a correct PLU factorization of the matrix 𝐴=⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

  1. LUP=⎑⎒⎒⎣1000210001100011⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣1011401βˆ’21βˆ’800227000βˆ’1βˆ’5⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦
  2. LUP=⎑⎒⎒⎣1000210001100011⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣1011401βˆ’21βˆ’800227000βˆ’1βˆ’5⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣0001001001001000⎀βŽ₯βŽ₯⎦
  3. LUP=⎑⎒⎒⎣1000210001100011⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣1000001βˆ’21βˆ’800227000βˆ’1βˆ’5⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦
  4. LUP=⎑⎒⎒⎣1000110001100010⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣1011401βˆ’21βˆ’800227000βˆ’1βˆ’5⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦

Answer

We begin by highlighting the pivot entries of the matrix 𝐴=⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

The two pivot entries in the first and second rows are not in an ideal position, so it is likely that we will have to use row-swap operations to change this, which will mean that some permutation matrices will be required. We can use the row-swap operation π‘Ÿβ†”π‘ŸοŠ§οŠ© to take the pivot entry in the third row and place this in the top left corner, which is normally our preferred step if possible. The corresponding matrices are PPP=⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦,==⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦.

We take the β€œequation” 𝐴=𝐴 and multiply the left-hand matrix by the product of these two matrices (which is just the identity matrix 𝐼οŠͺ), as shown: ⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

By taking the product of the second and third matrices on the left-hand side, we will obtain a shortened version of this equation, giving ⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10114002120103βˆ’121030⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

Although the middle matrix is closer to being in the upper-triangular form that it originally was in, the left-hand matrix is not in lower-triangular form. We can correct this by multiplying both sides of the equation, on the left, by the permutation matrix P, giving ⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10114002120103βˆ’121030⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

Since the permutation matrix P is equal to its own inverse, the product of the two leftmost matrices is just the identity matrix 𝐼οŠͺ, which we do not need to write down. More simply, the equation above can be written as ⎑⎒⎒⎣10114002120103βˆ’121030⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

The pivot entry in the second row is still likely to cause us a problem, but we will return to this later. For the moment, we will remove the pivot entry in the fourth row, as this entry precludes the achievement of upper-triangular form. We use the row operation π‘Ÿβ†’π‘Ÿβˆ’2π‘ŸοŠͺοŠͺ and hence the elementary matrices 𝐸(βˆ’2)=⎑⎒⎒⎣100001000010βˆ’2001⎀βŽ₯βŽ₯⎦,𝐸(βˆ’2)=𝐸(2)=⎑⎒⎒⎣1000010000102001⎀βŽ₯βŽ₯⎦.οŠͺοŠͺοŠͺ

Taking the previous step and multiplying the left-hand side, on the left, with these two matrices give the equivalent equation ⎑⎒⎒⎣1000010000102001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣100001000010βˆ’2001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10114002120103βˆ’121030⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

The second and third matrices can be combined using matrix multiplication to give the simplified equation ⎑⎒⎒⎣1000010000102001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10114002120103βˆ’101βˆ’21βˆ’8⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

We are now in a better position as the leftmost matrix is in lower-triangular form and the second matrix is moving closer toward upper-triangular form. However, there is still an issue with the pivot entry in the second row, which is to the right of the pivots in the third and fourth rows. To correct this, we now employ the row-swap operation π‘Ÿβ†”π‘ŸοŠ¨οŠͺ which has the permutation matrices PPPοŠͺοŠͺοŠͺ=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦,==⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦.

By injecting these equations into the previous step, we have the rather garish equation ⎑⎒⎒⎣1000010000102001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10114002120103βˆ’101βˆ’21βˆ’8⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

By taking the product of the second and third equations, we obtain the slightly neater form ⎑⎒⎒⎣1000000100102100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1011401βˆ’21βˆ’80103βˆ’100212⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

The advantage of this form is that the middle matrix is nearer to being in upper-triangular form. The disadvantage is that the leftmost matrix is no longer in lower-triangular form. The remedy for this is to multiply both sides of the equation, on the left, by the permutation matrix PοŠͺ: ⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000000100102100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1011401βˆ’21βˆ’80103βˆ’100212⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣1000000100100100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0010010010000001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

By taking the product of the first two matrices on the left-hand side and separately taking the product of the first two matrices on the right-hand side, we obtain the vastly preferable equation ⎑⎒⎒⎣1000210000100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1011401βˆ’21βˆ’80103βˆ’100212⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

The expression above looks very promising, since the leftmost matrix is a lower-triangular matrix and the second matrix is nearly in upper-triangular form. Additionally, the first matrix on the right-hand side of the equation is still a permutation matrix (even though it is no longer an elementary matrix). We now aim to quickly complete the process by moving the remaining pivot entries into the appropriate position. The first row operation is π‘Ÿβ†’π‘Ÿβˆ’π‘ŸοŠ©οŠ©οŠ¨ and the elementary matrices are 𝐸(βˆ’1)=⎑⎒⎒⎣100001000βˆ’1100001⎀βŽ₯βŽ₯⎦,𝐸(βˆ’1)=𝐸(1)=⎑⎒⎒⎣1000010001100001⎀βŽ₯βŽ₯⎦.

These two matrices are then inserted into the previous step in the normal way: ⎑⎒⎒⎣1000210000100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000010001100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣100001000βˆ’1100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1011401βˆ’21βˆ’80103βˆ’100212⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

Completing the matrix multiplication for the first pair of matrices and then for the second pair of matrices gives the simplified form ⎑⎒⎒⎣1000210001100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1011401βˆ’21βˆ’80022700212⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

Note that the leftmost matrix is in lower-triangular form and the second matrix is one step away from being in upper-triangular form. The last step is to use the row operation π‘Ÿβ†’π‘Ÿβˆ’π‘ŸοŠͺοŠͺ and the elementary matrices 𝐸(βˆ’1)=⎑⎒⎒⎣10000100001000βˆ’11⎀βŽ₯βŽ₯⎦,𝐸(βˆ’1)=𝐸(1)=⎑⎒⎒⎣1000010000100011⎀βŽ₯βŽ₯⎦.οŠͺοŠͺοŠͺ

Then, the previous step can be written as ⎑⎒⎒⎣1000210001100001⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1000010000100011⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣10000100001000βˆ’11⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1011401βˆ’21βˆ’80022700212⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

The final step needed is to bring together the two pairs of matrices on the left side of the above equation, giving the final form ⎑⎒⎒⎣1000210001100011⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣1011401βˆ’21βˆ’800227000βˆ’1βˆ’5⎀βŽ₯βŽ₯⎦=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦⎑⎒⎒⎣0103βˆ’1002121011421030⎀βŽ₯βŽ₯⎦.

We have therefore found the three matrices LUP=⎑⎒⎒⎣1000210001100011⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣1011401βˆ’21βˆ’800227000βˆ’1βˆ’5⎀βŽ₯βŽ₯⎦,=⎑⎒⎒⎣0010000110000100⎀βŽ₯βŽ₯⎦ such that LUP=𝐴, which means that we have found the PLU decomposition of the matrix. therefore, the correct option is A.

Just as with LU decomposition, finding the PLU decomposition of a matrix is ultimately a matter of understanding the elementary row operations and their counterpart elementary matrices. Given that each elementary matrix is very similar to the identity matrix of appropriate order, each elementary matrix is easy to combine with another matrix by matrix multiplication, with the effects being identical to performing whatever the associated row operation. This means that, even with matrices having large orders, finding the LU or PLU decomposition is essentially just a matter of determining a useful series of elementary row operations, with little extra effort required to turn these into the corresponding elementary matrices. Once one of the two types of decomposition is found, the original matrix 𝐴 is expressed in terms of matrices that either are in triangular form (and hence have much more useful algebraic properties) or are permutation matrices (which are very well understood and have convenient properties).

Key Points

  • The LU decomposition of a matrix uses elementary row operations of the second and third types, but it is not always possible to find. If at any point a row operation of the first type is needed, then the PLU decomposition must be calculated instead.
  • It is always possible to write a matrix 𝐴 in terms of a lower-triangular matrix L, an upper-triangular matrix U, and a permutation matrix P, such that LUP=𝐴.
  • In the PLU decomposition, the permutation matrix P can be expressed as a product of all of the elementary matrices of the first type, in order.
  • For any permutation matrix P, the inverse is PP=. One consequence of this is that the PLU decomposition can alternatively be expressed as PLU=𝐴, which is often considered favorable.

Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.