# Proving that two systems of linear equations are equivalent if they have the same solutions

I've just begun to work learn Linear Algebra on my own through Hoffman and Kunze's book and the first problem set already has a question that I can't solve:

Prove that if two homogeneous systems of linear equations in two unknowns have the same solutions, then they are equivalent.

I can't seem to figure out how to prove this without resorting to case work where you account for the cases where one of the coefficients are zero and when both are.

Is there an elegant way to prove in general that when two systems of linear equations have the same solutions, they are equivalent? The converse is obvious enough though.

-
What's the book's definition of "equivalent"? Usually it simply means having the same set of solutions... –  Hans Lundmark Jun 18 '11 at 9:56
@Lundmark: here it is probably an equivalence relation on the matrices associated with the equations, defined by some row/column operations. So the thing to prove is that those operations don't change the solution space. Is this what you had in mind, @Herman? –  Marek Jun 18 '11 at 10:02
@Marek: Well, the way Hoffman and Kunze define equivalent is that each equation in one system is a linear combination of equations in the other. –  Herman Chau Jun 18 '11 at 12:30

We have to prove the following: Given any solution set $L\subset{\mathbb R}^2$ then any two homogeneous systems $$\Sigma: \qquad a_i x+ b_i y=0 \qquad (1\leq i\leq n)$$ having the solution set $L$ can be transformed into each other by means of row operations.

The solution set $L$ can be one of the following:

(i) $\ \{0\}$,

(ii) a one-dimensional subspace $<r>$ with $r=(p,q)\ne 0$,

(iii) all of ${\mathbb R}^2$.

Ad (i): If $0$ is the only solution of $\Sigma$ then not all row vectors $c_i=(a_i,b_i)$ can be multiples of one and the same vector $c\ne0$. So there are two equations $a_1 x+b_1 y=0$, $a_2 x+ b_2 y=0$ in $\Sigma$ with linearly independent row vectors $(a_i, b_i)$, and by means of row operations one can transform these into $\Sigma_0: \ x=0, y=0$. Further row operations will remove all remaining equations from $\Sigma$. We conclude that in this case all systems $\Sigma$ are equivalent to $\Sigma_0$.

Ad (ii): The System $\Sigma$ has to contain at least one equation with $c_i=(a_i,b_i)\ne 0$. We claim that all equations with $c_i\ne 0$ are individually equivalent to $\Sigma_1: \ q x -p y=0$. So in this case any given $\Sigma$ is equivalent to $\Sigma_1$. To prove the claim we may assume $a_i\ne 0$. Now $r\in L$ implies $a_i p+ b_i q=0$, and as $r\ne 0$ we must have $q\ne 0$. This implies $b_i=-a_i p/q$, so multiplying the equation $a_i x+ b_i y=0$ by $q/a_i$ gives $\Sigma_1$.

Ad (iii): This case is trivial. All rows of $\Sigma$ are $0$.

-
Yes, I can prove it by breaking it down into the same three cases and showing it for each of them separately. However, it should be possible to prove it generally (two NxM systems have the same solutions iff they are equivalent), in which case proving it case by case doesn't work. –  Herman Chau Jun 18 '11 at 12:35
Any reason for working in two dimensions and writing out all the solution cases? In my mind the general proof is as simple as this: let $W$ be the solution space and $W'$ its orthogonal complement. Define a matrix $C$ that acts as identity on $W'$ and annihilates $W$. Now, by Gauss elimination, both $A$ and $B$ can be brought into this form and therefore are equivalent to $C$ and therefore to each other. –  Marek Jun 18 '11 at 12:37
Well, I'm just beginning to learn Linear Algebra and the exercise in the book only asked to prove it in two dimensions, presumably because you're not expected to be able to prove it in general yet. I don't really understand what an orthogonal complement or even what is meant by "annihilating" a solution space, so I guess I'll refer back to your answer once I get a bit farther in my textbook. Thanks! –  Herman Chau Jun 18 '11 at 12:56

If equivalence means "that each equation in one system is a linear combination of equations in the other" then the proof is almost trivial by the method of Gauss-Jordan elimination which is an application of Gauss elimination to make a system of equations equivalent to a diagonal form (upper triangular first, then diagonal), arriving at the solution by performing elementary row operations. You can work backwards and start up from solution of your system written as a diagonal matrix and apply a different set of elementary row operations to arrive at different systems of equations which are equivalent since each equation (row of your matrix) of one can be traced back to be written as a linear combination of the other by construction.

-

Let there be two systems, if the each equation of the second system is a Linear Combination of the first system then every solution of the first system is also the solution of the second system and if each equation of the first system is a Linear Combination of the second system the every solution of the second system is also the solution of the first system.

Now, let us consider the following two homogeneous systems in two unknowns ($x_1, x_2$), the solutions to both the systems are same. $A_{11}x_1+A_{12}x_2=0 ... A_{n1}x_1+A_{n2}x_2=0$ and $B_{11}x_1+B_{12}x_2=0 ... B_{n1}x_1+B_{n2}x_2=0$.

Select scalars $C_1, C_2, ..., C_n$. Multiply $k^{th}$ equation of the first system by $C_k$ and then add column-wise (so that variable is common) to get the following $(C_1A_{11}+...+C_nA_{n1})x_1+(C_1A_{12}+...+C_nA_{n2})x_2=0$.

Comparing this equation with all the equations of the second system and also utilising the fact given that both the systems have the same solutions, we get

$C_1A_{11}+...+C_nA_{n1}=B_{11}, B_{21},..., B_{n1}$ and $C_1A_{12}+...+C_nA_{n2}=B_{12}, B_{22},..., B_{n2}$,

which proves that the second system is a Linear Combination the the first system. Similar way we can show that the first system is a Linear Combination of the second system and thus conclude that both the systems are Equivalent.

-