**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.