Gaussian Elimination

50. Gaussian Elimination

Convert a matrix into its row echelon form (REF) or reduced row echelon form (RREF)

\begin{matrix} 𝑎_{11} 𝑥_{1} + 𝑎_{12} 𝑥_{2} + \dots + 𝑎_{1 𝑛} 𝑥_{𝑛} = 𝑏_{1} \\ 𝑎_{21} 𝑥_{1} + 𝑎_{22} 𝑥_{2} + \dots + 𝑎_{2 𝑛} 𝑥_{𝑛} = 𝑏_{2} \\ ⋮ \\ 𝑎_{𝑚 1} 𝑥_{1} + 𝑎_{𝑚 2} 𝑥_{2} + \dots + 𝑎_{𝑚 𝑛} 𝑥_{𝑛} = 𝑏_{𝑚} \end{matrix}

𝐴 = [\begin{matrix} 𝑎_{11} & 𝑎_{12} & \dots & 𝑎_{1 𝑛} & 𝑏_{1} \\ 𝑎_{21} & 𝑎_{22} & \dots & 𝑎_{2 𝑛} & 𝑏_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ & 𝑏_{3} \\ 𝑎_{2 𝑚 1} & 𝑎_{𝑚 2} & \dots & 𝑎_{𝑚 𝑛} & 𝑏_{𝑚} \end{matrix}]

Eliminate the element in the $𝑖$ -th of the $𝑘$ -th column ( $𝑘 > 𝑖$ )

𝑅_{𝑘} \leftarrow 𝑅_{𝑘} - \frac{𝑎_{𝑘 𝑖}}{𝑎_{𝑖 𝑖}} 𝑅_{𝑖}

Where

Example

\begin{matrix} 2 𝑥_{1} + 3 𝑥_{2} = 5 \\ 4 𝑥_{1} + 5 𝑥_{2} = 5 \end{matrix}

[\begin{matrix} 2 & 3 & 5 \\ 4 & 5 & 6 \end{matrix}]

$𝑅_{𝑘} \leftarrow 𝑅_{𝑘} - \frac{𝑎_{𝑘 𝑖}}{𝑎_{𝑖 𝑖}} 𝑅_{𝑖}$

$𝑅_{𝑘} \leftarrow 𝑅_{𝑘} - \frac{𝑎_{21}}{𝑎_{11}} 𝑅_{𝑖}$

$𝑅_{2} \leftarrow 𝑅_{2} - \frac{4}{2} 𝑅_{1}$

$𝑅_{2} \leftarrow 𝑅_{2} - 2 \times 𝑅_{1}$

[\begin{matrix} 2 & 3 & 5 \\ 4 - 2 \times 2 & 5 - 2 \times 3 & 6 - 2 \times 5 \end{matrix}]

Simplifies to:

[\begin{matrix} 2 & 3 & 5 \\ 0 & - 1 & - 4 \end{matrix}]

System is now:

\begin{aligned} 2 𝑥_{1} + 3 𝑥_{2} & = 5 \\ - 1 𝑥_{2} & = - 4 \end{aligned}

\begin{matrix} - 1 𝑥_{2} = - 4 \\ 𝑥_{2} = 4 \end{matrix}

Substitute:

\begin{matrix} 2 𝑥_{1} + 3 (4) = 5 \\ 2 𝑥_{1} + 12 = 5 \\ 𝑥_{1} = - 3.5 \end{matrix}

Solution:

\begin{matrix} 𝑥_{1} = - 3.5 \\ 𝑥_{2} = 4 \end{matrix}