How do I show that a system is both over-determined and under-determined? I am supposed to come up with a matrix that satisfies both but am not really sure I understand what types of equations would satisfy these criteria. If anyone could give me an example and maybe a format to go by, I would appreciate it.
Asked
Active
Viewed 9,228 times
3 Answers
4
I believe that, as pointed out in Overdetermined and underdetermined systems of equation put simply, thinking of the equations in a system making up a set of requests (equations) to a certain number of people (unknowns) is helpful to understand why systems can be overdetermined or underdetermined in the first place.
In your specific case, imagine to have 3 people, all waiting for a command from you. Finally, you speak and say:
- Bob, go fetch a bottle of water
- Bob, help me paint the house
- Lisa, do your homework
This is a real world example of a system that is both under and overdetermined. What makes it underdetermined is the fact that you had 3 people in front of you, and only addressed 2 of them, whereas giving conflicting commands to Bob makes it an overdetermined one.
Stephen Rauch
- 103
Ste_95
- 291
3
A system of linear equations is called over-determined if there are more equations than unknowns. For example:
$$ \begin{cases} x+y = 1\\2x+y = 1\\ 3x+y = 1\end{cases}$$
Often times for an over-determined system, as in the example above, there will be no solution. That is not to say however that every over-determined system has no solution however. There might be exactly one or infinitely many solutions.
For example, $\begin{cases} x+y=1\\ 2x+y = 1 \\ 3x+2y=2\end{cases}$ has one solution ($x=0,y=1$) and $\begin{cases}x+y=1\\ 2x+2y=2 \\ 3x+3y=3\end{cases}$ has infinitely many solutions (all of the form $x=1-y$).
A system of linear equations is called under-determined if there are more unknowns than equations. For example:
$$\begin{cases} x+y+z = 1\\ x+2y+z = 1\end{cases}$$
Often times for an under-determined system, as in the example above, there will be infinitely many solutions. That is not to say however that every under-determined system has infinitely many solutions however. It is possible that there are no solutions.
For example, $\begin{cases} x+y+z = 1\\ x+y+z = 2\end{cases}$ has no solution (else $2=1$ which is untrue). Note that for the under-determined systems, it is impossible to have only one unique solution. It will always be either infinitely many or none.
The way the terms are defined has the number of equations vs unknowns to be strictly different. As such you will fall into only one case or the other and never both at the same time.
-
ok, so if I need an over-determined system and an under-determined system, how do I come up with a matrix if they are so different? – Marie Apr 10 '15 at 16:12
-
Refer back to your lecture-notes or your book. It is possible that the definition your teacher is using is for "Equal to or greater number of equations vs unknowns" as opposed to "Strictly greater number of equations vs unknowns." Either that or the definition you are given has to do with location of pivot points in the reduced system (i.e. overdetermined $\leftrightarrow$ contradictory line, and underdetermined $\leftrightarrow$ free variable). Neither of those are the definition I know and use, and according to the definition I have given it is impossible for a single matrix to be both. – JMoravitz Apr 10 '15 at 16:17
-
@Marie it is possible also that you are misinterpreting the question. Perhaps they intend you to give an example of an underdetermined system and to give a separate example of an overdetermined system (as opposed to giving an example of a system that is simultaneously both over and underdetermined). – JMoravitz Apr 10 '15 at 16:19
-
This is the problem, I have no book or notes. I read matrix calculus and am working on regression and the generalized inverse equation. – Marie Apr 10 '15 at 16:20
-
with the information I have, it explains how an over and under-determined system can be both constrained and incomplete. Im just not sure how to show this – Marie Apr 10 '15 at 16:24
-
Depending on your definition of constrained and incomplete (I have not heard those terms in this context) if by constrained it means there is a contradiction and if by incomplete it means that there is a free variable, my example above $\begin{cases} x+y+z = 1\ x+y+z = 2\end{cases}$ satisfies exactly that statement. When row reducing you arrive at $\begin{array}{ccc|c} 1 & 1 & 1 & 1\ 0 & 0 & 0 & 1\end{array}$, which implies from the top line that $x$'s value is dependent on the values of $y$ and $z$, while $y$ and $z$ are allowed to be anything, and from the bottom line that $0=1$ no solutn – JMoravitz Apr 10 '15 at 16:36
-
ok, constrained says-that the right side has a compatibility condition and incomplete means that the solution is not unique – Marie Apr 10 '15 at 16:41
1
An over-determined system is a system of equations that has more equations than unknowns (e.g. three equations and two unknowns).
An under-determined system is a system of equations that has more unknowns than vectors (e.g. three unknowns and two equations).
The combination of the two leads to the critical case which is when you have the same number of equations as you do unknowns. The best case scenario of this would be to start in reduced row echelon form and work your way backwards to come up with an example of such a matrix.
alephnoughty
- 11
-
I agree with your answer except for the final paragraph. In my experience we use the terms over-determined and under-determined to mean "strictly more equations than unknowns" (strictly fewer respectively). As such, you cannot be in both situations at once. – JMoravitz Apr 10 '15 at 15:39
-
-
That is correct. I was attempting to try and make the concept clearer, but I can understand how this causes confusion. Edited. – alephnoughty Apr 10 '15 at 15:50
-
ok, what I am supposed to do is come up with a system that is both over and under-determined. I was told to start with an over-determined matrix but am not sure what I am supposed to get to. How do I show that it is both over and under? – Marie Apr 10 '15 at 18:07