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.

Definition of equivalence from the text :

Let us say that two systems of linear equations are equivalent if each equation in each system is a linear combination of the equations in the other system.

• 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
• @Christian Blatter I really don't get this although it may be because I am just starting Linear Algebra. I was stuck with the same question as well and I think I came up with a proof yet I don't know if it is wrong or not. can you check it? math.stackexchange.com/questions/2844153/… – user500668 Jul 8 '18 at 6:42

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.

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.

At the point in the text where this exercise occurs, row operations have not been introduced, so I am providing an answer that does not require them.

Breaking the answer down into cases is not inelegant for this exercise because all but one of the cases have obvious proofs.

Because there are only two unknowns, say $$x$$ and $$y,$$ and the systems are homogeneous, each equation has the form $$A_1x + A_2y = 0$$ where the coefficients $$A_1$$ and $$A_2$$ are scalars. Hence, each equation represents a line through the origin unless $$A_1$$ and $$A_2$$ are zero. There are three cases:

The first case is that all the coefficients are zero. Then the systems are trivially equivalent.

The second case is that all the lines are the same so that the solution is the set of points on that line. Then all the equations are scalar multiples of each other, so the systems again are equivalent.

The last case is that at least two lines are different so that the solution is the origin. Let \begin{align} A_{11}x + A_{12}y = 0\\ A_{21}x + A_{22}y = 0 \end{align} be two different lines in the first system so that $$A_{11}A_{22} - A_{12}A_{21} \ne 0$$ and $$B_1x + B_2y = 0$$ be any equation in the second system. We want to show that scalars $$c_1$$ and $$c_2$$ exist such that $$B_1x + B_2y = c_1(A_{11}x + A_{12}y) + c_2(A_{21}x + A_{22}y).$$ That equation leads to the system \begin{align} A_{11} c_1 + A_{21}c_2 = B_1\\ A_{12} c_1 + A_{22}c_2 = B_2\end{align} which has the solution \begin{align} c_1 & = \frac{B_1 A_{22} - B_2 A_{21}}{A_{11}A_{22} - A_{12}A_{21}}\\\\ c_2 & = \frac{A_{11} B_2 - A_{12} B_1}{A_{11}A_{22} - A_{12}A_{21}}.\end{align} Hence, each equation in each system is a linear combination of the equations in the other system. Thus, the systems are equivalent.

Consider the space of vectors in $$\mathbb R^n$$.

Then it is known that $$m \le n$$ vectors of it $$\bf v_1, \cdots, \bf v_m$$ will span a subspace of at most $$\mu \le m$$ dimensions.

It is also known that their null-space, i.e. the space spanned by the vectors normal to them, is of dimension $$n-\mu$$.
The solutions $$\bf x$$ to the system $$\bf v_1 \cdot \bf x=0, \; \bf v_2 \cdot \bf x =0, \; \cdots,\; \bf v_m\cdot \bf x =0$$ are in fact all the vectors pertaining to respective the null-space.

If two sets of vectors $$\bf v_1, \cdots, \bf v_m$$ and $$\bf w_1, \cdots, \bf w_m$$ have the same set of null vectors, i.e. the same nullspace, then the $$\bf v$$'s and $$\bf w$$'s span the same subspace, so they share the same base, can be expressed one as a linear combination of the other. In that sense they are equivalent.

In the other direction, if they are equivalent by spanning the same subspace, then they have the same null-space and so the same solutions to the homogeneous system.