# Condition for solvability of a linear system

Given a linear system $Ax=b$, for $A\in\mathbb{R}^{n\times n}$, does the exact solution $x$ exist if $b~\bot~ Ker(A^T)$, ie. vector $b$ is orthogonal to each vector of the null-space of $A^T$?

If one states that $b\in im(A)$, does that mean that the linear combination of the columns of $A$ may yield $b$. In such case, a solution to $Ax=b$ exists iff $b\in im(A)$.

So, if $b\in im(A)$, then $b~\bot~Ker(A^T)$. Could one state the opposite direction? I consider $A$ general square matrix; what would happen if $A$ is symmetric?

-

$\def\im{\mathop{\mathrm{im}}}\def\rank{\mathop{\mathrm{rank}}}$Suppose $b \in \im A$, then for $x \in \ker(A^T)$, i. e. $A^Tx = 0$, so $\left< x, Ab\right> = \left< A^Tx, b \right> = \left< 0,b \right> = 0$ As $x \in \ker A^T$ was arbitrary, we have $b \perp \ker A^T$.

So we have $(\ker A^T)^\perp \supseteq \im A$. Counting dimensions, we have $\dim(\ker A^T)^\perp = n - \dim\ker A^T = n - (n - \rank A^T) = \rank A^T = \rank A = \dim \im A$ which shows that $\im A = (\ker A^T)^\perp$, i. e. $Ax = b \text{ is solvable} \iff b \in \im A \iff b \in (\ker A^T)^\perp \iff b \perp \ker A^T$ If $A$ is symmetric, $A^T = A$, so $\im A = (\ker A)^\perp$, that is $Ax = b$ is solvable iff $b \perp \ker A$.

-

Your goal is to prove that $\operatorname{im} A = (\ker A^T)^{\perp}$, or equivalently, $(\operatorname{im} A)^{\perp} = \ker A^T$.

Suppose $y \in (\operatorname{im} A)^{\perp}$. Now $v = 0$ if and only if $\lVert v \rVert^2 = 0$, and $\lVert v \rVert^2 = v \cdot v = v^Tv$, so let's see where this leads. $$\lVert A^T y \rVert^2 = (A^Ty)^TA^Ty = y^TAA^Ty = y \cdot [A(A^Ty)] = 0$$ since $A(A^Ty) \in \operatorname{im} A$. So $(\operatorname{im} A)^{\perp} \subseteq \ker A^T$.

Conversely, suppose $y \in \ker A^T$ and that $z=Ax \in \operatorname{im} A$. Then $$y \cdot z = y^TAx = (A^Ty)^Tx = 0^Tx = 0$$ so $y \in (\operatorname{im} A)^{\perp}$. So $\ker A^T \subseteq (\operatorname{im} A)^{\perp}$ and thus we have equality.

So $\operatorname{im} A = (\ker A^T)^{\perp}$, and therefore $b \perp \ker A^T$ if and only if there is some $x$ such that $Ax=b$.

In particular, when $A$ is symmetric, we have $\mathbb{R}^n = \operatorname{im} A \oplus \ker A$.

-