Theorem: If an elementary row operation is applied to the augmented matrix $[A|\mathbf{b}]$ to obtain $[A'|\mathbf{b}']$, then the systems $A\mathbf{x} = \mathbf{b}$ and $A'\mathbf{x} = \mathbf{b}'$ have the same solution set.

Proof: We consider each type of elementary row operation separately. Let the original system have equations $E_1, E_2, \ldots, E_m$ and let $\mathbf{x}^*$ be any solution.

Case 1: Row Switching ($R_i \leftrightarrow R_j$)

Interchanging rows $i$ and $j$ simply reorders the equations. If $\mathbf{x}^*$ satisfies all equations in the original order, it clearly satisfies them in the new order. Conversely, any solution to the reordered system satisfies the original system. Thus the solution sets are identical.

Case 2: Row Multiplication ($R_i \to cR_i$ where $c \neq 0$)

Suppose equation $E_i$ is $a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n = b_i$. After the operation, equation $E_i$ becomes: $ca_{i1}x_1 + ca_{i2}x_2 + \cdots + ca_{in}x_n = cb_i$

If $\mathbf{x}^*$ satisfies the original equation, then: $a_{i1}x_1^* + a_{i2}x_2^* + \cdots + a_{in}x_n^* = b_i$

Multiplying both sides by $c$ yields: $ca_{i1}x_1^* + ca_{i2}x_2^* + \cdots + ca_{in}x_n^* = cb_i$

so $\mathbf{x}^*$ satisfies the new equation. Conversely, if $\mathbf{x}^*$ satisfies the new equation, dividing by $c$ (which is nonzero) shows it satisfies the original equation. All other equations remain unchanged.

Case 3: Row Addition ($R_i \to R_i + cR_j$ where $i \neq j$)

Let equation $E_i$ be $\sum_{k=1}^n a_{ik}x_k = b_i$ and equation $E_j$ be $\sum_{k=1}^n a_{jk}x_k = b_j$.

The new equation $E_i'$ is: $\sum_{k=1}^n (a_{ik} + ca_{jk})x_k = b_i + cb_j$

If $\mathbf{x}^*$ satisfies both $E_i$ and $E_j$, then: $\sum_{k=1}^n a_{ik}x_k^* = b_i \quad \text{and} \quad \sum_{k=1}^n a_{jk}x_k^* = b_j$

Adding $c$ times the second equation to the first: $\sum_{k=1}^n a_{ik}x_k^* + c\sum_{k=1}^n a_{jk}x_k^* = b_i + cb_j$ $\sum_{k=1}^n (a_{ik} + ca_{jk})x_k^* = b_i + cb_j$

Thus $\mathbf{x}^*$ satisfies $E_i'$. Since equation $E_j$ is unchanged, $\mathbf{x}^*$ satisfies the new system.

Conversely, suppose $\mathbf{x}^*$ satisfies the new system with $E_i'$ and $E_j$. Then $\mathbf{x}^*$ satisfies: $\sum_{k=1}^n (a_{ik} + ca_{jk})x_k^* = b_i + cb_j \quad \text{and} \quad \sum_{k=1}^n a_{jk}x_k^* = b_j$

Subtracting $c$ times the second from the first: $\sum_{k=1}^n a_{ik}x_k^* = b_i$

so $\mathbf{x}^*$ satisfies the original equation $E_i$ and hence the original system.

Since each row operation is reversible by an operation of the same type, and each preserves solutions, the solution sets must be identical. ∎