Why does elimination give exactly the solution to a system.

Question

I've been thinking about why elimination gives exactly the solution to a system.

What I think is that to solve any equation or systems of equations you must take "if and only if" steps. Things like $x=2 \implies x^2=4 \implies x=-2,2$ do not work because if and only if steps are not taken particularly in the first step. Things like multiply by a nonzero constant is an if and only if step because $f(x)=cx$ is injective. As so is $f(x)=x+c$.

I realize that if $a=b$ and $c=d$ then of course $a+c=b+d$. However $a+c=b+d$ does not imply $a=b$ and $c=d$. So adding equations is not an if and only if step.

However the way we do elimination, we keep $n$ equations, the number of equations we started with, and somehow this process is an "if and only if step".

I think that elimination gives the correct answer (we perform if and only if steps) because the elementary matrices being multiplied on both sides of $Ax=b$ at each step are invertible.

Do you have a reason, preferably more simpler, as to why elimination does not produce extraneous solutions.

Answer 1

Adding two equations and keeping the new one as well as one of the old ones is an "if and only if" step. For your example:

If we have the system {$a=b$ and $c=d$} and add them together and keep one of the old ones, we get the system {$a=b$ and $a+c=b+d$}. From this we can easily recover the original system by simple subtraction.

The same argument holds for mutiplication with a non-zero number.

Let me know if this answers your question.