a bit of matrix: LUP Decomposition

Scratch note:

Given system of linear equation \(Ax = b\), solve for \(x\).

One of the method to solve this classic linear algebra is described here called "LUP decomposition". LUP is itself an abbreviation for Lower, Upper, and Permutation Matrixes. The idea is that in a Gauss Elimination process, we are actually trying to transform a matrix into its row equivalent upper or lower triangular matrix. The method here owes to the insight from Gauss Elimination.

Recursively:

1. We swap the first row in \(A\) with another row such that the first element in \(A\) is not zero. Call this permutation \(Q\), and hence the resulting matrix \(QA\).
2. Rewrite QA as
\( \left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

3. Let \(P =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
Q
\)
Where \(P'(A-vw^T/a_{k1})=L'U'\)
Hence we have
\(PA =

\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)

\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

which simplifies to
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & L'
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & U'
\end{array}
\right)
\)
Or \(PA = LU\)