25:
420:. If, on the other hand, the ranks of these two matrices are equal, the system must have at least one solution; since in an underdetermined system this rank is necessarily less than the number of unknowns, there are indeed an infinitude of solutions, with the general solution having
160:
Therefore, the critical case (between overdetermined and underdetermined) occurs when the number of equations and the number of free variables are equal. For every variable giving a degree of freedom, there exists a corresponding constraint removing a degree of freedom. The
459:
The homogeneous (with all constant terms equal to zero) underdetermined linear system always has non-trivial solutions (in addition to the trivial solution where all the unknowns are zero). There are an infinity of such solutions, which form a
348:
256:
589:), consists in an upper bound on the number of variables which may be different from zero. In error correcting codes, this bound corresponds to the maximal number of errors that may be corrected simultaneously.
276:
187:
42:
555:
that are subject to linear equality constraints, only one of the solutions is relevant, namely the one giving the highest or lowest value of an
271:
182:
634:
380:. All of these solutions can be characterized by first subtracting the first equation from the second, to show that all solutions obey
89:
520:
108:
562:
Some problems specify that one or more of the variables are constrained to take on integer values. An integer constraint leads to
61:
624:
477:
435:
to decide whether an underdetermined system has solutions, and if it has any, to express all solutions as linear functions of
165:
case, by contrast, occurs when the system has been underconstrained—that is, when the unknowns outnumber the equations.
68:
130:
46:
405:
603:
496:
75:
551:
In general, an underdetermined system of linear equations has an infinite number of solutions, if any. However, in
488:
448:
262:
126:
57:
35:
552:
476:
The main property of linear underdetermined systems, of having either no solution or infinitely many, extends to
154:
656:
261:
is an underdetermined system without any solution; any system of equations having no solution is said to be
578:
146:
598:
567:
465:
409:
138:
141:, where there are more equations than unknowns). The terminology can be explained using the concept of
444:
82:
563:
142:
661:
586:
556:
417:
150:
630:
582:
413:
487:. It has either infinitely many complex solutions (or, more generally, solutions in an
483:
A system of polynomial equations which has fewer equations than unknowns is said to be
408:, any system of linear equations (underdetermined or otherwise) is inconsistent if the
173:
An underdetermined linear system has either no solution or infinitely many solutions.
650:
574:
516:
461:
495:
is a linear combination (with polynomial coefficients) of the equations (this is
122:
24:
533:. If the underdetermined system is chosen at random the dimension is equal to
432:
547:
Underdetermined systems with other constraints and in optimization problems
464:, whose dimension is the difference between the number of unknowns and the
343:{\displaystyle {\begin{aligned}x+y+z&=1\\x+y+2z&=3\end{aligned}}}
251:{\displaystyle {\begin{aligned}x+y+z&=1\\x+y+z&=0\end{aligned}}}
428:
is the difference between the number of variables and the rank.
153:. Each equation introduced into the system can be viewed as a
137:
if there are fewer equations than unknowns (in contrast to an
18:
515:) has solutions, then the set of all complex solutions is an
570:
problems, which may have only a finite number of solutions.
353:
is consistent and has an infinitude of solutions, such as
626:
Numerical Linear
Algebra and Applications, Second Edition
491:) or is inconsistent. It is inconsistent if and only if
387:; using this in either equation shows that any value of
274:
185:
49:. Unsourced material may be challenged and removed.
342:
250:
573:Another kind of constraint, which appears in
8:
275:
273:
186:
184:
109:Learn how and when to remove this message
615:
157:that restricts one degree of freedom.
7:
623:Biswa Nath Datta (4 February 2010).
404:More specifically, according to the
169:Solutions of underdetermined systems
47:adding citations to reliable sources
499:). If an underdetermined system of
472:Underdetermined polynomial systems
14:
416:is greater than the rank of the
265:. On the other hand, the system
23:
478:systems of polynomial equations
443:as above). The simplest one is
34:needs additional citations for
131:system of polynomial equations
1:
468:of the matrix of the system.
604:Regularization (mathematics)
149:can be seen as an available
678:
489:algebraically closed field
449:System of linear equations
127:system of linear equations
497:Hilbert's Nullstellensatz
58:"Underdetermined system"
629:. SIAM. pp. 263–.
439:of the variables (same
579:error correcting codes
543:with probability one.
480:in the following way.
424:free parameters where
406:Rouché–Capelli theorem
344:
252:
599:Overdetermined system
568:Diophantine equations
553:optimization problems
345:
253:
139:overdetermined system
445:Gaussian elimination
272:
183:
43:improve this article
16:Mathematical concept
564:integer programming
143:constraint counting
587:compressed sensing
557:objective function
451:for more details.
418:coefficient matrix
391:is possible, with
340:
338:
248:
246:
636:978-0-89871-685-6
583:signal processing
151:degree of freedom
119:
118:
111:
93:
669:
641:
640:
620:
577:, especially in
542:
532:
494:
455:Homogeneous case
414:augmented matrix
400:
386:
379:
375:
371:
368:
349:
347:
346:
341:
339:
257:
255:
254:
249:
247:
114:
107:
103:
100:
94:
92:
51:
27:
19:
677:
676:
672:
671:
670:
668:
667:
666:
647:
646:
645:
644:
637:
622:
621:
617:
612:
595:
549:
534:
524:
492:
485:underdetermined
474:
457:
392:
381:
377:
373:
369:
354:
337:
336:
326:
305:
304:
294:
270:
269:
245:
244:
234:
216:
215:
205:
181:
180:
171:
163:underdetermined
135:underdetermined
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
675:
673:
665:
664:
659:
657:Linear algebra
649:
648:
643:
642:
635:
614:
613:
611:
608:
607:
606:
601:
594:
591:
548:
545:
473:
470:
456:
453:
351:
350:
335:
332:
329:
327:
325:
322:
319:
316:
313:
310:
307:
306:
303:
300:
297:
295:
293:
290:
287:
284:
281:
278:
277:
259:
258:
243:
240:
237:
235:
233:
230:
227:
224:
221:
218:
217:
214:
211:
208:
206:
204:
201:
198:
195:
192:
189:
188:
170:
167:
133:is considered
117:
116:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
674:
663:
660:
658:
655:
654:
652:
638:
632:
628:
627:
619:
616:
609:
605:
602:
600:
597:
596:
592:
590:
588:
585:(for example
584:
580:
576:
575:coding theory
571:
569:
565:
560:
558:
554:
546:
544:
541:
537:
531:
527:
522:
518:
517:algebraic set
514:
510:
506:
503:equations in
502:
498:
490:
486:
481:
479:
471:
469:
467:
463:
454:
452:
450:
446:
442:
438:
434:
429:
427:
423:
419:
415:
411:
407:
402:
399:
395:
390:
384:
366:
362:
358:
333:
330:
328:
323:
320:
317:
314:
311:
308:
301:
298:
296:
291:
288:
285:
282:
279:
268:
267:
266:
264:
241:
238:
236:
231:
228:
225:
222:
219:
212:
209:
207:
202:
199:
196:
193:
190:
179:
178:
177:
176:For example,
174:
168:
166:
164:
158:
156:
152:
148:
144:
140:
136:
132:
128:
124:
113:
110:
102:
99:February 2018
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
625:
618:
572:
561:
550:
539:
535:
529:
525:
512:
508:
504:
500:
484:
482:
475:
462:vector space
458:
440:
436:
430:
425:
421:
403:
397:
393:
388:
382:
364:
360:
356:
352:
263:inconsistent
260:
175:
172:
162:
159:
134:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
507:variables (
123:mathematics
651:Categories
610:References
433:algorithms
431:There are
378:(3, −4, 2)
374:(2, −3, 2)
370:(1, −2, 2)
155:constraint
69:newspapers
662:Equations
523:at least
521:dimension
593:See also
412:of the
396:= −1 −
147:unknown
145:. Each
83:scholar
633:
447:. See
376:, and
85:
78:
71:
64:
56:
511:<
493:0 = 1
129:or a
90:JSTOR
76:books
631:ISBN
581:and
566:and
466:rank
410:rank
125:, a
62:news
519:of
385:= 2
367:) =
121:In
45:by
653::
559:.
538:-
528:-
401:.
372:,
363:,
359:,
639:.
540:t
536:n
530:t
526:n
513:n
509:t
505:n
501:t
441:k
437:k
426:k
422:k
398:y
394:x
389:y
383:z
365:z
361:y
357:x
355:(
334:3
331:=
324:z
321:2
318:+
315:y
312:+
309:x
302:1
299:=
292:z
289:+
286:y
283:+
280:x
242:0
239:=
232:z
229:+
226:y
223:+
220:x
213:1
210:=
203:z
200:+
197:y
194:+
191:x
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
