Is it possible to add vectors in rowspace with vectors in nullspace? Aren't they different dimensions?

I am looking at the solutions to homework 4, problem 4.8a in Stephen Boyds online course here: https://see.stanford.edu/Course/EE364A/78

The problem is about minimizing a linear objective:

$min \,\, c^Tx, \\subject \,\, to \,\,Ax=b$

And, in the solutions ( which can be found here https://see.stanford.edu/materials/lsocoee364a/hw3sol.pdf) for problem 4.8a, it says "and $c$ is orthogonal to the nullspace of $A$. We can decompose c as $c=A^T\lambda+\hat c, \,\, A\hat c=0.$"

So, from what I am seeing in that solution, I can deduce the following information:

• $\hat c$ is in the nullspace of A
• $A^T\lambda$ is in the rowspace of A
• we are adding $\hat c$ and $A^T\lambda$ to get vector $c$, which is apparently orthogonal to the nullspace of $A$.

If $A$ is square, then this can work. But, if $A$ is not square, then I do not understand how adding a vector in the nullspace and a vector in the rowspace is possible. They are different dimensions, right?

Furthermore, if someone can help me understand how it is possible for $c$ to be orthogonal to the nullspace, and also be in the rowspace of A, that would be much appreciated.

• For $A\in\mathbb{R}^{m\times n}$, both the nullspace and row space of $A$ are subspaces of $\mathbb{R}^{n}$, so they both contain vectors of length $n$ – nemo Sep 16 '17 at 18:18
• I guess that makes sense. Can you tell me how $c$ is orthogonal to the nullspace here? – nundo Sep 16 '17 at 18:23

Let $A\in\mathbb{R}^{m\times n}$. For any $v\in\mathbb{R}^{n}$ and a subspace $S$ of $\mathbb{R}^{n}$, $v$ can be written as the sum of its projection onto $S$ and the complement $S^{\perp}$, i.e., $$v=P_{S}v+P_{S^{\perp}}v.$$
In the reference you mention, $S$ is the nullspace of $A$ and $v=c$. So, the first component is something in the nullspace of $A$, let's call it $\hat{c}$ (so $A\hat{c}=0$). The second component is something perpendicular to the nullspace of $A$, or equivalently, something in the rowspace of $A$, so it can be represented as $A^{\top}\lambda$ for some $\lambda\in\mathbb{R}^{m}$. So we have $$c=A^{\top}\lambda+\hat{c}.$$
When $c$ is orthogonal to the nullspace of $A$, $\hat{c}=0$, and $$c=A^{\top}\lambda\implies c^{\top}x=\lambda^{\top}Ax=\lambda^{\top}b.$$
• I understand now, the trick is that when the vector $c$ is orthogonal to the sum of two orthogonal components, then the component in the nullspace MUST be $0$ by the definition of something being orthogonal. – nundo Sep 16 '17 at 21:08
• now, @nemo, the theorem you stated at the beginning - is that only true for $v \in \mathbb{R}^n$? Or is it true for a member of any vectorspace? i.e. is it true that, for any vector space, a member of it can be decomposed into a projection onto a subspace of that vector space, plus a projection onto the orthogonal completment of that subspace? – nundo Sep 17 '17 at 17:16