I was reading my Linear Algebra book and found this:
- Reduce $A$ to an echelon form $U$ by a sequence of row replacement operations, if possible.
- Place entries in L such that the same sequence of row operations reduces L to I.
Step 1 is not always possible, but when it is, the argument above shows that an LU factorization exists.
I want to know: when it's not possible to row reduce a matrix to an echelon form?
If $A$ is regular and if you allow pivoting (see below) there always exists a LU decomposition:
$$PA = LU.$$
with $P$ being the product of pivot matrices, L being a lower-right triangle matrix with 1-elements on the diagonal, and $U$ an upper-right triangle matrix.
Pivoting is the process of searching for the maximum element in each column for the $i-th$ LU-step:
Find $k$, such that $$|a_{ki}| = \max_{j≥i}|a_{ji}|.$$
The pivot matrix $P^{ki}$ then switches the $i$-th and $k$-th row. $P$ is simply the product of such matrices.
Pivoting also considers the case of $0$-elements on the diagonal, that might arise during the LU decomposition. E.g:
$$A=\pmatrix{1 & 4 & 2 \\ 2 & 8 & 1 \\ 1 & 2 & 1} ⇒ A^{(1)} = \pmatrix{1 & 4 & 2 \\ 0 & 0 & -3 \\ 0 & -2 & -1}$$
Here the pivot matrix needs to switch row 2 and 3: $$P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{pmatrix}$$
edit: I forgot to mention: Since $A$ is supposed to be regular there will always be an element $|a_{ki}|\neq 0$.