Moore-Penrose pseudoinverse solution of a system of linear equations I have found a theorem, taken from here:
Theorem: Let $A \in \mathbb{R}^{m \times n}$, $B \in \mathbb{R}^M$ and suppsoe that $AA^+b=b$. Then any vector of the form:
$$x = A^+b + (I-A^+A)y$$
where $y \in \mathbb{R}^n$ is arbitrary is a solution of 
$$Ax = b$$
1) My question concerns the fact how $y$ can be arbitrary, how come $x$ will be the same for any $y$.
2) And second concerns how they arrive at solution for $x$.
I do not know how to answer 1). But for 2) we can start like so, premultiply both sides by $A^+$
$$A^+Ax = A^+b$$ 
And now I am stuck :)
EDIT: I think I know why in 1) $y$ can be anything, because if $I \neq A^+A$ then there are infinite number of solutions. Is there like a best one, though?
 A: Let's apply $A$ to this $x$:
$$
Ax=AA^+b+A(I-A^+A)y.
$$
We see that since $A(I-A^+A)=A-AA^+A=0$ the dependence on $y$ goes away. Now we have two possibilities:


*

*$AA^+b=b$. Then this $x$ is the solution.

*$AA^+b\ne b$. Then the system is not compatible (no solution).


The matrix $AA^+$ is, in fact, the orthogonal projection onto the image of $A$, and the first case means that $b$ belongs to the image.
Another interpretation is that $A^+b$ is one particular solution to $Ax=b$ and $(I-A^+A)y$ are all solutions to $Ax=0$. The particular solution $A^+b$ is the special solution in the sense that it is the minimum norm solution.
Example: take
$$
A=\begin{bmatrix}
1 & 0\\0 & 0
\end{bmatrix}.
$$
The system is then
$$
Ax=b\quad\Leftrightarrow\quad \begin{bmatrix}
x_1\\0
\end{bmatrix}=\begin{bmatrix}
b_1\\b_2
\end{bmatrix}.
$$
The two cases above are


*

*$b_2=0$. Then all solutions are $x_1=b_1$ and $x_2=y_2$ (arbitrary), i.e.
$$
x=\begin{bmatrix}
b_1\\y_2
\end{bmatrix}=\begin{bmatrix}
b_1\\0
\end{bmatrix}+\begin{bmatrix}
0 & 0\\0 & 1
\end{bmatrix}\begin{bmatrix}
y_1\\y_2
\end{bmatrix}.
$$
Since $A^+=A$ in this example, it is easy to see that the first term is $A^+b$ and the second term is $(I-A^+A)y$.

*$b_2\ne 0$. Then no solution.

