In my case, I am calling an underdetermined system as a system of linear equations where there are fewer equations than variables (unknowns). My textbook says the answer is false, however the internet says otherwise.

On the outside, it makes sense that an underdetermined system can't have a unique solution, but I am leaning towards trusting the internet on this one. Can someone explain how a unique solution exists? A proof might be helpful too, although hopefully not too complex.

  • 3
    $\begingroup$ If there are some more limitations other then the equations themselves, the textbook is right. For example, $x+y=2$ has unique solution if $x,y$ are from $\mathbb{N}$. $\endgroup$ – Lazar Ljubenović Oct 5 '12 at 8:23
  • $\begingroup$ @Lazar: that depends on whether $0 \in \mathbb{N} or not $\endgroup$ – Henry Oct 5 '12 at 8:35

An underdetermined system is one with fewer equations than unknowns, so we can write this as a matrix equation $Ax = b$ with $A$ a matrix that has fewer rows than columns. This implies that solutions, if they exist, will not be unique. Two ways to see this:

Method 1. If you solve the equation $Ax = b$ by row reducing $A$ into echelon form, you will find that not every column in the echelon form can have a pivot. Therefore, when you write down the general solution, there will be free variables, leading to an infinite number of solutions.

Method 2. Since $A$ has fewer rows than columns, then $A$ is an $m \times n$ matrix with $m < n$. Then $\mathrm{rank}(A) \le m$, and since $\mathrm{rank}(A) + \mathrm{nullity}(A) = n$, then $\mathrm{nullity}(A) = n - \mathrm{rank}(A) \ge n - m > 0$. Therefore the null space of $A$ has dimension greater than $0$, so if $x_p$ is a particular solution to the equation, then any vector of the form $x_p + h$ is also a solution for any $h \in \mathrm{Nul}(A)$, and there are infinitely many choices for $h$.

  • $\begingroup$ So only specific conditions or constraints will allow underdetermined systems to have a unique solution? Or rather, if we simply only have a set of equations where we have more unknowns than equations, then there will never exist a unique solution? $\endgroup$ – krikara Oct 5 '12 at 16:20
  • 1
    $\begingroup$ Right, if there are specific conditions or constraints, then we could have unique solutions. However, an additional condition/constraint is essentially like another equation, and it could even break the linearity of the problem, in which case all the above theory just doesn't work anymore. $\endgroup$ – Christopher A. Wong Oct 5 '12 at 17:56

When solving $Ax=b$, with more unknown than equations, $A\in\mathbb{R}^{m\times n}$ with $m<n$.

Also $\operatorname{rank} A\leq m<n$. Since the linear system has a unique solution when $\operatorname{rank} A=n$, this can never occur.

As @Lazar commented, if there are additional conditions, you can get a unique solution. The linear equations don't provide the uniqueness though; the additional conditions do.

  • $\begingroup$ See @Christopher A Wong's answer for a more detailed response. $\endgroup$ – Daryl Oct 5 '12 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.