# Solving systems of linear equations when matrix of coefficients is singular

When attempting to solve a problem of type $AX=B$ where $A$ is the matrix of coefficients, $X$ contains the variables and $B$ is the right hand side, it turned out the $A$ was singular. As a result I could not premultiply both side by $A^{-1}$. In such a case, how would I solve for the variables without having to use augmented matrices?

Here is the question:

$$\begin{pmatrix} 1&2&1&1&1 \\ 2&1&2&1&1 \\ 1&2&3&1&1 \\ 2&2&1&1&3 \\3&3&5&2&2 \end{pmatrix}\begin{pmatrix} u \\ v \\ w \\ x \\ y \end{pmatrix}=\begin{pmatrix} 6.3 \\ 6.7 \\ 7.7 \\ 9.8 \\10.9 \end{pmatrix}$$

Since $A$ is singular I cannot do $X=A^{-1}B$ which is the method I would typically use to solve for the unknowns. In later parts of the book I am studying they elude to a method with which one can use to solve for $X$, but do not further elaborate. Does anyone have an idea on how to solve this problem (or any problem in general where A is singular) without the use augmented matrices or is that the only way?

-
You could try to do clever things, such as observing that subtracting rows 1 and 3 will immediately allow you to find $w$. But, sans that, probably the easiest thing to do is just perform row reduction on the augmented matrix. –  David Mitra Dec 21 '11 at 12:27
Do you typically invert a $5\times 5$ matrix? Don't you know Gaussian elimination? –  lhf Dec 21 '11 at 12:43
Emily, certainly the Gaussian elimination is the best thing to do. –  Elias Dec 21 '11 at 12:56
A pity you don't have an 4x5 system, then you could use the associated homogeneous system. –  user3.1415 Dec 21 '11 at 13:28

If the matrix is singular, the equation $Ax=b$ has no solution. This means that $b$ does not lie in the range of $A$. However it is possible to find a vector $x_0$ such that the image $Ax_0$ is closest'' to $b$ in a sense that can made precise. This requires a metric or norm on the target space.

One example of this is the Moore-Penrose pseudoinverse of $A$.

-
A square matrix $A$ is singular if and only if $Ax=b$ has no solution for $some$ $b$; in general, the equation $Ax=b$ may have (infinitely) many solutions. –  David Mitra Dec 21 '11 at 14:37

Per my comment, Gaussian Elimination is perhaps the easiest thing to do.

However:

You don't have to perform row reduction as given by the Gaussian Algorithm.

Any two systems that have row equivalent augmented matrices have the same solution set.

There is a lot of cancellation that can occur in your matrix by using row operations, other than those used in Gausian elimination; try taking advantage of that.

If you're lucky, you can obtain the solution, if any, through ad-hoc methods by examining the "sparse" row equivalent form of the augmented matrix.

Note here that the augmented matrix for your system is row equivalent to (adding multiples of row 1 to the others): $$\begin{pmatrix} 1&2&1&1&1&\ \ 6.3 \\ 1&-1&1&0&0&\ \ .4 \\ 0&0&2&0&0&\ \ 1.4 \\ 1&0&0&0&2&\ \ 3.5\\1&-1&3&0&0&\ \ -1.7 \end{pmatrix}$$

The above is row equivalent to (working with rows 2 and 5):

$$\begin{pmatrix} 1&2&1&1&1&\ \ 6.3 \\ 1&-1&1&0&0&\ \ .4 \\ 0&0&2&0&0&\ \ 1.4 \\ 1&0&0&0&2&\ \ 3.5\\0&0&2&0&0&\ \ -2.1 \end{pmatrix}$$

We see that there is no solution.

-
Even when the system of equations is singular, you can find a least-squares solution by solving the system $A^{T}Ax=A^{T}b$.