Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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}$. –  Lazar Ljubenović Oct 5 '12 at 8:23
    
@Lazar: that depends on whether $0 \in \mathbb{N} or not –  Henry Oct 5 '12 at 8:35
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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? –  krikara Oct 5 '12 at 16:20
    
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. –  Christopher A. Wong Oct 5 '12 at 17:56
add comment

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.

share|improve this answer
    
See @Christopher A Wong's answer for a more detailed response. –  Daryl Oct 5 '12 at 8:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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