Supersaturated and Undersaturated Systems
Definition1
Consider the following linear system for matrix $A$:
$$ A \mathbf{x} = \mathbf{b} $$
If $m \gt n$, then there are more constraints than unknowns, and such a linear system is called an overdetermined system.
If $m \lt n$, 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 $A$ with rank $r$ of $m \times n$.
$$ A \mathbf{x} = \mathbf{b} $$
The general solution of the above linear system has $n-r$ parameters.
Proof
$$ \rank(A) + \nullity(A) = \dim(A) $$
First, by the dimension theorem, $\nullity(A) = n-r$. Then, from the following theorem, the number of parameters equals the number of nullities.
Let $\mathbf{x}_{0}$ be any solution of $A\mathbf{x} = \mathbf{b}$. Let $S= \left\{ \mathbf{v}_{1}, \mathbf{v}_{2}, \dots, \mathbf{v}_{k} \right\}$ be the basis of $\mathcal{N}(A)$. Then, every solution of $A\mathbf{x} = \mathbf{b}$ can be expressed as follows:
$$ \mathbf{x} = \mathbf{x}_{0} + c_{1}\mathbf{v}_{1} + c_{2}\mathbf{v}_{2} + \cdots + c_{k}\mathbf{v}_{k} $$
This means that the number of parameters is equal to $\nullity(A)$.
■
Theorem 2
Consider the following linear system for matrix $A$:
$$ A \mathbf{x} = \mathbf{b} $$
Overdetermined
If the linear system is overdetermined, i.e., $m \gt n$, then the linear system doesn’t have a solution for at least one vector $\mathbf{b}$ in $\mathbb{R}^{m}$, meaning it doesn’t have a general solution.
Underdetermined
If the linear system is underdetermined, i.e., $m \lt n$, then the linear system either has no solution for all vectors $\mathbf{b}$ in $\mathbb{R}^{m}$ or has infinitely many solutions.
Proof
Overdetermined
If $m \gt n$, the column vectors of $A$ are in number $n$, so $\mathbb{R}^{m}$ cannot be spanned (since the number of vectors is less than the number of dimensions). Therefore, there exists at least one vector $\mathbf{b}$ that does not belong to the column space of $A$.
The necessary and sufficient condition for the linear system $A \mathbf{x} = \mathbf{b}$ to have a solution is that $\mathbf{b}$ is an element of the column space of $A$.
According to the auxiliary theorem, $A \mathbf{x} = \mathbf{b}$ does not have a solution.
Underdetermined
Assume $m \lt n$.
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 $n-r$ parameters. $r = \rank (A)$ is at most the lesser of $m$ and $n$.
$$ n-r \le n-m > 0 $$
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 ↩︎