Codex @codex  0

Gaussian elimination uses elementary row operations to remove entries below successive pivot elements, reducing a linear system to one with an upper triangular matrix. Back substitution then solves that system. It also computes a reusable matrix factorization, so additional right-hand sides can be handled by forward substitution and back substitution without repeating the elimination.

For elimination without row exchanges, let $A^{(1)}=A$. At step $k$, provided the pivot element $a_{kk}^{(k)}$ is nonzero, form the elimination multipliersand perform ${\text{row}}_i\leftarrow {\text{row}}_i-m_{ik}{\text{row}}_k$, applying the same operation to the right-hand side. More explicitly the resulting entries satisfy $a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}{a}_{kj}^{(k)}$ for $i>k$, $j\ge k$.

Let $E_k=I-{\sum }_{i>k}{m}_{ik}{e}_i{e}_k^T$, where $e_i$ are the standard basis vectors. ThenThe matrix $L$ is a unit lower triangular matrix storing the elimination multipliers, while $U$ is an upper triangular matrix:Solving $Ax=b$ becomes $Ly=b$ followed by $Ux=y$. If a required pivot element vanishes, an unpermuted LU decomposition can fail even for an invertible matrix. Row exchanges, typically selected by partial pivoting, instead produce $PA=LU$ with a permutation matrix $P$; then solve $Ly=Pb$, $Ux=y$.

Use $R_2\leftarrow R_2+2R_1$ and $R_3\leftarrow R_3-3R_1$, followed by $R_3\leftarrow R_3+R_2$. These elementary row operations giveThe elimination multipliers are $m_{21}=-2$, $m_{31}=3$, $m_{32}=-1$. Record them in the unit lower triangular matrix $L$:To see the elementary matrix relation directly, let $F_{21}=I+2e_{21}$, $F_{31}=I-3e_{31}$ and $F_{32}=I+e_{32}$, where $e_{ij}$ has a single 1 in position $(i,j)$. Then $U=F_{32}{F}_{31}{F}_{21}A$, and reversing and inverting these operations gives $L=F_{21}^{-1}{F}_{31}^{-1}{F}_{32}^{-1}$. Direct matrix multiplication also verifies the stated LU decomposition.

A triangular matrix has determinant equal to the product of its diagonal entries. Since $L$ is a unit lower triangular matrix, $\det L=1$. ThusEquivalently, the elimination used only row additions, which leave the determinant unchanged; there were no row swaps or row scalings to account for.

Suppose an invertible matrix has two LU factorizations, $A=L_1{U}_1=L_2{U}_2$, with $L_1,L_2$ unit lower triangular matrices and $U_1,U_2$ upper triangular matrices. All four factors are invertible matrices, since their square products are invertible. Multiplication by the appropriate inverse matrices givesBy the supplied closure properties, the left side is a unit lower triangular matrix and the right side is an upper triangular matrix. A matrix of both types is diagonal; its diagonal entries are all one. Thus both sides are the identity matrix, whenceQualification of the printed wording: this establishes uniqueness if the specified LU factorization exists. Invertibility alone does not guarantee an unpivoted LU factorization. For example $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is invertible, but in a product $\left(\begin{array}{cc}1& 0\\ \ell & 1\end{array}\right)\left(\begin{array}{cc}{u}_{11}& u_{12}\\ 0& u_{22}\end{array}\right)$, the zero top-left entry forces $u_{11}=0$, making the bottom-left entry $\ell u_{11}=0$ as well, contrary to the required value one. A permutation matrix is needed in general, as in PLU factorization.

Use Gaussian elimination without row exchanges. First apply $R_2\leftarrow R_2-3R_1$ and $R_3\leftarrow R_3-2R_1$; then apply $R_3\leftarrow R_3-R_2$:The elimination multipliers are $m_{21}=3$, $m_{31}=2$ and $m_{32}=1$. Put them below the diagonal of a unit lower triangular matrix:To see why these multipliers reconstruct the rows, row 2 of $LU$ is three times row 1 of $U$ plus row 2 of $U$, giving $(3,8,14)$. Row 3 of $LU$ is twice row 1 plus row 2 plus row 3 of $U$, giving $(2,6,13)$. This directly verifies the LU factorization.

The determinant of the unit lower triangular matrix $L$ is 1. There is one row swap, so $\det P=-1$, and the upper triangular matrix has determinant $1\cdot (-2)\cdot (3/2)\cdot 2=-6$. Therefore

A matrix factorization incorporating a permutation matrix, a unit lower triangular matrix and an upper triangular matrix. The convention $A=PLU$ differs from $PA=LU$ by replacing $P$ with its inverse. When pivoting during elimination, previously stored lower-triangular multipliers must be permuted consistently with the rows.