I am self-studying Linear Algebra by Hoffman & Kunze.

Exercise 6 in Section 1.2: "Prove that if two homogenous systems of linear equations in two unknowns have the same solutions, then they are equivalent."

I am trying to solve this problem by induction (see the first bullet point below).

I am hoping to solve this problem using only the information provided in the book thus far. In this text, two systems are equivalent if each equation in one system can be written as a linear combination of equations in the other system. So far the text has defined the following phrases: solution of a linear system of equations, equivalent systems, and homogenous system of equations. It has not yet covered linear dependence.

Some notes on previously asked questions:

  • This question seems to be asking the same thing, and while the OP was able to solve it with the hints given in the comments, they did not post the solution. I am trying to solve this problem by induction on the number of equations in one of the systems of equations, as suggested in the comments of that post. My trouble arises when attempting to invoke the inductive hypothesis (IH). Starting with $N+1$ equations, I cannot simply add two equations together to obtain an equivalent system of $N$ equations in order to invoke the IH. The new system of $N$ equations may have solutions that the system with $N+1$ did not.
  • This post asks the same question, but the answer uses material and intuition not yet covered by the text at this point.
  • I have found this question answered on this blog, but with a different approach.

marked as duplicate by Brahadeesh, GNUSupporter 8964民主女神 地下教會, José Carlos Santos linear-algebra Sep 30 '18 at 16:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Have you done elementary row operations, row reduction, echelon form? $\endgroup$ – Gerry Myerson Dec 25 '14 at 6:18
  • $\begingroup$ No, the text has not covered those topics at this point. They are covered in the next section. $\endgroup$ – khoda Dec 25 '14 at 19:04
  • $\begingroup$ Induction is not appropriate for this exercise because you need no more than two equations for the linear combination. $\endgroup$ – Maurice P Sep 30 '18 at 16:43

Let the two homogenous systems of equations in two variables with same solutions be $$ \begin{alignat}{10} a_{11}x_1 &{}+{}& a_{12}x_2 &{}={}& 0 \\ \vdots \ \ \ & & \vdots\ \ \ & & \vdots \\ a_{m1}x_1 &{}+{}& a_{m2}x_2 &{}={}& 0 \end{alignat}\tag{1} $$ and $$ \begin{alignat}{10} b_{11}x_1 &{}+{}& b_{12}x_2 &{}={}& 0 \\ \vdots \ \ \ & & \vdots\ \ \ & & \vdots \\ b_{n1}x_1 &{}+{}& b_{n2}x_2 &{}={}& 0 \end{alignat}\tag{2} $$ where the $a_{ij}$'s and $b_{ij}$'s are real numbers.

Case I: The solution set is all of $\mathbb{R}^2$.

In particular, $(1,0)$ and $(0,1)$ satisfy every equation in (1) and (2), so each equation is the zero equation: $$ 0x_1 + 0x_2 = 0. $$ So, clearly each equation in (1) can be written as a linear combination of the equations in (2) and vice-versa. So, (1) and (2) are equivalent.

Case II: The solution set is a line in $\mathbb{R}^2$.

We can assume that there is at least one equation in each system that is not the zero equation. Without loss of generality (wlog), assume that $$ a_{11}x_1 + a_{12} x_2 = 0\tag{i} $$ is not the zero equation. Again, wlog let $a_{11} \neq 0$. Then, the set of solutions to (i) is of the form $$ \{ ( -a_{12}t/a_{11} ,t ) : t \in \mathbb{R} \}. $$ Therefore, the solution to every nonzero equation in each of the two systems must be of the same form. Let $$ c_{i1}x_1 + c_{i2}x_2 = 0 \tag{ii} $$ be any other nonzero equation in any of the two systems. Then, $$ -c_{i1}a_{12}t/a_{11} + c _{i2}t = 0. $$ This shows that $c_{i1} \neq 0$, for otherwise only $t = 0$ satisfies the above equation, which is a contradiction. Hence, putting $t=1$ and rearranging, we get $$ c_{i2}/c_{i1} = a_{i2}/a_{i1}.\tag{iii} $$ Hence, every equation (ii) is a multiple of (i) (think about this!). Since our initial choice to pick (i) from (1) was arbitrary (we could have started with a non zero eqation from (2) and repeated the same process), we have proved that (1) and (2) are equivalent.

Case III: There is a unique solution, $x_1 = x_2 = 0$.

In particular, there exists a pair of equations in each system which are not multiples of one another and such that $(1,0)$ and $(0,1)$ are not solutions to the respective equations. So, wlog assume that the first two equations in (1) satisfy these criteria. This implies that $a_{11} \neq 0$ and $a_{22} \neq 0$. Again, let (ii) be a generic equation from any of the two systems. We will show that it can be expressed as a linear combination of the first two equations of (1).

Observe that if $a_{11}a_{22} - a_{12}a_{21} = 0$, then we get that the first two equations of (1) are multiples of each other by a similar argument as used arguing about (iii). Hence, $a_{11}a_{22} - a_{12}a_{21} \neq 0$.

Next, let $$ t_1 = \frac{1}{a_{11}a_{22} - a_{12}a_{21}} (a_{22}c_{i1} - a_{21}c_{i2}) $$ and $$ t_2 = \frac{1}{a_{11}a_{22} - a_{12}a_{21}} (-a_{12}c_{i1} + a_{11}c_{i2}). $$ Then, a simple calculation shows that $$ \begin{align} c_{i1} &= t_1 a_{11} + t_2 a_{12}\\ c_{i2} &= t_1 a_{21} + t_2 a_{22}. \end{align} $$ Thus, every equation in (1) and (2) is a linear combination of the first two equations of (1). We could have repeated the process in the other direction wlog, starting from a pair of equations in (2), and so we have shown that (1) and (2) are equivalent.


Not the answer you're looking for? Browse other questions tagged or ask your own question.