Prove that two homogeneous systems of linear equations are equivalent iff they have the same solution set.

My definition of equivalent of linear equations is that each equation of system $A$ is a linear combination of the equations of system $B$ and converse.

So i have a bit trouble proving this statement in general as $m\times n$ form. I worked with their coefficient matrices and if i show that these two are row equivalent the problem is solved. Is there any method to use for this? If not what's the general prove.


This cannot be done without the rank theorem or some other theorem of similar power.

We are given an $(m_A\times n)$-matrix $A$ and an $(m_B\times n)$-matrix $B$. Denote by ${\rm ker}(A)\subset{\mathbb R}^n$ the solution space of $Ax=0$, by $A_{i\!-}\in{\mathbb R}^n$ the $i^{\rm th}$ row vector of $A$, and by $${\rm row}(A):=\langle A_{1\!-}\>,\ldots, A_{m_A\!-}\rangle\subset{\mathbb R}^n$$ the row space of $A$. Similarly for $B$. We have to prove the following claim: $${\rm row}(A)={\rm row}(B)\qquad\Leftrightarrow\qquad{\rm ker}(A)={\rm ker}(B)\ . $$ For this it is sufficent to prove $${\rm row}(B)\subset {\rm row}(A)\qquad\Leftrightarrow\qquad{\rm ker}(A)\subset{\rm ker}(B)\ .$$ Proof of $\Rightarrow\>: \quad$ Assume ${\rm row}(B)\subset {\rm row}(A)$, and consider a vector $x\in{\rm ker}(A)$. Let $B_{i\!-}\> x=\sum_{k=1}^n B_{ik}x_k=0$ be an equation of the $B$-system. As $B_{i\!-}=\sum_{j=1}^{m_A} \lambda_j A_{j\!-}$ for certain $\lambda_j\in{\mathbb R}$ we obtain $$B_{i\!-}\>x=\sum_{j=1}^{m_A}\lambda_j A_{j\!-}\>x=0\ .$$ Since this is true for all $i\in[m_B]$ it follows that $x\in{\rm ker}(B)$. (This was the easy part.)

Proof of $\Leftarrow\>: \quad$ If ${\rm row}(B)\not\subset {\rm row}(A)$ then there is a row $B_{i\!-}$ of $B$ that does not belong to ${\rm row}(A)$. Denote by $A'$ the matrix obtained from $A$ by adding the row $B_{i\!-}$ at the bottom. Then $A'$ has rank one larger than $A$, hence ${\rm ker}(A')\subset{\rm ker}(A)$ has dimension one less than ${\rm ker}(A)$. It follows that there are vectors $x\in{\rm ker}(A)\setminus{\rm ker}(A')$. These vectors do not satisfy the last $A'$-equation $B_{i\!-}\>x=0$, hence do not belong to ${\rm ker}(B)$. This proves ${\rm ker}(A)\not\subset{\rm ker}(B)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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