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.

  • 5
    $\begingroup$ What's the book's definition of "equivalent"? Usually it simply means having the same set of solutions... $\endgroup$ Jun 18, 2011 at 9:56
  • $\begingroup$ @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? $\endgroup$
    – Marek
    Jun 18, 2011 at 10:02
  • $\begingroup$ @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. $\endgroup$ Jun 18, 2011 at 12:30

4 Answers 4


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

  • $\begingroup$ 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. $\endgroup$ Jun 18, 2011 at 12:35
  • $\begingroup$ 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. $\endgroup$
    – Marek
    Jun 18, 2011 at 12:37
  • $\begingroup$ 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! $\endgroup$ Jun 18, 2011 at 12:56
  • $\begingroup$ @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/… $\endgroup$
    – user500668
    Jul 8, 2018 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.

  • $\begingroup$ Thank you for your answer, I do not quite get the last step. Could you explain a bit more? $\endgroup$
    – xyz
    Jun 10, 2021 at 11:04

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.


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .