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.

  • 2
    $\begingroup$ 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$ $\endgroup$ – nemo Sep 16 '17 at 18:18
  • $\begingroup$ I guess that makes sense. Can you tell me how $c$ is orthogonal to the nullspace here? $\endgroup$ – 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., \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}

  • $\begingroup$ This is awesome!! Thank you $\endgroup$ – nundo Sep 16 '17 at 20:24
  • $\begingroup$ 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. $\endgroup$ – nundo Sep 16 '17 at 21:08
  • $\begingroup$ 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? $\endgroup$ – nundo Sep 17 '17 at 17:16
  • $\begingroup$ @nundo This kind of decomposition can be done for any vector space that is equipped with an inner product structure; for more details you can read this for a start $\endgroup$ – nemo Sep 18 '17 at 4:51

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.