10
$\begingroup$

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.

$\endgroup$
2
  • 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$ Oct 5, 2012 at 8:23
  • $\begingroup$ @Lazar: that depends on whether $0 \in \mathbb{N} or not $\endgroup$
    – Henry
    Oct 5, 2012 at 8:35

2 Answers 2

26
$\begingroup$

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

$\endgroup$
4
  • $\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, 2012 at 16:20
  • 2
    $\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$ Oct 5, 2012 at 17:56
  • $\begingroup$ what are these specific conditions/constraints? $\endgroup$
    – Thana
    May 2, 2022 at 5:41
  • 1
    $\begingroup$ @Thana This is problem dependent. But if the system is purely a linear system, then unique solutions can only exist if the corresponding matrix has a trivial null space. $\endgroup$ May 5, 2022 at 2:20
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .