📂Matrix Algebra

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.