gaussian elimination

Solving a system of equations at once, by simply augmenting the matrix and applying elementary row operations to both sides.

---

The familliar basic process:
e.g.:

$$\begin{array}{rl}x+2y+z& =2\\ 3x+8y+z& =12\\ 4y+z& =2\end{array}$$

We can solve it using gaussian elimination by hand, by eliminating variables, until only one is left:
$II-III$

$$\begin{array}{rl}3x-8y+z-4y-z& =12-2\\ 3x-4y& =10\end{array}$$

$I-III$

$$\begin{array}{rl}x-2y+z-4y-z& =2-2\\ x-2y& =0\end{array}$$

Now we can solve for $x$:

$$\begin{array}{rl}3x-4y-2x+4y& =10\\ x& =10\end{array}$$

For $y$:

$$\begin{array}{rl}10-2y& =0\\ y& =5\end{array}$$

And for $z$:

$$\begin{array}{rl}4\cdot 5+z& =2\\ z& =-18\end{array}$$

Gaussian elimination with matrices

Representing systems of equations as matrices is how every computer solves them.

e.g. continuing with the example from the introduction, we can pull out the coefficients into a matrix:

$$\underset{A}{\underbrace{\left[\begin{array}{ccc}1& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]}}\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=\underset{b}{\underbrace{\left[\begin{array}{c}2\\ 12\\ 2\end{array}\right]}}$$

Now again, we want to eliminate variables from the equation.
$a_{1,1}$ is our first so called pivot. We want to knock out $x$ from the second equation / row by subtracting $3$ times the first row:

$$\to \left[\begin{array}{cccc}1& 2& 1& 2\\ 0& 2& -2& 6\\ 0& 4& 1& 2\end{array}\right]$$

We apply the same operations to the vector $b$, which we carry along with us in the augmented matrix.
Step $a_{2,1}$ is done and there’s nothing to do in step $a_{3,1}$ as $x$ is already $0$.
Now clearing out $a_{3,2}$ (subtracting $2$ times the newly obtained second from the third row):

$$\to \left[\begin{array}{cccc}\boxed{1}& 2& 1& 2\\ 0& \boxed{2}& -2& 12\\ 0& 0& \boxed{5}& -10\end{array}\right]$$

We now have an upper triangular matrix $U$ in row echelon form, with three pivot columns along the main diagonal. And we have a new vector $c$ after the elimination.
The determinant of this matrix would be the product of the main diagonal.

Gaussian elimination vs Gauss-Jordan

Gaussian elimination → row echelon form.
Gauss-Jordan → reduced row echelon form.
RREF lets you read off solutions directly (no back-substitution) and compute inverses (by doing $[A\mid I]\to [I\mid A^{-1}]$, because for invertible matrices, RREF of $A$ is $I$ see below).
Here we just do Gaussian elimination + back-substitution:

Now we do “back-substitution” of the values into a system of equations:

$$\begin{array}{rl}x+2y+z& =1\\ y-2z& =12\\ 5z& =-10\end{array}$$

And solve the S.O.E. in reverse order:
$z=-2,y=1,x=2$

The steps we took can be expressed as multiplying $A$ with some elimination matrix (elementary matrix) $E$:

$$\begin{array}{r}\underset{E_{2,1}}{\underbrace{\left[\begin{array}{ccc}1& 0& 0\\ -3& 1& 0\\ 0& 0& 1\end{array}\right]}}\left[\begin{array}{ccc}1& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]=\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]\\ \underset{E_{3,2}}{\underbrace{\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -2& 1\end{array}\right]}}\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]=\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 0& 5\end{array}\right]\end{array}$$ $$\begin{array}{r}{E}_{2,1}(E_{3,2}A)=U\\ (E_{2,1}{E}_{3,2})A=U\\ EA=I\end{array}$$

Column operations are not allowed, as they would change the equations we are trying to solve.

Finding the Inverse with Gauss-Jordan elimination

Computing inverses via RREF

For invertible $A\in {\mathbb{R}}^{n\times n}$, the RREF of the augmented matrix $[A\mid I]$ is $[I\mid A^{-1}]$:

$$\left[\begin{array}{cccccc}{a}_{11}& \cdots & a_{1n}& 1& & 0\\ ⋮& & ⋮& & \ddots & \\ a_{n1}& \cdots & a_{nn}& 0& & 1\end{array}\right]\stackrel{\text{RREF}}{\to }\left[\begin{array}{cccccc}1& & 0& a_{11}^{\prime }& \cdots & a_{1n}^{\prime }\\ & \ddots & & ⋮& & ⋮\\ 0& & 1& a_{n1}^{\prime }& \cdots & a_{nn}^{\prime }\end{array}\right]$$

where $A^{-1}=(a_{ij}^{\prime })$.

This is the Gauss-Jordan algorithm: apply row operations to $[A\mid I]$ until the left side becomes $I$; the right side becomes $A^{-1}$.

Link to original

Gauss-Jordan

$$\underset{A}{\underbrace{\left[\begin{array}{cc}1& 3\\ 2& 7\end{array}\right]}}\underset{A^{-1}}{\underbrace{\left[\begin{array}{cc}a& c\\ b& d\end{array}\right]}}=\underset{I}{\underbrace{\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]}}$$

A is invertible, since $det(A)$ is positive / the vectors are pointing in different directions.

Now finding the Inverse is just like solving two systems of linear equations!

$$\begin{gathered} \left[\begin{array}{cc}1& 3\\ 2& 7\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}1\\ 0\end{array}\right] \\ \left[\begin{array}{cc}1& 3\\ 2& 7\end{array}\right]\left[\begin{array}{c}c\\ d\end{array}\right]=\left[\begin{array}{c}0\\ 1\end{array}\right] \end{gathered}$$

By the gauss-jordan method, we can solve them at once, by augmenting the matrix, i.e. carrying the right side of the equations with us / applying the same elimination steps to it. Our goal is to transform $A$ into $I$. By the end of the elimination, the augmented part will have turned into the inverse matrix:

$$\begin{gathered} \left[\begin{array}{cccc}1& 3& 1& 0\\ 2& 7& 0& 1\end{array}\right]\stackrel{E_{2,1}}{\to }\left[\begin{array}{cccc}1& 3& 1& 0\\ 0& 1& -2& 1\end{array}\right]\stackrel{E_{1,2}}{\to }\left[\begin{array}{cccc}1& 0& 7& -1\\ 0& 1& -2& 1\end{array}\right] \\ {A}^{-1}=\left[\begin{array}{cc}7& -1\\ -2& 1\end{array}\right] \end{gathered}$$

So we applied an elimination $E=E_{2,1}{E}_{1,2}$ to $[AI]$, such that $A$ turns into the inverse, so by definition, $E$ is the inverse:

$$E\left[AI\right]=\left[I{A}^{-1}\right]$$

We discovered it step by step, as we multiplied the partial $E$‘s with the identity.
$EA=I\to E=A^{-1}$

My first intuition was to view it like this:
It’s just like the usual transformations when solving equations
($\underset{(I)}{\frac{A}{A}}(A^{-1})=\underset{(A^{-1})}{\frac{I}{A}}$, just imagine matrices being divisible).

Link to original

References

Gilbert Strang OCW lecture Lecture 2: Elimination with matrices