I am following along Stephen Boyd's lectures on convex optimization and am having trouble understanding the diagram in this screenshot.
I have read through a few answers such as this one and this one.
My question is I am having trouble understanding why $$a^Tx = b$$ implies that a and x are perpendicular.
One way I understood it, following this post's answer is $$a^Tx = b \implies a^T x – a^T x_b = 0 $$ for some $x_b$ and so $a^T (x – x_b) = 0$. I understand why $a$ will be perpendicular to $x – x_b$ but am having trouble seeing why $a$ will be perpendicular to $x$.
One way I think about it is $x_b$ is a particular solution to the equation $a^Tx = b$ and since this is a linear program, any $a' = ka$ and $x' = x_b/k$ for non-zero $k$ will solve for $a'^T x' = b$. Hence, $x_b$ is just one of the solutions, and the other solutions are of the form $x_b/ k$, for non-zero $k$. Note, the other solutions are all parallel to $x_b$ and I think the linear combination of parallel lines is parallel to any of of them.
Hence, since $x$ and $x_b$ are parallel, $x – x_b$ is parallel to $x$ and so $a^T$ which is perpendicular to $x – x_b$ is perpendicular to $x$.
However, I'm having trouble seeing this for fixed $a$. In particular, is $a$ fixed?
Best Answer
The diagram in the screenshot is not showing that $a$ and $x$ are perpendicular. Indeed, by definition two vectors are perpendicular (aka orthogonal) iff their dot product is zero. Rather, it is showing that if $x_0$ satisfies $a^\top x_0 =b$, then every element $y$ in the hyperplane $H = \{y: a^\top y = b\}$ may be written in the form $y = x_0 + x$, where $a^\top x = 0$.