Underdetermined system

Last updated March 07, 2021

In mathematics, a system of linear equations or a system of polynomial equations is considered underdetermined if there are fewer equations than unknowns^[1] (in contrast to an overdetermined system, where there are more equations than unknowns). The terminology can be explained using the concept of constraint counting. Each unknown can be seen as an available degree of freedom. Each equation introduced into the system can be viewed as a constraint that restricts one degree of freedom.

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 underdetermined case, by contrast, occurs when the system has been underconstrained—that is, when the unknowns outnumber the equations.

Solutions of underdetermined systems

An underdetermined linear system has either no solution or infinitely many solutions.

For example,

{\begin{aligned}x+y+z&=1\\x+y+z&=0\end{aligned}}

is an underdetermined system without any solution; any system of equations having no solution is said to be inconsistent. On the other hand, the system

{\begin{aligned}x+y+z&=1\\x+y+2z&=3\end{aligned}}

is consistent and has an infinitude of solutions, such as (x, y, z) =(1, −2, 2), (2, −3, 2), and (3, −4, 2). All of these solutions can be characterized by first subtracting the first equation from the second, to show that all solutions obey z = 2; using this in either equation shows that any value of y is possible, with x = −1 − y.

More specifically, according to the Rouché–Capelli theorem, any system of linear equations (underdetermined or otherwise) is inconsistent if the rank of the augmented matrix is greater than the rank of the coefficient matrix. 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 k free parameters where k is the difference between the number of variables and the rank.

There are algorithms to decide whether an underdetermined system has solutions, and if it has any, to express all solutions as linear functions of k of the variables (same k as above). The simplest one is Gaussian elimination. See System of linear equations for more details.

Homogeneous case

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 vector space, whose dimension is the difference between the number of unknowns and the rank of the matrix of the system.

Underdetermined polynomial systems

The main property of linear underdetermined systems, of having either no solution or infinitely many, extends to systems of polynomial equations in the following way.

A system of polynomial equations which has fewer equations than unknowns is said to be underdetermined. It has either infinitely many complex solutions (or, more generally, solutions in an algebraically closed field) or is inconsistent. It is inconsistent if and only if 0 = 1 is a linear combination (with polynomial coefficients) of the equations (this is Hilbert's Nullstellensatz). If an underdetermined system of t equations in n variables (t < n) has solutions, then the set of all complex solutions is an algebraic set of dimension at least n - t. If the underdetermined system is chosen at random the dimension is equal to n - t with probability one.

Underdetermined systems with other constraints and in optimization problems

In general, an underdetermined system of linear equations has an infinite number of solutions, if any. However, in optimization problems 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 objective function.

Some problems specify that one or more of the variables are constrained to take on integer values. An integer constraint leads to integer programming and Diophantine equations problems, which may have only a finite number of solutions.

Another kind of constraint, which appears in coding theory, especially in error correcting codes and signal processing (for example compressed sensing), 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.

Related Research Articles

Diophantine equation Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is a polynomial equation, usually involving two or more unknowns, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

In mathematics, an equation is a statement that asserts the equality of two expressions, which are connected by the equals sign "=". The word equation and its cognates in other languages may have subtly different meanings; for example, in French an équation is defined as containing one or more variables, while in English, any equality is an equation.

Elementary algebra Basic concepts of algebra

Elementary algebra encompasses some of the basic concepts of algebra, one of the main branches of mathematics. It is typically taught to secondary school students and builds on their understanding of arithmetic. Whereas arithmetic deals with specified numbers, algebra introduces quantities without fixed values, known as variables. This use of variables entails use of algebraic notation and an understanding of the general rules of the operators introduced in arithmetic. Unlike abstract algebra, elementary algebra is not concerned with algebraic structures outside the realm of real and complex numbers.

Polynomial In mathematics, sum of products of variables, power of variables, and coefficients

In mathematics, a polynomial is an expression consisting of variables and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponentiation of variables. An example of a polynomial of a single indeterminate $x$ is $x 2 - 4 x + 7$ . An example in three variables is $x 3 + 2 xyz 2 - yz + 1$ .

In mathematics, a system of linear equations is a collection of one or more linear equations involving the same set of variables. For example,

In linear algebra, Cramer's rule is an explicit formula for the solution of a system of linear equations with as many equations as unknowns, valid whenever the system has a unique solution. It expresses the solution in terms of the determinants of the (square) coefficient matrix and of matrices obtained from it by replacing one column by the column vector of right-hand-sides of the equations. It is named after Gabriel Cramer (1704–1752), who published the rule for an arbitrary number of unknowns in 1750, although Colin Maclaurin also published special cases of the rule in 1748.

In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.

In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form

In mathematics, an algebraic equation or polynomial equation is an equation of the form

In mathematics, to solve an equation is to find its solutions, which are the values that fulfill the condition stated by the equation, consisting generally of two expressions related by an equals sign. When seeking a solution, one or more variables are designated as unknowns. A solution is an assignment of values to the unknown variables that makes the equality in the equation true. In other words, a solution is a value or a collection of values such that, when substituted for the unknowns, the equation becomes an equality. A solution of an equation is often called a root of the equation, particularly but not only for polynomial equations. The set of all solutions of an equation is its solution set.

Symmetry in mathematics Symmetry in mathematics

Symmetry occurs not only in geometry, but also in other branches of mathematics. Symmetry is a type of invariance: the property that a mathematical object remains unchanged under a set of operations or transformations.

In linear algebra, an augmented matrix is a matrix obtained by appending the columns of two given matrices, usually for the purpose of performing the same elementary row operations on each of the given matrices.

In mathematics, a surface is a generalization of a plane, which is not necessarily flat – that is, the curvature is not necessarily zero. This is analogous to a curve generalizing a straight line. There are many more precise definitions, depending on the context and the mathematical tools that are used to analyze the surface.

In linear algebra, a coefficient matrix is a matrix consisting of the coefficients of the variables in a set of linear equations. The matrix is used in solving systems of linear equations.

In mathematics, particularly in algebra, an indeterminate system is a system of simultaneous equations which has more than one solution. In the case of a linear system, the system may be said to be underspecified, in which case the presence of more than one solution would imply an infinite number of solutions, but that property does not extend to nonlinear systems.

In mathematics, a system of equations is considered overdetermined if there are more equations than unknowns. An overdetermined system is almost always inconsistent when constructed with random coefficients. However, an overdetermined system will have solutions in some cases, for example if some equation occurs several times in the system, or if some equations are linear combinations of the others.

A system of polynomial equations is a set of simultaneous equations $f 1 = 0, ..., f h = 0$ where the $f i$ are polynomials in several variables, say $x 1, ..., x n$ , over some field $k$ .

In linear algebra, the Rouché–Capelli theorem determines the number of solutions for a system of linear equations, given the rank of its augmented matrix and coefficient matrix. The theorem is variously known as the:

In mathematics and particularly in algebra, a linear or nonlinear system of equations is called consistent if there is at least one set of values for the unknowns that satisfies each equation in the system—that is, when substituted into each of the equations, they make each equation hold true as an identity. In contrast, a linear or non linear equation system is called inconsistent if there is no set of values for the unknowns that satisfies all of the equations.

References

↑ Biswa Nath Datta (4 February 2010). Numerical Linear Algebra and Applications, Second Edition. SIAM. pp. 263–. ISBN 978-0-89871-685-6.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Datta2010-1] Biswa Nath Datta (4 February 2010). Numerical Linear Algebra and Applications, Second Edition. SIAM. pp. 263–. ISBN 978-0-89871-685-6.

[1]