📂Matrix Algebra

Supersaturated and Undersaturated Systems

Definition¹

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

Dimension Theorem

$$ \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$.

  Auxiliary Theorem

  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.

■