Supersaturated and Undersaturated Systems
Definition1
Consider the following linear system for matrix :
If , then there are more constraints than unknowns, and such a linear system is called an overdetermined system.
If , then there are less constraints than unknowns, and such a linear system is called an underdetermined system.
Theorem 1
Consider the linear system for matrix with rank of .
The general solution of the above linear system has parameters.
Proof
First, by the dimension theorem, . Then, from the following theorem, the number of parameters equals the number of nullities.
Let be any solution of . Let be the basis of . Then, every solution of can be expressed as follows:
This means that the number of parameters is equal to .
■
Theorem 2
Consider the following linear system for matrix :
Overdetermined
If the linear system is overdetermined, i.e., , then the linear system doesn’t have a solution for at least one vector in , meaning it doesn’t have a general solution.
Underdetermined
If the linear system is underdetermined, i.e., , then the linear system either has no solution for all vectors in or has infinitely many solutions.
Proof
Overdetermined
If , the column vectors of are in number , so cannot be spanned (since the number of vectors is less than the number of dimensions). Therefore, there exists at least one vector that does not belong to the column space of .
The necessary and sufficient condition for the linear system to have a solution is that is an element of the column space of .
According to the auxiliary theorem, does not have a solution.
Underdetermined
Assume .
If there is no solution
Then the proof is complete.
If there is a solution
If there is a solution, then by Theorem 1, the general solution has parameters. is at most the lesser of and .
This implies that the general solution of the linear system has more than one parameter, meaning that if there is a solution, it is infinitely many.
■
Howard Anton, Elementary Linear Algebra: Aplications Version (12th Edition, 2019), p259 ↩︎