Overdetermined System - Non-homogeneous Case

Non-homogeneous Case

In systems of linear equations, L_i=c_i for 1 ≤ i ≤ M, in variables X₁, X₂, ..., X_N the equations are sometimes linearly dependent; in fact the number of linearly independent equations cannot exceed N+1. We have the following possible cases for an overdetermined system with N unknowns and M equations (M>N).

• M = N+1 and all M equations are linearly independent. This case yields no solution. Example: x = 1, x = 2.
• M > N but only K equations (K < M and K ≤ N+1) are linearly independent. There exist three possible sub-cases of this:
  • K = N+1. This case yields no solutions. Example: 2x = 2, x = 1, x = 2.
  • K = N. This case yields either a single solution or no solution, the latter occurring when the coefficient vector of one equation can be replicated by a weighted sum of the coefficient vectors of the other equations but that weighted sum applied to the constant terms of the other equations does not replicate the one equation's constant term. Example with one solution: 2x = 2, x = 1. Example with no solution: 2x + 2y = 2, x + y = 1, x + y = 3.
  • K < N. This case yields either infinitely many solutions or no solution, the latter occurring as in the previous sub-case. Example with infinitely many solutions: 3x + 3y = 3, 2x + 2y = 2, x + y = 1. Example with no solution: 3x + 3y + 3z = 3, 2x + 2y + 2z = 2, x + y + z = 1, x + y + z = 4.

These results may be easier to understand by putting the augmented matrix of the coefficients of the system in row echelon form by using Gaussian elimination. This row echelon form is the augmented matrix of a system of equations that is equivalent to the given system (it has exactly the same solutions). The number of independent equations in the original system is the number of non-zero rows in the echelon form. The system is inconsistent (no solution) if and only if the last non-zero row in echelon form has only one non-zero entry that is in the last column (giving an equation 0 = c where c is a non-zero constant). Otherwise, there is exactly one solution when the number of non-zero rows in echelon form is equal to the number of unknowns, and there are infinitely many solutions when the number of non-zero rows is lower than the number of variables.

Putting it another way, according to the Rouché–Capelli theorem, any system of equations (overdetermined 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. The solution is unique if and only if the rank equals the number of variables. Otherwise the general solution has k free parameters where k is the difference between the number of variables and the rank; hence in such a case there are an infinitude of solutions.