underdetermined system of equations

Question

I am trying to solve a system of linear equations that is underdetermined. Meaning the number of unknown is more than the equations. The system is of the form $Ax=0$. I have seen methods of solving this type of problem when the right hand side is nonzero. Namely, $Ax=b\implies x=(A^{T}A)^{-}A^{T}b$ as here. But this method is inapplicable when $b=0$. Any suggestions?

Answer 1

If A has a nontrivial null space then $A^T A$ is not invertible. Unless the matrix is huge, I suggest SVD. The SVD allows you to break apart the null space from the non-null space since the former is spanned by the singular vectors associated with zero singular value. There are other ways to do this but I suspect that SVD is the easiest, unless you have a large, sparse matrix. NB, for a rectangular matrix you'll have both a left and right null spaces, but you're only asking for an element of the right null space. So you could just pick one of the right null space singular vectors, or you can characterize the subspace of all of them as the span of these (zero-singular value) right singular vectors. Any standard math package will do the job such as numpy.linalg.svd

Answer 2

A question is whether you are trying to do this by hand, or using, say, matlab or a library like LAPACK.

For an underdetermined system that is of full row rank, one usually computes something called the LQ factorization. Or, equivalently, the QR factorization of $ A^T $. (The Q in the LQ factorization is $ Q^T $ in the QR factorization.)

Let's say $ A^T = Q R $. If you are trying to solve $ A x = b $, you can instead solve $ ( Q R )^T x = b $ or $ R^T Q^T x = b $. So, you find $ z $ so that $ R^T z = b $ (that means solving with a triangular matrix) and then you are left with solving $ Q^T x = z $. This is itself an underdetermined system. Pick $ x $ to be in the column space of $ Q $. Then $ x = Q w $ and $ Q^T Q w = z $. Ah, $ w = z $ since $ Q $ has orthonormal columns. So, $ x = Q z = Q R^{-T} b $ is a solution.

Check: $ A x = ( Q R )^T ( Q z ) = R^{T} Q^T Q z = R^{T} z = b $.

Now, this is not the only solution. You can add any vector in the nullspace of $ A $.