Proposition 2   Suppose that $A=LU$ is an LU factorization, and let $L_{ij}$ denote the entries of $L$ . Then, the row reduction $A\stackrel{\rho}{\Longrightarrow} U$ is accomplished by the following sequence $\rho$ of $\tfrac{1}{2}n(n-1)$ row replacement operations:

In the most general case, one has to employ row exchange operations.

The LU decomposition of a given matrix $A$ is useful for the solution of the systems of linear equations of the form $Ax = b$ . Indeed, it suffices to first solve the linear system $Ly=b$ , and second, to solve the system $Ux=y$ . This two-step procedure is easy to implement, because owing to the lower and upper-triangular nature of the matrices $L$ and $U$ , the required row operations are determined, more or less, directly from the entries of $L$ and $U$ . Indeed, the first step,$$ [\, L\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, I \; y \,]$$ a sequence of row operations $\rho_1$ , and the second step$$ [\, U\; y\, ] \stackrel{\rho_2}{\Longrightarrow} [\, E \; x_0 \,]$$ a sequence of row operations $\rho_2$ , are exactly the same row operations one has to perform to row reduce $A$ directly to reduced echelon form $E$ :$$ [\, A\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, U\; y \, ] \stackrel{\rho_2}{\Longrightarrow} [\, E\; x_0 \, ] .$$ Note: $x_0$ is the particular solution of $Ax=b$ that sits in the rightmost colulmn of the augmented matrix at the termination of the row-reduction algorithm.