The Question for a Homogeneous System
A homogeneous linear system always has at least one solution: setting every variable to zero satisfies every equation. The important question is whether there are any other solutions. Row reduction makes this question precise. If an echelon form has a column without a pivot, the variable in that column is free, and a suitable choice of its value produces a nonzero solution. If every column has a pivot, back substitution forces every variable to be zero.
We work over \(\mathbb{R}\). Let \(m,n\in\mathbb{N}\), let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and write \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\). A homogeneous system with coefficient matrix \(\mathbf{A}\) is the matrix equation \(\mathbf{A}\mathbf{x}=\mathbf{0}\). Its zero solution is \(\mathbf{x}=\mathbf{0}\), and a nonzero solution is any solution \(\mathbf{x}\ne\mathbf{0}\).
In echelon form, the pivots move strictly to the right as we move down through nonzero rows, and any zero rows are at the bottom. These properties let us solve for pivot variables from the bottom upward. A free variable can be assigned a value, but the pivot variables must then be found from the equations; simply choosing a nonzero value for a free variable is not yet a complete solution.
Why Row Reduction Keeps the Solutions
We may row-reduce the coefficient matrix because each elementary row operation preserves the solutions of a homogeneous system. The operation can change the displayed equations, but it does not change which vectors \(\mathbf{x}\) satisfy them.
Proof. Fix any vector \(\mathbf{x}\). Swapping two equations only changes their order, so it preserves whether all equations are satisfied. Multiplying an equation by a nonzero scalar preserves whether its left-hand side is zero, because \(c y=0\) if and only if \(y=0\) when \(c\ne0\). Replacing one equation by itself plus a scalar multiple of another also preserves the system's solutions: any solution of the original equations satisfies the replacement equation, and the original equation can be recovered by subtracting that same multiple of the other equation. Thus each operation preserves the solution set in both directions, and so does any finite sequence of them. \(\square\)
In particular, if \(\mathbf{E}\) is an echelon form of \(\mathbf{A}\), we may decide whether the original system has a nonzero solution by solving \(\mathbf{E}\mathbf{x}=\mathbf{0}\). The row operations do not need to produce a reduced row-echelon form for this test; echelon form is enough.
The Free-Variable Criterion
Proof. By the lemma, \(\mathbf{A}\mathbf{x}=\mathbf{0}\) and \(\mathbf{E}\mathbf{x}=\mathbf{0}\) have the same solutions. We prove both directions for the echelon system.
First suppose \(\mathbf{E}\) has a free-variable column. Assign the value \(1\) to one free variable and \(0\) to every other free variable. Starting with the last nonzero row and working upward, solve each pivot equation for its pivot variable. This is possible at each step because the pivot coefficient is nonzero and every other variable in that row is either free or a pivot variable already determined lower down. The resulting vector satisfies all nonzero rows; zero rows impose no additional equation. It is nonzero because its chosen free variable is \(1\). Hence the system has a nonzero solution.
Conversely, suppose \(\mathbf{E}\) has no free-variable column. Then every variable is a pivot variable. In the last nonzero row, all entries to the right of the pivot are zero: there are no later pivot columns, and there are no free columns. Since the system is homogeneous, that row forces its pivot variable to be zero. Moving upward, assume the pivot variables in all rows below a given row have been shown to be zero. Every variable to the right of this row's pivot is one of those later pivot variables, so the row forces its own pivot variable to be zero as well. Applying this argument through the nonzero rows shows that every variable is zero. If there are no nonzero rows, having no free-variable column would require \(n=0\), which is excluded by \(n\in\mathbb{N}\); thus that case cannot occur under this assumption. Therefore there is no nonzero solution. The two directions prove the equivalence. \(\square\)
The theorem describes a test, not just a pattern to memorize. A free variable supplies a value that cannot be forced by a pivot equation. Back substitution then determines the pivot variables so that the equations hold. Without free variables, the bottom-up equations successively force every variable to vanish.
Using the Criterion in Examples
Worked Example: One Free Variable Produces a Nonzero Solution
Consider the homogeneous system with coefficient matrix \(\mathbf{A}=\begin{bmatrix}1&2&-1\\2&4&-2\end{bmatrix}\). Reduce the matrix, then find and check a nonzero solution.
Subtracting \(2R_1\) from \(R_2\) gives an echelon form:
Column 1 is a pivot column. Columns 2 and 3 are free-variable columns, so set \(x_2=1\) and \(x_3=0\). The nonzero row gives \(x_1+2x_2-x_3=0\), hence \(x_1+2(1)-0=0\) and \(x_1=-2\). Thus \(\mathbf{x}=(-2,1,0)^{\top}\).
Check: Multiplying by the original matrix gives \(\mathbf{A}\mathbf{x}=(-2+2,\,-4+4)^{\top}=(0,0)^{\top}\). The vector is nonzero because its second entry is \(1\).
Worked Example: Every Column Is a Pivot Column
Consider \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&3\\0&0&2\end{bmatrix}\). This matrix is already in echelon form. Determine whether its homogeneous system has a nonzero solution.
There is a pivot in each of the three columns, so there are no free variables. Back substitution makes the conclusion explicit. The last equation is \(2x_3=0\), so \(x_3=0\). The second equation is \(x_2+3x_3=0\), so \(x_2=0\). The first is \(x_1+2x_2=0\), so \(x_1=0\). Therefore the only solution is \(\mathbf{x}=\mathbf{0}\).
Check: Multiplying by \(\mathbf{A}\) gives \(\mathbf{A}\mathbf{0}=\mathbf{0}\). The back-substitution equations show that no other vector can be a solution.
Worked Example: Two Free Variables and a Zero Row
Consider \(\mathbf{A}=\begin{bmatrix}1&2&1&0\\2&4&2&0\\0&0&0&1\end{bmatrix}\). Reduce it and use its free-variable columns to construct a nonzero solution.
First subtract \(2R_1\) from \(R_2\); then swap rows 2 and 3 to place the zero row at the bottom:
The pivots are in columns 1 and 4, leaving columns 2 and 3 free. Choose \(x_2=1\) and \(x_3=0\). The second nonzero row gives \(x_4=0\), and the first gives \(x_1+2(1)+0=0\), so \(x_1=-2\). Therefore \(\mathbf{x}=(-2,1,0,0)^{\top}\).
Check: The product with the original matrix is \(\mathbf{A}\mathbf{x}=(-2+2,\,-4+4,\,0)^{\top}=(0,0,0)^{\top}\). The constructed vector is nonzero, and the zero row in the echelon form adds no constraint.
Common Pitfall: A Free Choice Still Has to Satisfy the Equations
Suppose the echelon matrix is \(\begin{bmatrix}1&2\\0&0\end{bmatrix}\). Column 2 is free, so it is tempting to set \(x_2=1\) and \(x_1=0\), then claim \((0,1)^{\top}\) is a solution. That claim is wrong: multiplying gives \(\begin{bmatrix}1&2\\0&0\end{bmatrix}(0,1)^{\top}=(2,0)^{\top}\ne\mathbf{0}\). The free variable may be chosen, but the pivot variable must be calculated. With \(x_2=1\), the first equation \(x_1+2x_2=0\) requires \(x_1=-2\), and the corrected vector \((-2,1)^{\top}\) satisfies the system.
Another useful check is to distinguish the number of variables from the number of equations. The theorem counts columns, because each column corresponds to a variable. A zero row does not itself create a free variable; a column without a pivot does. A system can have zero rows and still have no free variables only if every variable column has a pivot elsewhere.
Why the Test Is Useful
For a homogeneous system, the zero vector is guaranteed to be a solution, so the pivot pattern answers the key remaining question: whether the solution set contains anything else. The test works for square and rectangular coefficient matrices, and it does not require solving for every possible solution. Reduce to echelon form, inspect the columns, and use back substitution only when a free column is present and an explicit nonzero solution is needed.
The construction in the theorem also explains why the result is an if-and-only-if statement. A free column lets us choose a nonzero coordinate and then solve for the pivot coordinates. If no column is free, every coordinate is a pivot variable and the homogeneous equations force them all to zero. In either case, checking a proposed vector by multiplying it by the original matrix is a direct way to confirm that it satisfies the original system.
Check Your Understanding
For each question, use the pivot pattern and, when appropriate, verify a proposed vector by multiplication.
- In an echelon form with pivots in columns 1 and 3 of a matrix with 4 columns, does the associated homogeneous system have a nonzero solution? Explain.
- For \(\begin{bmatrix}1&-1&2\\0&0&1\\0&0&0\end{bmatrix}\), identify the free-variable columns and find one nonzero solution.
- Why does assigning a nonzero value to a free variable not by itself guarantee that the resulting vector is a solution?
- In the theorem's proof, why does the absence of free columns imply that every variable is a pivot variable?
- Does a zero row in an echelon form count as a free-variable column? State the distinction.
