# Prove that if two linear systems have the same solutions then, they are equivalent

I'm having troubles with this proof:

Given two linear systems in $$n$$ unknowns:

$$A=\begin{pmatrix} A_1\\ A_2\\ ...\\ A_m \end{pmatrix}$$

$$B=\begin{pmatrix} B_1\\ B_2\\ ...\\ B_p \end{pmatrix}$$

Let $$S_A$$ and $$S_B$$ be the set of their solutions. Prove that:

$$S_A=S_B \Rightarrow A_i=\sum_\limits{k=1}^{p} c_k^i B_k$$ and $$B_j=\sum_\limits{k=1}^{m} d_k^j A_k \ \ \ 1\leq i\leq m , 1\leq j\leq p$$

I had not difficulties in proving the inverse implication but this is giving me troubles. Practically I have to prove that his 2 linear systems have the same solutions than the second can be derived by a linear combination of the equations of the first and vice-versa. Now I'll write my (miserable) attempt:

Attempt

Let's write the systems in a more explicit form:

$$A: (\sum_\limits{j=1}^{n}a_{ij}x_j)-a_i=0 \ \ \ 1\leq i \leq m$$

$$B: (\sum_\limits{j=1}^{n}b_{ij}x_j)-b_i=0 \ \ \ 1\leq i \leq p$$

Where $$a_i$$ and $$b_i$$ are the constant terms. Practically we have to prove that there exist constants such that:

$$(\sum_\limits{j=1}^{n}a_{ij}x_j)-a_i=c_1^i[(\sum_\limits{j=1}^{n}b_{1j}x_j)-b_1]+...+c_p^i[(\sum_\limits{j=1}^{n}b_{pj}x_j)-b_p] \ \ 1\leq i \leq m$$

One of my friends proved this equality by substituting $$(x_1,...,x_j)=(t_1,...,t_j)$$ where $$t_k$$ are the solution of both the systems. But I think that this is dumb because this proves just that they have common solutions (the hypothesis): I want the equality for a generic $$(x_1,...,x_j)$$. My idea is this: to be equal the coefficients of the same unknown must be equal both sides. So:

$$\left\{\begin{matrix} a_ {i1}=c_1^i b_{11}+c_2^i b_{21}+...+c_p^i b_{p1}\\ a_ {i2}=c_1^i b_{21}+c_2^i b_{22}+...+c_p^i b_{p2}\\ ...\\ a_ {in}=c_1^i b_{n1}+c_2^i b_{n2}+...+c_p^i b_{pn}\\ a_i=c_1^i b_1+c_2^i b_2+...+c_p^i b_p \end{matrix}\right.$$

And now I have to prove that this system has always a solution( the unknowns are $$(c_1^i,c_2^i,c_3^i,...)$$. I still have to use the fact that $$A$$ and $$B$$ have the same solutions, but I don't know how to do this.

[I know that there is a similar post, but it's about the particular case of a system with 2 unknowns, and I can't understand many answers because these are my first lessons of Linear Algebra/Geometry]

P.S : The notation we are using is really heavy, am I right?

Moreover I think that maybe the hypothesis $$S_A=S_B$$ implies also that $$m=p$$: the two systems must have the same number of independent equations, otherwise the system that I obtained during my proof couldn't be always solved.

• It's not true if both sets of solutions are empty. For example, $A_1: x_1 = 0$; $A_2: x_1 = 1$; $B_1: x_2 = 0$; $B_2: x_2 = 1$. – Litho Oct 3 '19 at 14:16
• It seems like that with your rudimentary knowledge of linear algebra and matrices there will never be an answer that fully convinces you. For example one could argue as follows (I am restricting to n by n cases and regarding the systems as matrices): The two systems having the same set of solutions means they have the same null-space. Looking at the (orthogonal) complement one can show that then they must have the same (row) space, the span of the rows treated as vectors. But having the same row space implies that any row of one can be written as a linear combination of the rows of the other. – Behnam Esmayli Oct 4 '19 at 0:29

Let $$A\in M_{m,n},u\in\mathbb{C}^m$$ and $$B\in M_{p,n},v\in \mathbb{C}^p$$. We consider the $$2$$ systems in $$x\in\mathbb{C}^n$$:

$$(S_1)$$: $$Ax=u$$ and $$(S_2)$$: $$Bx=v$$.

EDIT. I forgot the case when both sets of solutions are void. The correct result is

$$\textbf{Proposition}$$. The above systems have same set of solutions IFF

EITHER $$AA^+u\not= u,BB^+v\not= v$$ (both sets of solutions are void)

OR $$AA^+u=u,BB^+v=v$$, $$\ker(A)=\ker(B)$$ and $$AB^+v=u,BA^+u=v$$.

$$\textbf{Proof}$$ (of the second part, when $$AA^+u=u,BB^+v=v$$). The set of solutions of $$(S_1)$$ is the non-void affine set

$$x=A^+u+(I_n-A^+A)w$$ where $$w$$ is arbitrary in $$\mathbb{C}^n$$.

The set of solutions of $$(S_2)$$ is the non-void affine set

$$x=B^+v+(I_n-B^+B)z$$ where $$z$$ is arbitrary in $$\mathbb{C}^n$$.

These affine sets are the same IFF $$im(I-A^+A)=im(I-B^+B)$$ and $$BA^+u=v,AB^+v=u$$.

$$A^+A$$ is hermitian and, more precisely, is the orthogonal projection on $$im(A^*)=(\ker(A)^{\perp}$$.

Then $$im(I-A^+A)=(im(A^+A))^{\perp}=\ker(A)$$ and we are done.$$\square$$

$$\textbf{Remark}$$. The last $$2$$ conditions positively responds to the OP's question when both sets of solutions are non-void.

• I don’t understand this notation. I’m a beginner:i don’t even know how to multiply two matrixes. Is there a way to prove it in a notation that an high school student can understand. – Eureka Oct 1 '19 at 13:16
• I cannot do much for you except specify the notations. $U^+$ denotes the Moore Penrose inverse of $U$ (cf. en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse ). $im(V)$ denotes the range of the matrix $V$. Practically, for you, it suffices to use my result, with the help of Matlab, for example. – loup blanc Oct 1 '19 at 13:33
• Thank you, but i didn't understand a single word of your answer, so i cannot give you the best answer :c – Eureka Oct 2 '19 at 10:40

The most elementary proof of the fact I would imagine to be as the following.

Assume two systems $$Ax=a$$ and $$Bx=b$$ have the same (non-void) solution that is completely parameterized as $$x=x_0+\sum_{j=1}^rN_j\lambda_j=x_0+N\lambda$$ where all column vectors $$N_j$$ are linearly independent, $$N=[N_1\ \ldots\ N_r]$$ and $$\lambda$$ is the column vector of $$\lambda_j$$. Then $$Ax_0=a$$, $$Bx_0=b$$ (set $$x$$ into the systems with $$\lambda=0$$) and $$AN=0,\qquad BN=0\tag{*}$$ i.e. the columns of $$N$$ are the basic solutions to the homogeneous systems $$Ax=0$$ and $$Bx=0$$. The equations (*) can be understood as $$A_iN_j=0,\quad B_iN_j=0,$$ i.e. the rows of $$A$$ and $$B$$ are orthogonal to the same subspace spanned by the columns of $$N$$. Moreover, the latter subspace cannot be expanded to a larger one, since that would mean that the solution $$x$$ were not complete, i.e. there are more $$N_j$$ possible in the parameterization for $$x$$, which is a contradiction. In other words, the row space of $$A$$ and the row space of $$B$$ are the same space, which is the orthogonal complement to the subspace spanned by all $$N_j$$, i.e. every $$A_i$$ is a linear combination of some rows of $$B$$ and vice versa. It can be formalized as $$B=SA,\qquad A=TB$$ for some matrices $$S$$ and $$T$$ of proper size. Now apply this equations to $$x_0$$ to get that the right hand sides are up to the same transformations $$b=Sa,\qquad a=Tb.$$ Summing up, all equations in $$Bx=b$$ are the linear combinations of equations in $$Ax=a$$ (described by the rows of $$S$$) and all equations in $$Ax=a$$ are the linear combinations of that in $$Bx=b$$ (described by the rows of $$T$$).

P.S. Alternatively, one can apply the reduced row echelon form and use the fact that it is unique for every matrix and the same solution means the same RREF.