Theorem: Row Equivalent Matrix for Homogeneous System has same Solutions

Let $\mathbf A$ be a matrix in the matrix space $\map {\MM_\R} {m, n}$ such that:
:$\mathbf A \mathbf x = \mathbf 0$
represents a homogeneous system of linear equations.
Let $\mathbf H$ be row equivalent to $\mathbf A$.
Then the solution set of $\mathbf H \mathbf x = \mathbf 0$ equals the solution set of $\mathbf A \mathbf x = \mathbf 0$.
That is:
:$\mathbf A \sim \mathbf H \implies \set {\mathbf x: \mathbf A \mathbf x = \mathbf 0} = \set {\mathbf x: \mathbf H \mathbf x = \mathbf 0}$
where $\sim$ represents row equivalence.

Proof:
Let:
{{begin-eqn}}
{{eqn | l = \alpha_{1 1} x_1 + \alpha_{1 2} x_2 + \ldots + \alpha_{1 n} x_n
      | r = 0
      | c = 
}}
{{eqn | l = \alpha_{2 1} x_1 + \alpha_{2 2} x_2 + \ldots + \alpha_{2 n} x_n
      | r = 0
      | c = 
}}
{{eqn | o = \vdots
}}
{{eqn | l = \alpha_{m 1} x_1 + \alpha_{m 2} x_2 + \ldots + \alpha_{m n} x_n
      | r = 0
      | c = 
}}
{{end-eqn}}
be the system of equations to be solved.
Suppose the elementary row operation of multiplying one row $i$ by a non-zero scalar $\lambda$ is performed.
Recall, the $i$th row of the matrix represents the $i$th equation of the system to be solved.
Then this is logically equivalent to multiplying the $i$th equation on both sides by the scalar $\lambda$:
{{begin-eqn}}
{{eqn | l = \alpha_{i 1} x_1 + \alpha_{i 2} x_2 + \ldots + \alpha_{i n} x_n
      | r = 0
}}
{{eqn | ll= \to
      | l = \lambda \alpha_{i 1} x_1 + \lambda \alpha_{i 2} x_2 + \ldots + \lambda \alpha_{i n} x_n
      | r = 0
      | c = $r_i \to \lambda r_i$
}}
{{end-eqn}}
which clearly has the same solutions as the original equation.
Suppose the elementary row operation of adding a scalar multiple of row $i$ to another row $j$ is performed.
Recall that the $i$th and $j$th row of the matrix represent the $i$th and $j$th equation in the system to be solved.
{{explain|Woolly. The matrix (by which I presume you mean $\mathbf A$) contains the coefficients and so no part of it "represents" an equation. The act of multiplying $\mathbf x$ by it to obtain $\mathbf b$ represents the equation.}}
Thus this is logically equivalent to manipulating the $i$th and $j$th equations as such:
{{begin-eqn}}
{{eqn | l = \alpha_{i 1} x_1 + \alpha_{i 2} x_2 + \ldots + \alpha_{i n} x_n
      | r = 0
      | c = 
}}
{{eqn | l = \alpha_{j 1} x_1 + \alpha_{j 2} x_2 + \ldots + \alpha_{j n} x_n
      | r = 0
      | c = 
}}
{{eqn | ll= \to
      | l = \alpha_{j 1} x_1 + \alpha_{j 2} x_2 + \ldots + \alpha_{j n} x_n + \lambda \paren {\alpha_{i 1} x_1 + \alpha_{i 2} x_2 + \ldots + \alpha_{i n} x_n}
      | r = 0
      | c = $r_i \to r_i + \lambda r_j$
}}
{{end-eqn}}
As both sides of equation $i$ are equal to each other, this operation is simply performing the same act on both sides of equation $j$.
This clearly will have no effect on the solution set of the system of equations.
Suppose the elementary row operation of interchanging row $i$ and row $j$ is performed.
Recall that the $i$th and $j$th row of the matrix represent the $i$th and $j$th equation in the system to be solved.
Then, interchanging row $i$ and row $j$ is logically equivalent to switching the $i$th equation and the $j$th equation of the system to be solved.
But clearly the system containing the following two equations:
{{begin-eqn}}
{{eqn | l = \alpha_{i 1} x_1 + \alpha_{i 2} x_2 + \cdots + \alpha_{i n} x_n
      | r = 0
      | c = 
}}
{{eqn | l = \alpha_{j 1} x_1 + \alpha_{j 2} x_2 + \cdots + \alpha_{j n} x_n
      | r = 0
      | c = 
}}
{{end-eqn}}
has the same solution set as a system instead containing the following two equations:
{{begin-eqn}}
{{eqn | l = \alpha_{j 1} x_1 + \alpha_{j 2} x_2 + \cdots + \alpha_{j n} x_n
      | r = 0
      | c = 
}}
{{eqn | l = \alpha_{i 1} x_1 + \alpha_{i 2} x_2 + \cdots + \alpha_{i n} x_n
      | r = 0
      | c = $r_i \leftrightarrow r_j$
}}
{{end-eqn}}
Hence the result, by the definition of row equivalence.
{{qed}}
{{proofread}}
Category:Linear Algebra
ix7loxpm1evprncf15v9560q41jslzx