Overdetermined system

From Wikipedia, the free encyclopedia

In mathematics, a system of linear equations is considered overdetermined if there are more equations than unknowns.^[1]

The terminology is justified in terms of a simple concept idea of counting constants. Each equation to satisfy as a constraint can be seen as using up one degree of freedom. Therefore the critical case, according to this kind of commonsense approach, is when the number of equations and the number of independent variables is the same.

1 Discussion
2 In general use
3 See also
4 References

[edit] Discussion

In mathematical detail, it requires more careful discussion to get accurate statements. Considering a system of linear equations

L_i = 0

for 1 ≤ i ≤ M, in variables

X₁, X₂, ..., X_N,

then

X₁ = X₂ = ... = X_N = 0

is always a solution. When

M < N

the system is underdetermined and there are always further solutions. In fact the dimension of the space of solutions is always at least

N − M.

For M ≥ N, there may be no solution other than all values being 0. There will be other solutions just when the system of equations has an adequate number of dependencies, so that the number of effective constraints is less than the apparent number M; more precisely the system must reduce to at most N − 1 equations. All we can be sure about is that it will reduce to at most N. This deals with the homogeneous equation case.

The inhomogeneous case

L_i = c_i

with any constants on the RHS is slightly different. Here there is no solution to be found by inspection; and there is another phenomenon of incompatible equations, such as

X₁ = 1, with

X₁ = 2.

If M > N, the excess equations must reduce to ones that already follow from N of them, for there to be any solution at all.

The discussion is more convincing, perhaps, when translated into the geometric language of intersecting hyperplanes. The homogeneous case applies to hyperplanes through a given point, taken as origin of coordinates. The inhomogeneous case is for general hyperplanes, which may therefore exhibit parallelism, or form prisms. A sequence of hyperplanes

H₁, H₂, ..., H_M

gives rise to intersections of the first k, which are expected to drop in dimension 1 each time. If M > N, the dimension of the ambient space, we expect the intersection to be empty, and this is precisely the overdetermined case.