Is it always possible to row reduce any matrix to echelon form? 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?
 A: 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$.
