# Proving that if $\vec{k}$ is a least solutionof $A\vec{x}=\vec{b}$, then $c\vec{k}$ is for $A\vec{x}=c\vec{b}$

Say if $\vec{k}$ is a least squares solution to $A\vec{x}=\vec{b}$ such that $A\vec{x}=\vec{b}$ has no solutions. My guts feel tell me that for all constants $c\vec{k}$, where $c\in\mathbb{R}$, it is still a least squares solution to $A\vec{x}=c\vec{b}$ as long as $c$ isn't zero. But to write a proof on this, how should I start off with?

I know that $A\vec{x}=\vec{b}$ does not have a solution. So I have to do a projection to find the closest, that is $A\vec{k}=\vec{p}$ where $\vec{p}$ is the projected vector and is in the column space of $A$. So now, I am not going to care about $A\vec{x}=\vec{b}$ anymore. Then of course, if $A\vec{k}=\vec{p}$ has a solution, then $cA\vec{k}=c\vec{p} \Rightarrow Ac\vec{k}=c\vec{p}$ because it is just a combination the column space of $A$. Since $A\vec{k}=\vec{p}$ is the projected equation that has the closest solution, then this means $c\vec{k}$ indeed is a least squares solution to $A\vec{x}=\vec{b}$ for all $c\in\mathbb{R}$ and $c\neq0$.

Is my proving right? I find it very informal and the proof is somewhat not sharp enough.

-
"Say if $\vec{k}$ is a least squares solution to $A\vec{x}=\vec{b}$ such that $A\vec{x}=\vec{b}$ has no solutions." - that's kinda sorta self-contradicting, eh? – J. M. Aug 4 '11 at 12:53
hmm...maybe I'm not phrasing it properly. What I meant was $A\vec{x}=\vec{b}$ is inconsistent and cannot be solved. And $\vec{k}$ is its least squares solution. – xenon Aug 4 '11 at 12:55
@J.M. Not at all: $A\vec{x}=\vec{b}$ is inconsistent, and $\vec{k}$ is the least squares solution to the problem (a vector such that $\lVert A\vec{k}-\vec{b}\rVert$ is minimized). – Arturo Magidin Aug 4 '11 at 12:55
@Arturo: I was thinking "if $\vec k$ is an LS solution, why then are you saying that $A\vec{x}=\vec{b}$ doesn't have solutions"? But, yes, that'd be the reasonable phrasing... – J. M. Aug 4 '11 at 12:58
If you think at the practical level, this can't be true. We have that $k$ is in some sense (well, a very definite sense) close to a solution, that $Ak$ is "near" b. Unless b is the zero vector, which it isn't, $A(100k)$ is nowhere near b. – André Nicolas Aug 4 '11 at 13:02

As to the new question, if $\vec{y}$ is a least squares solution to $A\mathbf{x}=\vec{b}$, and $c\neq 0$, is $c\vec{y}$ a least squares solution to $A\mathbf{x}=c\vec{b}$?

Note that $$\lVert A\vec{y}-c\vec{b} \rVert = \left\lVert cA\left(\frac{1}{c}\vec{y}\right) - c\vec{b}\right\rVert = |c|\left\lVert A\left(\frac{1}{c}\vec{y}\right) - \vec{b}\right\rVert.$$ So $\vec{y}$ is a least squares solution to $A\vec{x}=c\vec{b}$ if and only if $\lVert A\vec{y} - c\vec{b}\rVert$ is as small as possible, if and only if $\lVert A(\frac{1}{c}\vec{y}) - \vec{b}\rVert$ is as small as possible, if and only if $\frac{1}{c}\vec{y}$ is a least squares solution to $A\vec{x}=\vec{b}$; equivalently, $\vec{y}$ is a least square solution to $A\vec{x}=\vec{b}$ if and only if $c\vec{y}$ is a least squares solution to $A\vec{x}=c\vec{b}$, which is what you wanted to show.

-

This isn't right. First, intuitively, if $\vec{k}$ is a least-squares solution, this means that $A\vec{k}$ is close to $\vec{b}$. Multiplying $\vec{k}$ by some arbitrary real number would multiply $A\vec{k}$ by the same number, and this could take it very far from $\vec{b}$.

To engage with your thinking more directly, if $\vec{p}$ is the orthogonal projection of $\vec{b}$ into the column space of $A$, then $c\vec{p}$ is not in general. Visualizing this in 3-space is helpful. Say $\vec{b}$ is a point in 3-space. If $A\vec{x}=\vec{b}$ doesn't have a solution, then the column space of $A$ is some subspace of 3-space that doesn't include $\vec{b}$. Say it is a plane. Then if $\vec{k}$ is the least squares solution, $\vec{p}=A\vec{k}$ is the unique point in this plane that is closest to $\vec{b}$. Scaling $\vec{p}$ by something will take it further away from $\vec{b}$.

EDIT: now that you have edited the question,

YES, you are right; if $\vec{k}$ is the least-squares solution of $A\vec{x}=\vec{b}$, then $c\vec{k}$ is the least-squares solution of $A\vec{x}=c\vec{b}$. Furthermore, your reasoning is correct, though imprecisely articulated (and $\vec{b}$ should be $c\vec{b}$ at the end of the paragraph). I take your question to be about how to make your proof more precise.

Here is one way to do it. As you note, saying that $\vec{k}$ is a least-squares solution of $A\vec{x}=\vec{b}$ is equivalent to saying that $A\vec{k}=\vec{p}$ is the orthogonal projection of $\vec{b}$ into the column space of $A$. Let $\vec{q}=\vec{b}-\vec{p}$, so that $\vec{b}=\vec{p}+\vec{q}$, $\vec{p}$ is in $A$'s column space, and $\vec{q}$ is orthogonal to every vector in $A$'s column space.

Multiplying everything by $c \in \mathbb{R}$, we have $c\vec{b}=c\vec{p}+c\vec{q}$; $c\vec{p}$ is still in $A$'s column space (you noted this in your informal proof), and $c\vec{q}$ is still orthogonal to everything in $A$'s column space, since as a multiple of $\vec{q}$, it is orthogonal to everything $\vec{q}$ is orthogonal to. (This is what was missing from your argument, although you intuited it). This means that $c\vec{p}$ is the orthogonal projection of $c\vec{b}$ into $A$'s column space. Since $A(c\vec{k})=cA\vec{k}=c\vec{p}$ as you note, this means that $c\vec{k}$ is a least-squares solution to $A\vec{x}=c\vec{b}$.

-

$\bf k$ is a least squares solution means it is the value of $\bf x$ that minimizes the norm of $A{\bf x}-{\bf b}$. There is no reason why the norm of $Ac{\bf x}-{\bf b}$ should equal that of $A{\bf x}-{\bf b}$ (and every reason to believe it shouldn't), so no reason to think $c{\bf k}$ should be a least squares solution.

-
I think I missed out a $c$ in my equation just now. It should be if $\vec{k}$ is the least squares solution, it is also one to $A\vec{x}=c\vec{b}$. So when proving, do I just say $Ac{\bf x}-{\bf cb}$ is the same as $A{\bf x}-{\bf b}$? – xenon Aug 4 '11 at 13:15
But $Ac{\bf x}-c{\bf b}$ isn't the same as $A{\bf x}-{\bf b}$ (unless $c$ is 1 or $A{\bf x}-{\bf b}$ is $\bf 0$) since it is $(c)(A{\bf x}-{\bf b})$. – Gerry Myerson Aug 4 '11 at 22:43