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?
 A: 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$.  
A: 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.
A: Use Singular Value Decomposition to obtain a low-rank approximation of the coefficient matrix.
Example: (using MATLAB for simplicity. one can easily obtain this solution by hand!)
A=[1 1;2 2];
b=[5 5];
[U,S,V]=svd(A);
A_approx=U(:,1)*S(1,1)*V(:,1)';

Now, One can use A_approx instead of A to obtain a solution in the least squares sense as 
@Paul mentioned above.
A: 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$. 
