3.2 Solving Underdetermined Systems

A m × n system of linear equations where m > n (or m = n and A is singular) is underdetermined. There are fewer equations than there are unknowns. Underdetermined systems have q linearly independent families of solutions, where

q=n-rq=n-r

and

r=rank(𝐀)r=\text{rank}\left(\mathbf{A}\right)

The value q is referred to as the nullity of matrix A. The q linearly dependent equations in A are the null space of A.

”Solving” an underdetermined set of equations usually boils down to solving a fully determined r × r system (known as the range of A) and adding this solution to any linear combination of the other q vectors of A. A numerical procedure that solves the crux of this problem is known as singular value decomposition (or SVD). A singular value decomposition constructs a set of orthonormal bases for the null space and range of A.