What the Solution Set Records
A homogeneous system records more than whether a nonzero solution exists. Its full solution set also tells us which coordinates may be chosen freely and how the remaining coordinates depend on them. If the coefficient matrix is in reduced row echelon form, those coordinate relationships encode its pivot columns and its nonzero rows.
Let \(\mathbf{R}\in\mathbb{R}^{m\times n}\) be in reduced row echelon form (RREF). In this tutorial, the leading \(1\) of a nonzero row is a pivot, and its column is a pivot column. In reduced row echelon form, a pivot is the only nonzero entry in its column, but not every column with a single nonzero entry is a pivot column. Columns without pivots are free columns. The nonzero rows of an RREF matrix have leading \(1\)s, with their pivot positions moving strictly to the right as we move down the rows; any zero rows are at the bottom. The solution set of the homogeneous system is \(S=\{\mathbf{x}\in\mathbb{R}^n:\mathbf{R}\mathbf{x}=\mathbf{0}\}\).
For example, if \(\varphi_1=-2\varphi_2+3\varphi_4\), then every solution satisfies \(x_1=-2x_2+3x_4\). The key distinction is between a coordinate that can be assigned freely and one whose value is forced by the others. Scanning coordinates from right to left makes this distinction visible in an RREF system.
Why Free Coordinates Vary Independently
Proof. In each nonzero row, the pivot column has a \(1\) and all its other entries are \(0\). Thus the equation in that row expresses its pivot variable as the negative of a sum of free variables multiplied by the entries in that row. Assigning all free variables therefore determines each pivot variable. Every pivot column belongs to exactly one such row, so this determines all pivot variables and gives a solution. Conversely, every solution must satisfy those row equations, so its pivot variables must have exactly those determined values. Zero rows impose no conditions. Hence the extension exists and is unique. \(\square\)
This lemma explains why the restrictions belonging to free columns can be distinguished: any one free variable can be set to \(1\) while all the other free variables are set to \(0\). A pivot coordinate behaves differently: its value is already prescribed by the row equation, using free coordinates to its right.
Proof. Consider the scan from right to left. We show, as each column is reached, that free columns are retained and pivot columns are not. A pivot column \(p\) has an equation \(x_p+\sum_{j>p}r_{ij}x_j=0\) from its pivot row \(i\); entries before the pivot are zero, and any other pivot-column entries in that row are zero. Consequently \(\varphi_p=-\sum_{j>p,\ j\text{ free}}r_{ij}\varphi_j\). Every free column to the right has already been scanned and retained, by the right-to-left order and the claim for free columns. Thus \(\varphi_p\) is a combination of restrictions already retained, so it is not retained. For a free column \(f\), set its variable to \(1\) and all other free variables to \(0\). The lemma supplies a solution with these values. Every previously retained restriction belongs to a free column to the right, so each has value \(0\) on this solution, whereas \(\varphi_f\) has value \(1\). No combination of the previously retained restrictions can equal \(\varphi_f\), so \(\varphi_f\) is retained. This proves the scan identifies exactly the free columns. For a pivot \(p\), its row equation expresses \(\varphi_p\) as a combination of the retained free-coordinate restrictions. Those coefficients are unique: if two coefficient lists gave the same function, set one free variable at a time to \(1\) and all other free variables to \(0\); evaluation on each such solution forces the two coefficients for that variable to agree. Finally, the row has coefficient \(1\) in column \(p\), zero in every other pivot column, and the negatives of the recovered coefficients in the free columns. This recovers its nonzero row. Zero rows impose no equation on \(S\), so their number cannot be read from \(S\). \(\square\)
Recovering Pivot Equations in Practice
Worked Example: Two Pivot Equations from a Parametrized Solution Set
Suppose the homogeneous solution set in \(\mathbb{R}^4\) is given by \(\mathbf{x}=(-2s+3t,\ s,\ 4t,\ t)^{\top}\), where \(s,t\in\mathbb{R}\). Identify the free columns and reconstruct the nonzero RREF rows.
Read off the coordinate restrictions on this set:
Scan from the right. The restriction \(\varphi_4=t\) is retained. Since \(\varphi_3=4\varphi_4\), column \(3\) is not retained. The restriction \(\varphi_2=s\) cannot be written using only \(\varphi_4\), so column \(2\) is retained. Finally, \(\varphi_1=-2\varphi_2+3\varphi_4\), so column \(1\) is not retained. The free columns are \(2\) and \(4\), and the pivot columns are \(1\) and \(3\).
The coordinate identities give the pivot equations \(x_1+2x_2-3x_4=0\) and \(x_3-4x_4=0\). Thus the nonzero rows, in pivot order, are:
Check: Substitute \(\mathbf{x}=(-2s+3t,s,4t,t)^{\top}\). The first row gives \((-2s+3t)+2s-3t=0\), and the second gives \(4t-4t=0\). Conversely, the two equations give \(x_1=-2x_2+3x_4\) and \(x_3=4x_4\). Setting \(x_2=s\) and \(x_4=t\) recovers exactly the stated solution set.
Worked Example: A Free Column Before a Pivot Column
Let \(S=\{(s,-2t,t)^{\top}:s,t\in\mathbb{R}\}\). Identify the pivot and free columns and recover the nonzero RREF row.
The restrictions are \(\varphi_1=s\), \(\varphi_2=-2t\), and \(\varphi_3=t\). Scanning from the right, retain \(\varphi_3=t\). Since \(\varphi_2=-2\varphi_3\), column \(2\) is a pivot column. Column \(1\) is free: its restriction \(\varphi_1=s\) cannot be expressed using \(\varphi_3=t\), since \(s\) and \(t\) can be chosen independently.
The coordinate relation \(x_2=-2x_3\) gives the equation \(x_2+2x_3=0\). Its RREF row is \(\begin{bmatrix}0&1&2\end{bmatrix}\), with pivot in column \(2\).
Check: Multiplying the row by a vector in \(S\) gives \(0\cdot s+(-2t)+2t=0\). Conversely, \(x_2+2x_3=0\) allows \(x_1=s\) and \(x_3=t\) to be chosen freely, forcing \(x_2=-2t\); this gives precisely \(S\).
What the Zero Vector Solution Set Can—and Cannot—Tell You
Worked Example: The Same Solution Set with Different Numbers of Rows
Consider the solution set \(S=\{\mathbf{0}\}\) in \(\mathbb{R}^2\). Every coordinate restriction is the zero function on \(S\), so the right-to-left scan retains no columns. Both columns must be pivot columns. If the matrix has exactly two rows, the RREF matrix is
Indeed, its equations are \(x_1=0\) and \(x_2=0\). If the matrix has three rows, an RREF matrix with the same solution set is
The extra row adds no condition. Both matrices have the same homogeneous solutions, so the solution set alone does not specify the number of rows. More generally, once the nonzero rows have been recovered, append as many zero rows as needed to match a specified total row count.
Check: For either displayed matrix, the equation \(\mathbf{R}\mathbf{x}=\mathbf{0}\) forces \(x_1=0\) and \(x_2=0\); the additional zero row in the second matrix evaluates to \(0=0\). Thus both solution sets are exactly \(\{\mathbf{0}\}\).
Common Pitfalls
Scanning in the wrong direction can select the wrong columns. In the first worked example, a left-to-right scan would retain \(\varphi_1=-2s+3t\), then \(\varphi_2=s\), then \(\varphi_3=4t\). It would fail to retain \(\varphi_4=t\), because \(\varphi_4=\tfrac14\varphi_3\). That procedure labels columns \(1,2,3\) as free, even though the recovered equations show that columns \(1\) and \(3\) are pivot columns. The specified right-to-left scan avoids this: when a pivot coordinate is reached, its equation involves only free coordinates to its right, which have already been identified.
Do not infer the number of rows from the solution set. The two matrices in the preceding example have the same solution set but different row counts. The scan recovers the pivot equations—the nonzero rows—not optional zero rows. If the matrix size is known, add the required number of zero rows; if it is not known, state that the row count is undetermined by the solution set.
How the Reconstruction Helps
The solution set can be treated as coordinate data. A coordinate restriction that can be expressed using already retained restrictions is forced by the others; a restriction that cannot be so expressed supplies a new free coordinate. Once the free columns are identified, each pivot coordinate is a specific combination of them, and changing the signs in that identity gives the corresponding RREF row.
This reasoning is useful when a homogeneous solution set is given parametrically but the equations that produced it are not. It also provides a check on a proposed RREF: its free variables must vary independently, and its pivot equations must agree with the coordinate relations on every solution. The method reconstructs the nonzero equations without needing to know how the original coefficient matrix was obtained.
Check Your Understanding
For each question, use coordinate restrictions on the full solution set, not just one sample solution.
- For \(S=\{(a-3b,\ 2b,\ a,\ b)^{\top}:a,b\in\mathbb{R}\}\), scan from right to left and identify the free columns.
- For the set in question 1, recover the pivot equations and write the nonzero RREF rows.
- Explain why the coordinate restrictions for free columns cannot be combinations of only the free-coordinate restrictions to their right.
- Give two RREF matrices with different row counts whose homogeneous solution set is \(\{\mathbf{0}\}\) in \(\mathbb{R}^3\).
- Why does the solution set determine the nonzero pivot equations but not the number of trailing zero rows?
