LinArg assignment 9

exercise

2. Characterizing solvability via null spaces

Theorem 6.2.4

$$\{x\in {\mathbb{R}}^n|Ax=b\}=\varnothing ⟺\{z\in {\mathbb{R}}^m|A^{\top }z=0,b^{\top }z=1\}\ne \varnothing$$

$EQ$ has a solution for every $c$ $⟹$ $N(A^{\top })\cap N(B^{\top })=\{0\}$

Let $M=\left[\begin{array}{cc}A& B\end{array}\right]\in {\mathbb{R}}^{m\times (n_1+n_2)}$ and $u=\left(\begin{array}{c}x\\ y\end{array}\right)\in {\mathbb{R}}^{n_1+n_2}$ we can write EQ as $Mu=c$ Assume for every $c$ there exists a $u$, then for every c: $\{u|Mu=c\}\ne \varnothing$ $⟹\{z\in {\mathbb{R}}^m|M^{\top }z=0,c^{\top }z=1\}=\varnothing$ (Theorem 6.2.4) We show this by using contradiction Suppose there exists a nonzero $z_0$ with $A^{\top }{z}_0=0$ and $B^{\top }{z}_0=0$ then $M^{\top }{z}_0=\left(\begin{array}{c}{A}^{\top }\\ B^{\top }\end{array}\right)z_0=0$ so $z_0\in N(M^{\top })$ Since $z_0\ne 0$ then we can choose some $c$ such that $c^{\top }{z}_0=1$, which means $z_0\in \{z\in {\mathbb{R}}^m|M^{\top }z=0,c^{\top }z=1\}$. This is a contradiction to $\{z\in {\mathbb{R}}^m|M^{\top }z=0,c^{\top }z=1\}=\varnothing$ Therefore $N(M^{\top })=\{0\}$ note that, for every $z$, $M^{\top }z=0⟺\left(\begin{array}{c}{A}^{\top }z\\ B^{\top }z\end{array}\right)=0⟺A^{\top }z=0\wedge B^{\top }z=0$ So $N(M^{\top })=N(A^{\top })\cap N(B^{\top })$ Together with $N(M^{\top })=\{0\}$ we get $N(A^{\top })\cap N(B^{\top })=\{0\}$

$N(A^{\top })\cap N(B^{\top })=\{0\}⟹$ $EQ$ has a solution for every $c$

we define $M$ and $u$ just like in the last section. we know from last part $N(A^{\top })\cap N(B^{\top })=\{0\}⟹N(M^{\top })=\{0\}$ we also know that $\{u|Mu=c\}=\varnothing ⟺⟹\{z\in {\mathbb{R}}^m|M^{\top }z=0,c^{\top }z=1\}\ne \varnothing$ (Theorem 6.2.4) Let $c$ be an arbitrary vector in ${\mathbb{R}}^m$: Assume $Mu=c$ has no solution, then there must exist at least one $z$ such that $M^{\top }z=0$ and $c^{\top }z=1$. But $M^{\top }z=0$ means $z\in N(M^{\top })$, so $z=0$ However, $c^{\top }0=0$ contradicts our assumption, which means $Mu=c$ must have at least a solution. Equivalently there exists $x,y$ such that $Ax+By=c$ for every $c$

Conclusion We proved the claim in both direction, so the claim holds.