Moore-Penrose pseudoinverse solution of a system of linear equations

Question

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?

Answer 1

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:

1. $AA^+b=b$. Then this $x$ is the solution.
2. $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

1. $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$.
2. $b_2\ne 0$. Then no solution.