The Existence Criterion for Solutions

When Does a Linear System Have a Solution?

A system of linear equations is consistent if there is at least one choice of its unknowns that satisfies every equation. Row reduction makes this existence question visible: an equation whose coefficients are all zero can either impose no restriction, as in \(0=0\), or be impossible, as in \(0=1\). The important detail is the augmented entry on that row.

Consider a finite system with real unknowns \(x_1,\dots,x_n\). Write it as \(\mathbf{A}\mathbf{x}=\mathbf{b}\), where \(\mathbf{A}\in\mathbb{R}^{m\times n}\) is the coefficient matrix, \(\mathbf{x}\in\mathbb{R}^n\) is the column of unknowns, and \(\mathbf{b}\in\mathbb{R}^m\) is the column of right-hand sides. Its augmented matrix is \([\mathbf{A}\mid\mathbf{b}]\). An echelon form of this matrix is obtained using elementary row operations on the entire augmented matrix. Those operations preserve the solution set, so the original system and the system represented by the echelon form have exactly the same solutions.

The condition is about the coefficient columns, not about whether the whole row is zero. For example, \([0\;\;0\mid 0]\) represents \(0=0\), which every assignment satisfies. The row \([0\;\;0\mid 5]\) represents \(0=5\), which no assignment satisfies. An echelon form may contain either kind of row.

Why a Contradictory Row Rules Out Solutions

Proof. A contradictory row represents \(0=c\) for some \(c\ne0\). No values of the unknowns can satisfy this equation, since its left side is zero for every choice while its right side is nonzero. Thus the system represented by the echelon form has no solution. Elementary row operations preserve the solution set, so the original system has no solution either. \(\square\)

This direction is a direct obstruction: finding one contradictory row is enough to settle the question. If no such row appears, however, the absence of an obstruction alone does not yet exhibit a solution. We also need to show that the echelon equations can actually be satisfied.

Why No Contradictory Row Guarantees a Solution

In an echelon system with no contradictory row, every row whose coefficient entries are all zero must also have augmented entry zero. Such a row is \(0=0\) and imposes no restriction. Every other row has a leading nonzero coefficient, called its pivot; the pivot columns move to the right as we move down the nonzero rows.

Proof. Let the system have \(n\) unknowns. If every coefficient row is zero, the absence of a contradictory row means every augmented entry is zero as well. The system consists only of equations \(0=0\), so choosing all unknowns to be zero gives a solution.

Otherwise, consider the nonzero coefficient rows, in order from top to bottom. Their pivot columns are strictly increasing. Set every variable in a nonpivot column equal to zero. Starting at the last nonzero coefficient row and working upward, solve each row for the variable in its pivot column. This is possible because the pivot coefficient is nonzero, and every other variable appearing to its right has already been assigned a value or solved for. If row \(i\) has pivot in column \(j_i\), set

The denominator is nonzero by the definition of a pivot. This choice makes row \(i\) true, because its terms in columns before \(j_i\) have zero coefficients. Working upward assigns all pivot variables and satisfies every nonzero coefficient row. The remaining rows have zero coefficient entries and, since there is no contradictory row, zero augmented entries; they are equations \(0=0\). Thus all rows are satisfied, and the system has a solution. \(\square\)

The construction proves existence without requiring that the solution be unique. A nonpivot variable can be assigned zero for convenience; other assignments might also work. The existence question asks only whether at least one solution can be produced.

The Existence Criterion

Proof. Row operations preserve the solution set, so it is enough to compare the original system with the system represented by its echelon form. If that form contains a contradictory row, the first proposition shows that the system has no solution. Therefore, consistency implies that the echelon form contains no contradictory row. Conversely, if the echelon form has no contradictory row, the second proposition constructs a solution, which is also a solution of the original system because the row operations preserved the solution set. Hence the system is consistent exactly when its echelon form contains no contradictory row. \(\square\)

The same criterion applies no matter which sequence of valid row operations produces the echelon form. If one such form has no contradictory row, the system is consistent and therefore no row-equivalent form can contain a contradictory row. If one form has a contradictory row, the system is inconsistent and no row-equivalent form can be free of them.

Common Mistake: Ignoring the Augmented Entry

A common error is to label every row with zero coefficients as contradictory. For example, the row \([0\;\;0\mid 0]\) does not say that the system is impossible; it says \(0=0\). Treating the first two rows of the preceding example as inconsistent just because the final row has zero coefficients would incorrectly reject a system that has the verified solution \((2,1)\).

The correction is to inspect the entire row: all coefficient entries must be zero and the augmented entry must be nonzero for a contradiction. A second error is to look only for a visibly impossible equation before row reduction. Row combinations can reveal a conflict that is hidden among the original equations, as \(0=1\) was in the first example. Reduce the augmented matrix, preserving the augmented column at every step, and apply the criterion to the resulting rows.

The criterion separates two questions that are easy to blur together. First ask whether a solution exists: inspect for a contradictory row. If none occurs, back substitution constructs at least one solution. How many solutions there are is a separate issue; the existence test alone does not decide that question.