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 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. The terminology can be described in terms of 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 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. The overdetermined case occurs when the system has been overconstrained — that is, when the equations outnumber the unknowns. In contrast, the underdetermined case occurs when the system has been underconstrained — that is, when the number of equations is fewer than the number of unknowns. Such systems usually have an infinite number of solutions.
Overdetermined linear systems of equations
An example in two dimensions
Consider the system of 3 equations and 2 unknowns (X and Y), which is overdetermined because 3 > 2, and which corresponds to Diagram #1:
Y = − 2 X − 1 Y = 3 X − 2 Y = X + 1. {\displaystyle {\begin{aligned}Y&=-2X-1\\Y&=3X-2\\Y&=X+1.\end{aligned}}}
There is one solution for each pair of linear equations: for the first and second equations (0.2, −1.4), for the first and third (−2/3, 1/3), and for the second and third (1.5, 2.5). However, there is no solution that satisfies all three simultaneously. Diagrams #2 and 3 show other configurations that are inconsistent because no point is on all of the lines. Systems of this variety are deemed inconsistent. The only cases where the overdetermined system does in fact have a solution are demonstrated in Diagrams #4, 5, and 6. These exceptions can occur only when the overdetermined system contains enough linearly dependent equations that the number of independent equations does not exceed the number of unknowns. Linear dependence means that some equations can be obtained from linearly combining other equations. For example, Y = X + 1 and 2Y = 2X + 2 are linearly dependent equations because the second one can be obtained by taking twice the first one.
Matrix form Any system of linear equations can be written as a matrix equation. The previous system of equations (in Diagram #1) can be written as follows:
[ 2 1 − 3 1 − 1 1 ] [ X Y ] = [ − 1 − 2 1 ] {\displaystyle {\begin{bmatrix}2&1\\-3&1\\-1&1\\\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}-1\\-2\\1\end{bmatrix}}}
Notice that the rows of the coefficient matrix (corresponding to equations) outnumber the columns (corresponding to unknowns), meaning that the system is overdetermined. The rank of this matrix is 2, which corresponds to the number of dependent variables in the system. A linear system is consistent if and only if the coefficient matrix has the same rank as its augmented matrix (the coefficient matrix with an extra column added, that column being the column vector of constants). The augmented matrix has rank 3, so the system is inconsistent. The nullity is 0, which means that the null space contains only the zero vector and thus has no basis. In linear algebra the concepts of row space, column space and null space are important for determining the properties of matrices. The informal discussion of constraints and degrees of freedom above relates directly to these more formal concepts.
… excerpt ends here. Continue reading the full article.
