Under-Constrained System

Definition

${\mathbf{A}}_{m\times n}\mathbf{x}=\mathbf{b}$ where $m<n$

The number of unknowns(n) > the number of equations(m) usually has infinitely many or no solutions.

Solution

Homogeneous Under-Constrained System

solving the homogeneous under-constrained linear system $\mathbf{Ax}=0$

1. Obtain $\mathbf{Rx}=0$ and identify pivot and free variables where $\mathbf{R}$ is the reduced Echelon matrix.
2. Find Special solution
   1. set a free variable = 1, and others = 0
   2. solve $\mathbf{Rx}=0$ to find the pivot variables

Example

$\mathbf{Ax}=0\iff \left[\begin{array}{cccc}1& 3& 3& 2\\ 2& 6& 9& 7\\ -1& -3& 3& 4\end{array}\right]\left[\begin{array}{c}u\\ v\\ w\\ y\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$

1. Find the reduced Echelon matrix $\left[\begin{array}{cccc}1& 3& 3& 2\\ 2& 6& 9& 7\\ -1& -3& 3& 4\end{array}\right]\stackrel{\text{Echelon matrix}}{\to }\left[\begin{array}{cccc}1& 3& 3& 2\\ 0& 0& 3& 3\\ 0& 0& 0& 0\end{array}\right]\stackrel{\text{Reduced Echelon matrix}}{\to }\left[\begin{array}{cccc}1& 3& 0& -1\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right]$
2. $\mathbf{Rx}=0\iff \left[\begin{array}{cccc}1& 3& 0& -1\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right]\left[\begin{array}{c}u\\ v\\ w\\ y\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$ where $u,w$ are the pivot variables and $v,y$ are the free variables.
   1. Set a free variable $v=1$ and others $y=0$ and find the pivot variables $\left[\begin{array}{cccc}1& 3& 0& -1\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right]\left[\begin{array}{c}u\\ 1\\ w\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\Rightarrow \{\begin{array}{ll}u+3=0& \Rightarrow u=-3\\ w=0& \end{array}\Rightarrow \left[\begin{array}{c}u\\ v\\ w\\ y\end{array}\right]=\left[\begin{array}{c}-3\\ 1\\ 0\\ 0\end{array}\right]$
   2. Set a free variable $y=0$ and others $v=0$ and find the pivot variables $\left[\begin{array}{cccc}1& 3& 0& -1\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right]\left[\begin{array}{c}u\\ 0\\ w\\ 1\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\Rightarrow \{\begin{array}{ll}u-1=0& \Rightarrow u=1\\ w+1=0& \Rightarrow w=-1\end{array}\Rightarrow \left[\begin{array}{c}u\\ v\\ w\\ y\end{array}\right]=\left[\begin{array}{c}1\\ 0\\ -1\\ 1\end{array}\right]$
3. Now, the solutions^[null space] are all linear combinations of special solution $\mathbf{x}=a\left[\begin{array}{c}-3\\ 1\\ 0\\ 0\end{array}\right]+b\left[\begin{array}{c}1\\ 0\\ -1\\ 1\end{array}\right]$

Non-Homogeneous Under-Constrained System

solving the non-homogeneous under-constrained linear system $\mathbf{Ax}=\mathbf{b}\ne 0$

1. Find the special solution for $\mathbf{Ax}=0$ and find a particular solution from $\mathbf{d}$ obtained by Gauss Elimination $\mathbf{Rx}=\mathbf{d}$ where $\mathbf{R}$ is the reduced Echelon matrix
2. Sum the special solution and particular solution

Example

$\mathbf{Ax}=\mathbf{b}\iff \left[\begin{array}{cccc}2& 4& 6& 4\\ 2& 5& 7& 6\\ 2& -3& 5& 2\end{array}\right]\left[\begin{array}{c}u\\ v\\ w\\ y\end{array}\right]=\left[\begin{array}{c}4\\ 3\\ 5\end{array}\right]$

1. Find the reduced Echelon matrix $\left[\begin{array}{cccccc}2& 4& 6& 4& |& 4\\ 2& 5& 7& 6& |& 3\\ 2& -3& 5& 2& |& 5\end{array}\right]\stackrel{\text{Echelon matrix}}{\to }\left[\begin{array}{cccccc}2& 4& 6& 4& |& 4\\ 0& 1& 1& 2& |& -1\\ 0& 0& 6& 12& |& -6\end{array}\right]\stackrel{\text{Reduced Echelon matrix}}{\to }\left[\begin{array}{cccccc}1& 0& 0& -4& |& 5\\ 0& 1& 0& 0& |& 0\\ 0& 0& 1& 2& |& -1\end{array}\right]$ where $\left[\begin{array}{cccc}1& 0& 0& -4\\ 0& 1& 0& 0\\ 0& 0& 1& 2\end{array}\right]$ is the $\mathbf{R}$ and $\left[\begin{array}{c}5\\ 0\\ -1\end{array}\right]$ is the $\mathbf{d}$
2. Find the special solution $a\left[\begin{array}{c}4\\ 0\\ -2\\ 0\end{array}\right]$ using the method of homogeneous equation
3. Find the particular solution $\left[\begin{array}{c}5\\ 0\\ -1\\ 0\end{array}\right]$ using $\mathbf{d}$
4. Now, the solution of $\mathbf{Ax}=\mathbf{b}$ are the sum of all linear combination of special solution and a particular solution $\mathbf{x}=a\left[\begin{array}{c}4\\ 0\\ -2\\ 0\end{array}\right]+\left[\begin{array}{c}5\\ 0\\ -1\\ 0\end{array}\right]$