logo

Supersaturated and Undersaturated Systems 📂Matrix Algebra

Supersaturated and Undersaturated Systems

Definition1

Consider the following linear system for matrix AA:

Ax=b A \mathbf{x} = \mathbf{b}

If m>nm \gt n, then there are more constraints than unknowns, and such a linear system is called an overdetermined system.

If m<nm \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 AA with rank rr of m×nm \times n.

Ax=b A \mathbf{x} = \mathbf{b}

The general solution of the above linear system has nrn-r parameters.

Proof

Dimension Theorem

rank(A)+nullity(A)=dim(A) \rank(A) + \nullity(A) = \dim(A)

First, by the dimension theorem, nullity(A)=nr\nullity(A) = n-r. Then, from the following theorem, the number of parameters equals the number of nullities.

Let x0\mathbf{x}_{0} be any solution of Ax=bA\mathbf{x} = \mathbf{b}. Let S={v1,v2,,vk}S= \left\{ \mathbf{v}_{1}, \mathbf{v}_{2}, \dots, \mathbf{v}_{k} \right\} be the basis of N(A)\mathcal{N}(A). Then, every solution of Ax=bA\mathbf{x} = \mathbf{b} can be expressed as follows:

x=x0+c1v1+c2v2++ckvk \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)\nullity(A).

Theorem 2

Consider the following linear system for matrix AA:

Ax=b A \mathbf{x} = \mathbf{b}

  • Overdetermined

    If the linear system is overdetermined, i.e., m>nm \gt n, then the linear system doesn’t have a solution for at least one vector b\mathbf{b} in Rm\mathbb{R}^{m}, meaning it doesn’t have a general solution.

  • Underdetermined

    If the linear system is underdetermined, i.e., m<nm \lt n, then the linear system either has no solution for all vectors b\mathbf{b} in Rm\mathbb{R}^{m} or has infinitely many solutions.

Proof

  • Overdetermined

    If m>nm \gt n, the column vectors of AA are in number nn, so Rm\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 b\mathbf{b} that does not belong to the column space of AA.

    Auxiliary Theorem

    The necessary and sufficient condition for the linear system Ax=bA \mathbf{x} = \mathbf{b} to have a solution is that b\mathbf{b} is an element of the column space of AA.

    According to the auxiliary theorem, Ax=bA \mathbf{x} = \mathbf{b} does not have a solution.

  • Underdetermined

    Assume m<nm \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 nrn-r parameters. r=rank(A)r = \rank (A) is at most the lesser of mm and nn.

      nrnm>0 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.


  1. Howard Anton, Elementary Linear Algebra: Aplications Version (12th Edition, 2019), p259 ↩︎