Definition · applies to square matrices · also called LU decomposition with partial pivoting, LUP decomposition

Undergraduate

Consider a square matrix $A$. A PLU decomposition of $A$ is a factorization $A = P L U$, where $P$ is a permutation matrix (the identity matrix with its rows reordered), $L$ is lower triangular with ones on its diagonal, and $U$ is upper triangular.

Examples

Worked examples

  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : $P = I$, with $L$ and $U$ as in the LU decomposition Undergraduate
    The matrix \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) has an LU decomposition, so $P = I$ works. With partial pivoting, the rows are exchanged first instead, because $4$ is larger than $2$.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $P = I$, with $L$ and $U$ as in the LU decomposition Undergraduate
    The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric positive definite, so it has every decomposition in the table, including a Cholesky decomposition. Its eigendecomposition, Schur decomposition, Jordan normal form, and singular value decomposition all coincide, and its polar and Toeplitz decompositions are trivial.
  • The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) : $P = I$, $L = I$, $U = A$ Undergraduate
    $A$ is upper triangular, so its LU decomposition is $I \cdot A$, and its QR decomposition is $I \cdot A$. $A$ is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N$.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : $P = A$, $L = I$, $U = I$ Undergraduate
    The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) has no LU decomposition, but it has the PLU decomposition $A = A \cdot I \cdot I$, because $A$ is itself the permutation matrix that exchanges the two rows.

Properties

  • Every square matrix has a PLU decomposition, unlike an LU decomposition, which need not exist.
  • Gaussian elimination with row exchanges computes a PLU decomposition: $P$ records the row exchanges, $U$ is the resulting echelon form, and $L$ records the multiples of rows that were subtracted.
  • The PLU decomposition of a matrix is not unique in general, because different row exchanges can be chosen. Partial pivoting, which brings the entry of largest absolute value in each column to the pivot position, makes the multipliers in $L$ at most $1$ in absolute value, which limits the growth of rounding errors.

Notes

Some authors write $P A = L U$ instead of $A = P L U$. The two conventions use inverse permutation matrices, since $P^{-1} = P^{\top}$.

Numerical libraries (for example, lu in MATLAB and scipy.linalg.lu in Python) compute a PLU decomposition with partial pivoting, not a plain LU decomposition.

Distinctions involving this term

  • Types of matrix decompositions: A matrix decomposition writes a matrix in terms of simpler matrices. Most are products: LU, PLU, and Cholesky decompositions use triangular factors, QR and singular value decompositions use orthogonal factors, and eigendecompositions, Schur decompositions, and Jordan normal forms are similarities $A = P M P^{-1}$ to a simpler matrix $M$ (diagonal, triangular, or made of Jordan blocks). In contrast, the Jordan–Chevalley decomposition is a sum of commuting diagonalizable and nilpotent parts, and the Toeplitz decomposition is a sum $H + K$ of a symmetric matrix $H$ and a skew-symmetric matrix $K$.

All definitions · All distinctions · All examples