Extracting Dependence Relations from Row Reduction

From a Homogeneous Solution to a Column Relation

Row reduction can show that a list of columns is dependent, but the computation is more useful when it also gives an explicit dependence relation. The key is to keep track of the coefficients: a solution \(\mathbf{x}\) of \(\mathbf{A}\mathbf{x}=\mathbf{0}\) uses those coefficients on the original columns of \(\mathbf{A}\), even after row operations have changed the entries of the matrix.

Throughout this tutorial, matrices and vectors have real entries. Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\) have columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\), and write \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\). By the definition of matrix multiplication, \(\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\). Thus a solution \(\mathbf{x}\ne\mathbf{0}\) of the homogeneous system \(\mathbf{A}\mathbf{x}=\mathbf{0}\) gives a dependence relation among the columns. The challenge is to find and interpret such a solution accurately.

To find such a coefficient vector, row-reduce \(\mathbf{A}\) to reduced row echelon form (RREF). The row operations used in this process preserve the solutions of a homogeneous system: swapping two equations, multiplying an equation by a nonzero scalar, or adding a multiple of one equation to another does not change which \(\mathbf{x}\) satisfies all the equations. Consequently, if \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\), then \(\mathbf{A}\mathbf{x}=\mathbf{0}\) and \(\mathbf{R}\mathbf{x}=\mathbf{0}\) have exactly the same solutions.

Proof. Set the free variable \(x_k=1\), and set every other free variable to \(0\). In RREF, pivot column \(j_i\) has a \(1\) in pivot row \(i\) and \(0\) in the other pivot rows. The equation in pivot row \(i\) is therefore \(x_{j_i}+r_{ik}x_k=0\), so \(x_{j_i}=-r_{ik}\). All zero rows give no additional conditions. This constructs a solution of \(\mathbf{R}\mathbf{x}=\mathbf{0}\), and hence of \(\mathbf{A}\mathbf{x}=\mathbf{0}\), since the row operations preserve solutions. The resulting column equation is \(\mathbf{a}_k-\sum_{i=1}^{q}r_{ik}\mathbf{a}_{j_i}=\mathbf{0}\), as claimed. If there are no pivot columns, the sum is empty and the same argument gives \(\mathbf{a}_k=\mathbf{0}\). \(\square\)

The minus signs in this result come directly from solving the pivot equations: the pivot-variable coefficient is \(-r_{ik}\), not \(r_{ik}\). Equivalently, the free column is the sum of the pivot columns weighted by the entries in its column of the RREF. The relation itself has coefficient \(1\) on the selected free column and coefficients \(-r_{ik}\) on the pivot columns.

One Free Variable, One Explicit Relation

For a single free variable, choosing its value to be \(1\) gives a convenient relation. Choosing another nonzero value would produce a scalar multiple of the same relation. When there are several free variables, each one can be used to produce a relation, and choosing several free variables at once combines those relations.

Several Free Variables and All Relations

Proof. The systems \(\mathbf{A}\mathbf{x}=\mathbf{0}\) and \(\mathbf{R}\mathbf{x}=\mathbf{0}\) have the same solutions because each row operation is reversible and preserves the solution set. In pivot row \(i\), the RREF equation is \(x_{j_i}+\sum_{k\in K}r_{ik}x_k=0\); solving this equation gives the stated value of \(x_{j_i}\). There is no pivot equation that fixes a free variable, so the values \(x_k\), \(k\in K\), can be chosen arbitrarily. Conversely, for any such choices, assigning the pivot variables by the displayed equations satisfies every pivot row, and the zero rows are satisfied as well. The resulting vector is therefore a solution of both homogeneous systems. It gives a dependence relation exactly when at least one chosen free-variable value is nonzero, because if all free variables are zero, then every pivot variable is also zero. \(\square\)

In column language, an arbitrary solution gives the relation \(\sum_{k\in K}x_k\mathbf{a}_k-\sum_{i=1}^{q}\left(\sum_{k\in K}r_{ik}x_k\right)\mathbf{a}_{j_i}=\mathbf{0}\). This formula makes the signs explicit: each pivot-column coefficient is the negative of the corresponding sum of RREF entries times free-variable values.

The theorem also explains how to obtain every relation, not just these two examples. If \(x_3=s\) and \(x_4=t\), then \(x_1=-s-2t\) and \(x_2=-s+t\). Thus the relation is \(s(\mathbf{a}_3-\mathbf{a}_1-\mathbf{a}_2)+t(\mathbf{a}_4-2\mathbf{a}_1+\mathbf{a}_2)=\mathbf{0}\). It is nontrivial whenever \(s\) and \(t\) are not both zero. This parametrization is useful when a problem asks for one relation or asks to describe the full set of relations.

A Free-Variable Choice Need Not Be One

Common Sign and Interpretation Pitfalls

Common mistake: copying the RREF entries as pivot coefficients. In the first worked example, the free-column entries are \(1\) and \(2\). A wrong sign choice would claim \(\mathbf{a}_3+\mathbf{a}_1+2\mathbf{a}_2=\mathbf{0}\). But direct substitution gives \((5,4)^{\top}+(1,2)^{\top}+2(2,1)^{\top}=(10,8)^{\top}\), not the zero vector. The pivot equations instead give \(x_1=-1\) and \(x_2=-2\) when \(x_3=1\). The correct relation is \(\mathbf{a}_3-\mathbf{a}_1-2\mathbf{a}_2=\mathbf{0}\), which checks to \((0,0)^{\top}\).

Do not treat the RREF columns as the original columns. Row reduction changes the columns themselves. What it preserves is the set of coefficient vectors solving the homogeneous system. To check a relation, use its coefficients with the original columns, or multiply the original matrix by the coefficient vector. For example, the relation from the second worked example was verified using the original vectors in \(\mathbb{R}^3\), not by interpreting the RREF columns as those vectors.

Do not call a zero solution a dependence relation. Assigning zero to every free variable forces every pivot variable to be zero, so it produces only the trivial coefficient vector. To establish dependence, choose at least one free variable to be nonzero. Conversely, if the RREF has no free columns, then every variable is a pivot variable and the pivot equations force all variables to be zero; there is no nontrivial solution and hence no dependence relation.

A reliable procedure is to identify the free columns, choose their values, solve the pivot equations with their signs intact, and then check \(\mathbf{A}\mathbf{x}=\mathbf{0}\) using the original matrix. The row-reduced system organizes the coefficient calculation; the final multiplication confirms that the coefficients really give a relation among the columns under consideration.