PLU Decomposition
Definition 1 2
For permutation matrices $P^{T}$ and invertible matrices $A \in \mathbb{R}^{n \times n}$, their matrix product $P^{T} A$’s LU decomposition is referred to as the PLU Decomposition $A$. Since $P$ is a permutation matrix, it’s an orthogonal matrix, i.e., $P^{-1} = P^{T}$, and thus can be represented as follows. $$ P^{T} A = LU \iff A = PLU $$
Description
Algorithm of LU decomposition: Let’s assume $(a_{ij}) \in \mathbb{R}^{n \times n}$ is an invertible matrix.
Step 1. $k = 1$
Substitute $u_{1j} = a_{1j}$ and compute $\displaystyle l_{i1} = {{1} \over {u_{11}}} a_{i1}$.
Step 2. $k = 2, 3, \cdots , n-1$
- Step 2-1. Compute the following. $$ u_{kk} = a_{kk} - \sum_{s = 1}^{k-1} l_{ks} u_{sk} $$
- Step 2-2. For $j = k+1 , k+2 , \cdots , n-1$, compute the following. $$ u_{kj} = a_{kj} - \sum_{s = 1}^{k-1} l_{ks} u_{sj} $$
- Step 2-3. For $i = k+1 , k+2 , \cdots , n-1$, compute the following. $$ l_{ik} = {{ 1 } \over {u_{kk} }} \left\{ a_{ik} - \sum_{s = 1}^{k-1} l_{is} u_{sk} \right\} $$
Step 3. For $k = n$, compute the following. $$ u_{nn} = a_{nn} - \sum_{s = 1}^{n-1} l_{ns} u_{sn} $$
To perform LU decomposition of a matrix as above, it is necessary to be able to take the inverse of either $u_{11} = a_{11}$ or $u_{kk}$. However, even $$ A = \begin{bmatrix} 0 & 3 \\ 2 & 1 \end{bmatrix} $$ a matrix like this cannot be applied to the algorithm. Therefore, by multiplying some permutation matrix $P^{T}$, the $A$ is entirely expressed as $PLU$, which is called PLU decomposition. Of course, whether it’s left or right, rows or columns doesn’t matter, so $$ A P^{T} = LU \iff A = LUP $$ can be set, and it’s also fine to read it as LUP decomposition.