According to this solution, it seems that it's possible to find one solution of a non-square linear system that has infinitely many solutions with the following method.
-
Write the linear system as $A X = B$.
(A is non invertible, since A is non-square) -
Consider the singular value decomposition of $A$:
$$A = U\ D\ ^t V$$
where $D$ is a $(m, n)$ diagonal matrix with non-negative real numbers on the diagonal.
-
Let $\Delta$ be a $(m, n)$ diagonal matrix, with:
$\Delta_{i,i} = 0$ if $D_{i,i} = 0$
$\Delta_{i,i} = \frac{1}{D_{i,i}}$ if $D_{i,i} \neq 0$ -
One solution of the initial linear system is given by:
$$ X= V\ \Delta\ ^tU\ B$$
Is this true in general? (it seems to be true at least for this example). How can you prove this?
Note: It seems that $A^+ = V\ \Delta\ ^tU$ is the pseudoinverse of the matrix $A$, see this article.
PS: Here are some ideas but I'm looking for a real proof.
Note2: It seems that this problem is in fact made of 2 steps:
-
Prove that if $A = U \Sigma ^tV$ is the SVD of $A$, then $A^+ = V \Sigma^+\, ^tU$ respects the conditions defining the pseudo inverse, i.e. $A A^+ A = A$, $A^+ A A^+ = A^+$, and the fact that $A^+ A$ and $A A^+$ are symmetrical matrices.
-
Prove that if $(1) A X = B$ has infinitely many solutions, then $X = A^+ B$ is a solution of (1), i.e. we have to prove that $A A^+ B = B$.
Best Answer
If we have the SVD $A=UDV^*$, with $U$, $V$ unitary, $D$ diagonal, then the matrix $V\Delta U^*$ (with $\Delta$ as in your post) is equal to the Moore-Penrose inverse of $A$: For instance $$ A(V\Delta U^*)A = UDV^*(V\Delta U^*)UDV^*=UD\Delta DV^*=UDV^*=A, $$ since $D\Delta D=D$. All other properties can be verified similarly.
If $Ax=b$ is solvable, i.e., there is $x_0$ such that $Ax_0=b$, then $A^+b$ is a solution: $$ A(A^+b) = AA^+Ax_0 = Ax_0=b $$ by the properties of the Moore-Penrose inverse.