Proof of Gaussian elimination/Why does it work

First notice that any combination of elementary row operation(s) is invertible.

Let $Ax=b$ a system of $m$ linear equations in $n$ unknowns, and let $C$ be an invertible $m\times m$ matrix, then $Ax=b$ is equivalent to $CAx=Cb.$ (equivalent means they have the same solution set.)

Proof:

Let $K$ be the solution set of $Ax=b$, and $K'$ of $CAx=Cb$.
$\Longrightarrow:$ Given $k\in K$, $Ak = b$, then multiply $C$ at left on both side we get $CAk=Cb$, so $k\in K'$. So $K\subseteq K'$.

$\Longleftarrow:$ Given $k'\in K'$, $CAk'=Cb$, but since $C$ is invertible, $(C^{-1}C)Ak'=(C^{-1}C)b\implies Ak'=b,$ so $k'\in K$. So $K'\subseteq K,$

which complete the proof.

Any matrix equation is just a system of equations. Consider the example below,

$$ \left( \begin{array} & 0 &0 & 1\\ 1 &1 & 1\\ 0 &1 & 1\\ \end{array}\right) \left( \begin{array} & x\\ y\\ z\\ \end{array}\right) = \left( \begin{array} & 1\\ 2\\ 3\\ \end{array}\right), $$

which is the same as,

$$z=1$$ $$x+y+z=2$$ $$y+z=3.$$

You are probably familiar with the fact that when working with a system of equations you can add multiples of the equations together without affecting the solution. The truth of this statement is related to Euclid's common notions which are in fact axioms. This is why adding and subtracting the rows of a matrix do not affect the solution.

Furthermore you can exchange the rows of the matrix and the constant vector without affecting the solution because they yield the same equations for $x,y,$ and $z$.

The matrix equation below has the same solutions as the original matrix equation because it induces the same system of equations for the variables $x,y,z$. $$ \left( \begin{array} & 1 &1 & 1\\ 0 &1 & 1\\ 0 &0 & 1\\ \end{array}\right) \left( \begin{array} & x\\ y\\ z\\ \end{array}\right) = \left( \begin{array} & 2\\ 3\\ 1\\ \end{array}\right), $$

The matrix equation below has the same solutions as the original matrix because it induces equations which are linear combinations of the equations induced by the original matrix. $$ \left( \begin{array} & 1 &1 & 2\\ 1 &3 & 3\\ 0 &1 & 1\\ \end{array}\right) \left( \begin{array} & x\\ y\\ z\\ \end{array}\right) = \left( \begin{array} & 3\\ 8\\ 1\\ \end{array}\right), $$