Linear Equation system - solve only solvable variables

Question

If I have the SVD of a Matrix $A$, how do I solve the linear equation system $Ax=b$?

The problem is that if I e.g. has this linear equation system:

$-2y + z = 3$

$-4y + 2z = 6$

$x -2y + z = 4$

Then it's easy to see that $-2y + z = 3$ and therefore both $y$ and $z$ has infinitely many solutions, and that $x = 1$. However, how do deduce this from a general linear equation $Ax=b$? I'm sure it has to do with the SVD.

Note: I'm writing a Java program computing this so if you have any computational resources to point me at it would be great.

Thanks in advance!

Answer 1

Here we have $Ax=b$, where $A=\left[ \begin{array}{ccc} 0 & -2 & 1 \\ 0 & -4 & 2 \\ 1 & 2 & 1 \end{array} \right]$ and $b=\left[ \begin{array}{ccc} 3 \\ 6 \\ 4\end{array} \right]$, but the top two rows of $A$ are linearly dependent, producing the same equiation twice, which is why of course, there are an infinite amount of solutions for $y,z$.

So our system can now be written as $Dx=C$, where $D=\left[ \begin{array}{ccc} 0 & -4 & 2 \\ 1 & -2 & 1 \\ \end{array} \right]$, and $C=\left[ \begin{array}{ccc} 6 \\ 4 \\ \end{array} \right]$.

Answer 2

To solve your problem, Rouché–Capelli theorem could be useful.

It's not related to SVD, though. I think you can implement it using Gaussian elimination.

Some useful links:

• Gaussian elimination in Java

• About Rouché–Capelli theorem (pag 4.)