= Solution
<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 multipliers>
$$
m_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}},\qquad i=k+1,\ldots,n,
$$
and 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\geq k$.
Let $E_k=I-\sum_{i>k}m_{ik}e_i e_k^T$, where $e_i$ are the <standard basis> <vectors>. Then
$$
U=E_{n-1}\cdots E_1A,\qquad
A=LU,\qquad L=E_1^{-1}\cdots E_{n-1}^{-1}.
$$
The <matrix> $L$ is a <unit lower triangular matrix> storing the <elimination multipliers>, while $U$ is an <upper triangular matrix>:
$$
L=\begin{pmatrix}
1&0&\cdots&0\\
m_{21}&1&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
m_{n1}&m_{n2}&\cdots&1
\end{pmatrix},\qquad
U=\begin{pmatrix}
u_{11}&u_{12}&\cdots&u_{1n}\\
0&u_{22}&\cdots&u_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&u_{nn}
\end{pmatrix}.
$$
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$.
Back to article page
