How to solve $Mx=b$ where singular M but setting $x_n=0$ for some $x$ allows unique solution

Question

I want to solve $Mx=b$ where $M$ (concrete example below) is singular, but where I can arbitrarily set some $x_i=0$ .. in which case I believe there should be a unique solution for $x$? But how how do I obtain it? The concrete example I provide is a simple example but approach to solving will need to work for large matrices (working in Matlab).. I apologize if this turns out to be an elementary problem... it's troubling me.

$$ M= \begin{bmatrix} 2 & -1 & -1 \\ 1 & 0 & -1 \\ 1 & 1 & -2 \\ \end{bmatrix} $$ and $$ b=\begin{bmatrix} 2 \\ 0 \\ -2 \\ \end{bmatrix} $$

Answer 1

So $Mx =b$ has infinitely many solutions. One approach is that you could find the least norm solution by multiplying both sides by the pseudoinverse of $M$.

Answer 2

You can use the SVD. Let $M = U \Sigma V^{T}$. Then if you consider the problem least squares problem

$$ \min_{x} \| Mx - b\|_{2}^{2} $$

we get

$$ \| Mx - b\|_{2}^{2} = \|U^{T} (M VV^{T} x - b)\|_{2}^{2} = \| \Sigma V^{T}x - U^{T}b\|_{2}^{2}$$

You can compute this like

$$ x^{*} = V \Sigma^{-1}U^{T}b $$

with

$$ \Sigma^{-1} = \begin{align}\begin{cases} \frac{1}{\sigma_{i}}& \sigma_{i} \neq 0 \\ 0 & \textrm{ otherwise} \end{cases} \end{align}$$

Your matrix is really ill-conditioned.

import numpy as np

M = np.array( [[ 2, -1, -1 ] , [1 , 0,-1] , [1, 1, -2] ])

b = np.array([2,1,-1])

Mstar = np.linalg.pinv(M)
xstar = np.dot(Mstar, b)

error = np.linalg.norm(np.dot(M,xstar) - b)
error


0.6030226891555274

np.linalg.cond(M)


1.2505769527845804e+16

If you check the singular values

U, S, Vt = np.linalg.svd(M)

S

array([3.31662479e+00, 1.73205081e+00, 2.65207573e-16])

The rank is $2$. You need to drop that last singular value.