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.
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., \begin{equation} v=P_{S}v+P_{S^{\perp}}v. \end{equation}
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 \begin{equation} c=A^{\top}\lambda+\hat{c}. \end{equation}
When $c$ is orthogonal to the nullspace of $A$, $\hat{c}=0$, and \begin{equation} c=A^{\top}\lambda\implies c^{\top}x=\lambda^{\top}Ax=\lambda^{\top}b. \end{equation}