In this explainer, we will learn how to find the PLU (permutation, lower-, and upper-triangular matrices) decomposition (factorization) 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 and an upper-triangular matrix such that , 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:
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
Suppose that we were to create a new, row-equivalent matrix by multiplying the elementary matrix on the left-hand side with the original matrix . Then, the effect would be
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 . The corresponding elementary matrix and the inverse are as follows:
Given that these two matrices are inverses of each other, we have that , meaning that we can inject this pairing on the left-hand side of the trivial equation . This gives the matrix equation
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
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 . The corresponding elementary matrix and inverse are
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:
By multiplying together the first pair of matrices and then separately multiplying together the second set of matrices, we obtain
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
Following the established method, we insert this pairing between the left and middle matrices of the previous step, giving
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:
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 , where
Since we originally defined the matrix as being equal to a permutation matrix multiplied by the original matrix as , we can write the full expression as . This is known as the PLU decomposition of .
Suppose we had obtained the general expression , where was the product of elementary matrices of the first type. This means that is a product of permutation matrices and, given that all permutation matrices are equal to their own multiplicative inverse, this means that itself is equal to its own inverse. Therefore, the expression can just as easily be written if this is considered preferable.
Example 1: PLU Decomposition of a 3 × 3 Matrix
Find the PLU factoring of the matrix
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:
The pivot in the second row can be removed using the row operation , for which the corresponding elementary matrices are
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 and taking the product of the two leftmost matrices gives the new matrix equation
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 , which has the elementary matrices
Taking the previous step and injecting the elementary matrix and inverse in between the first and second matrices give
Combining the first pair of matrices and the second pair of matrices gives the simplified expression
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
Injecting into the previous step in the normal way gives the matrix equation 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
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 . This gives
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
We have therefore achieved the form , where
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
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:
An obvious choice for the first row operation is , which will eliminate the pivot in the second row. The elementary matrices for this row operation are
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 and we can take the product of the second and third matrices to give the simplified equation
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
By inserting this into the previous step, we have
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
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
By inserting these matrices in the normal way, we have the expanded and yet equivalent equation
We again take the product of the first pair of matrices and then the product of the second pair of matrices, giving the equation
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 to both sides of the previous equation. This gives
The “lower-triangular-ness” can then be restored by taking the product of the first and second matrices, giving
We have therefore obtained the PLU decomposition for the matrix , with the full specification being encapsulated by the equation , where
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
Answer
Our approach begins by highlighting the pivot entries, all of which are in the first column of the matrix:
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
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 since the product of the two leftmost matrices is the identity matrix . Written out in full, this is
Now, we take the product of the second and third matrices to find
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 . The elementary matrices that we will need are
By slotting this pair of matrices into the previous step, we obtain the matrix equation
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
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 , which has the corresponding elementary matrices
Placing these matrices into the previous step gives
Taking the product of the first pair of matrices and then the product of the second pair of matrices gives
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
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:
Taking the two matrix products gives
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 :
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:
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
These elementary matrices are pumped into the previous step in the normal way:
Taking the product between the two pairs of matrices now reveals the final solution to be
The leftmost matrix is in lower-triangular form and the second matrix is in upper-triangular form. Therefore, we have found the matrices such that , 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 and can be lumped together as , where is also a permutation matrix.
We will demonstrate this with the example matrix
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
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:
By taking the product of the second and third matrices, we obtain
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 . Since this matrix is equal to its own inverse, we obtain
Taking the product of the first and second matrices will return the identity matrix , given that is equal to its own inverse. This gives the simplified equation
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 and the corresponding elementary matrices
Inserting these into the previous step gives the equation
By taking the product of the second and third matrices, we find that
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 . The elementary matrices are and these are placed into the previous step in the usual way:
We take the product of the first pair of matrices and the second pair of matrices in the normal way:
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
Completing the usual step gives the equation
We then take the product of the first pair of matrices and the second pair of matrices, giving
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 . This gives
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
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 then we have 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
Find the PLU factoring of the matrix
Answer
We begin by highlighting the pivot entries of the matrix
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
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:
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
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 , giving
Since the permutation matrix 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
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 and hence the elementary matrices
Taking the previous step and multiplying the left-hand side, on the left, with these two matrices give the equivalent equation
The second and third matrices can be combined using matrix multiplication to give the simplified equation
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
By injecting these equations into the previous step, we have the rather garish equation
By taking the product of the second and third equations, we obtain the slightly neater form
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 :
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
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
These two matrices are then inserted into the previous step in the normal way:
Completing the matrix multiplication for the first pair of matrices and then for the second pair of matrices gives the simplified form
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
Then, the previous step can be written as
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
We have therefore found the three matrices such that , which means that we have found the PLU decomposition of the matrix.
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 , an upper-triangular matrix , and a permutation matrix , such that .
- In the PLU decomposition, the permutation matrix can be expressed as a product of all of the elementary matrices of the first type, in order.
- For any permutation matrix , the inverse is . One consequence of this is that the PLU decomposition can alternatively be expressed as , which is often considered favorable.
