mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a

system of linear equations In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables. For example, :\begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three ...

or a

system of polynomial equations A system of polynomial equations (sometimes simply a polynomial system) is a set of simultaneous equations where the are polynomials in several variables, say , over some field . A ''solution'' of a polynomial system is a set of values for the ...

is considered underdetermined if there are fewer equations than unknowns (in contrast to an

overdetermined system In mathematics, a system of equations is considered overdetermined if there are more equations than unknowns. An overdetermined system is almost always inconsistent (it has no solution) when constructed with random coefficients. However, an over ...

, where there are more equations than unknowns). The terminology can be explained using the concept of constraint counting. Each

unknown Unknown or The Unknown may refer to: Film * The Unknown (1915 comedy film), ''The Unknown'' (1915 comedy film), a silent boxing film * The Unknown (1915 drama film), ''The Unknown'' (1915 drama film) * The Unknown (1927 film), ''The Unknown'' (1 ...

can be seen as an available

degree of freedom Degrees of freedom (often abbreviated df or DOF) refers to the number of independent variables or parameters of a thermodynamic system. In various scientific fields, the word "freedom" is used to describe the limits to which physical movement or ...

. 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
x+y+z&=1\\
x+y+z&=0
\end

is an underdetermined system without any solution; any system of equations having no solution is said to be

inconsistent In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...

. On the other hand, the system :

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

is consistent and has an infinitude of solutions, such as , , and . All of these solutions can be characterized by first subtracting the first equation from the second, to show that all solutions obey ; using this in either equation shows that any value of ''y'' is possible, with . More specifically, according to the

Rouché–Capelli theorem 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: * Rouché–Capelli theore ...

, any system of linear equations (underdetermined or otherwise) is inconsistent if the

rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * ...

of the

augmented matrix 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. Given the matrices and , where ...

is greater than the rank of the

coefficient matrix 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. Coefficient matrix In general, a system with ''m'' linear ...

. 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

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s 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 In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...

. See

System of linear equations In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables. For example, :\begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three ...

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 In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...

, whose dimension is the difference between the number of unknowns and the

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 In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in . Examples As an example, the field of real numbers is not algebraically closed, because ...

) or is inconsistent. It is inconsistent if and only if is a linear combination (with polynomial coefficients) of the equations (this is

Hilbert's Nullstellensatz In mathematics, Hilbert's Nullstellensatz (German for "theorem of zeros," or more literally, "zero-locus-theorem") is a theorem that establishes a fundamental relationship between geometry and algebra. This relationship is the basis of algebraic ...

). 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 Algebraic may refer to any subject related to algebra in mathematics and related branches like algebraic number theory and algebraic topology. The word algebra itself has several meanings. Algebraic may also refer to: * Algebraic data type, a data ...

dimension In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...

at least . If the underdetermined system is chosen at random the dimension is equal to 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 In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...

. Some problems specify that one or more of the variables are constrained to take on integer values. An integer constraint leads to

integer programming An integer programming problem is a mathematical optimization or Constraint satisfaction problem, feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programmin ...

and

Diophantine equations In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...

problems, which may have only a finite number of solutions. Another kind of constraint, which appears in

coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...

, especially in

error correcting codes In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...

and

signal processing Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, and scientific measurements. Signal processing techniq ...

(for example

compressed sensing Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a Signal (electronics), signal, by finding solutions to Underdetermined ...

), 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.

References

{{reflist Linear algebra Equations

Solutions of underdetermined systems

Homogeneous case

Underdetermined polynomial systems

Underdetermined systems with other constraints and in optimization problems

See also

References