Definition of equation operations on a linear system

Theorem: Applying any of the three equation operations to a linear system produces a new system that is equivalent to the original — i.e., both systems have exactly the same solution set.

Proof sketch: Each operation is reversible:

• Swapping equations can be undone by swapping them back
• Scaling by $c \neq 0$ can be undone by scaling by $1/c$
• Replacing $E_i$ with $E_i + cE_j$ can be undone by replacing with $E_i - cE_j$

Since each operation is invertible, no solutions are lost or gained.

Why this matters: This theorem justifies Gaussian elimination. We can transform a system into a simpler equivalent form (echelon form) and solve that instead of the original system.