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

Question

From Exercise 6 of Sec 1.2 of Linear Algebra by K.Hoffman and R.Kunze.
Equivalence is defined as follows:

Two systems of linear equations are equivalent if each equation in each system is a linear combination of the equations in the other system.

I did some research, but most answers I found on math.stackexchange.com either use some serious math like ranks or null spaces, or are merely "intuitive". I'm curious how to formalize the proof, with concepts previously defined.

Thx.

More specifically --
$A_{11}x_1+A_{12}x_2=0$, $A_{21}x_1+A_{22}x_2=0$;
$B_{11}x_1+B_{12}x_2=0$, $B_{21}x_1+B_{22}x_2=0$;
We are asked to find $c_{11},c_{12},c_{21},c_{22}$ such that:
$A_{11}c_{11}+A_{21}c_{12}=B_{11}$;
$A_{12}c_{11}+A_{22}c_{12}=B_{12}$;
$A_{11}c_{21}+A_{21}c_{22}=B_{21}$;
$A_{12}c_{21}+A_{22}c_{22}=B_{22}$; (Sorry about the mess...I don't know how to type systems of equations...)
I can't convince myself in formal language the existence of such $c$s.

Since this problem appears at the beginning of the book, I assume there's a rather rookie proof. I suppose I have to express the $c$s in terms of the given quantities. But how?

Answer 1

This time I finally get it done without using the words 'determinant', 'rank' and so on. Special thanks to @orangeskid, and thank you all.

---

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

[Proof] A proof by contradiction.

Assuming the negation of the conclusion , suppose systems $\bf{A}$ and $\bf{B}$ are not equivalent. Accoording to the symmetry of the problem, this is the same as asserting that the first equation of $\bf{A}$: $$A_1x_1+A_2x_2=0$$ is not a linear combination of the equations of $\bf{B}$: $$B_{i1}x_1+B_{i2}x_2=0, (i=1,2,...,k).$$
Case 1. $A_1\neq0,(\forall i)\ B_{i1}=0$. In this case, $(x_1,x_2)=(x_1\neq0,0)$ solves $\bf{B}$ but not $\bf{A}$.
Case 2. $A_1=0,A_2\neq0,(\forall i)\ B_{i1}=B_{i2}=0$. In this case, $\bf{B}$ yields $(x_1,x_2)=(x_1\in\mathbb{R},x_2\in\mathbb{R})$ while $\bf{A}$ yields $(x_1,x_2)=(x_1\in\mathbb{R},0)$.
Case 3. $A_1\neq0,(\exists i)\ B_{i1}\neq0,(\exists j)\ B_{j2}\neq0$. In this case, there exist $c_1,c_2,...,c_k$ such that $$A_1=c_1B_{11}+c_2B_{21}+...+c_kB_{k1};$$ and $$A_2\neq c_1B_{12}+c_2B_{22}+...+c_kB_{k2}.$$ Noticing that $A_1x_1+(c_1B_{12}+c_2B_{22}+...+c_kB_{k2})x_2=0$ and $A_1x_1+A_2x_2=0$ gives $$(A_2-(c_1B_{12}+c_2B_{22}+...+c_kB_{k2}))x_2=0$$ which means $x_2=0$. A closer examination of the $j$th equation of $\bf{B}$:$$B_{j1}x_1+B_{j2}x_2=0$$ suggests that for both systems to have exactly the same solutions, $B_{j1}x_1=0$ must happen to be true. However, realizing that $B_{j2}\neq0$, we can adjust $c_j$ so that $$A_2= c_1B_{12}+c_2B_{22}+...+c_kB_{k2}$$ also holds.

Thus, the statement is proved.

Answer 2

The assumption that the two linear systems have the same space of solutions is equivalent, by the Rouché-Capelli theorem, to the fact that the two matrices

$$A= \left( {\begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A_{22} \\ \end{array} } \right), \quad B= \left( {\begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A_{22} \\ B_{11} & B_{12} \\ B_{21} & B_{22} \\ \end{array} } \right)$$ have the same rank. This in turn means that the last two rows of $B$ are in the span of the rows of $A$, which is your claim.

Note that exactly the same proof works for two homogeneous systems of $n$ equations in $n$ unknown.

Answer 3

First, let's see that it's enough to prove the following: if any solution of the system $$ A_{11} x_1 + A_{12} x_2 = 0 \\ A_{21} x_1 + A_{22}x_2 = 0 $$ is also a solution of $$B_1 x_1 + B_2 x_2 = 0$$ then $(B_1, B_2)$ is a linear combination of $(A_{11}, A_{12})$, $(A_{21}, A_{22})$. Now, to show this, we can't just produce the linear combination in a uniform way -- there are several cases to analyse.

Case $1$: the determinant of the $2\times 2$ system is nonzero. Then the determinant of system with unknowns $(c_1, c_2)$ $$c_1 A_{11}+ c_2 A_{21} = B_1\\ c_1 A_{12} + c_2 A_{22} = B_2$$ is also nonzero ( just the transpose!) so this system has a (unique!) solution ( given by the Cramer formula). Notice that we haven't used the hypothesis, since it is quite empty: the first system has the only solution $(x_1, x_2) = (0,0)$, which clearly also satisfies $B_1 x_1+ B_2 x_2 = 0$.

Case $2$. The first system has a zero determinant but not all coefficients $A_{ij}$ are zero. Let's suppose that $A_{11} \ne 0$. Now, $$A_{11} (-A_{12}) + A_{12} A_{11} = 0 \\ A_{21}(-A_{12}) + A_{22} A_{11} = 0$$ so $(x_1, x_2) = ( -A_{12}, A_{11})$ is a solution of the system. It follows that $B_1 ( - A_{12})+ B_2 A_{11} = 0$ and so $$(B_1, B_2) = \frac{B_1}{A_{11}}\cdot (A_{11}, A_{12})$$

Case $3$. All the coefficients $A_{ij}$ are $0$. Then any $(x_1, x_2)$ is a solution of the system. It follows that for any $(x_1, x_2)$ we have $B_1 x_1 + B_2 x_2 = 0$, and this readily implies $(B_1, B_2) = (0,0)$, so clearly a linear combination.

We are done.

Observation. This is true in general: if any solution $(x_j)$ of the system $\sum_{j} A_{ij} x_j = 0$, $i=1,\ldots m$ is also a solution of $\sum B_j x_j = 0$ then $(B_1, \ldots B_n)$ is a linear combination of the $(A_{i1}, \ldots, A_{in})$, $i=1, \ldots, m$. One can do away with determinants and Cramer rule, using instead row echelon form. The several cases possible are expressed by the possible shapes of the row echelon form. After the row reduction, the proof is in fact not that more difficult.