Row Reduction Tests for Independence

From a List of Vectors to a Homogeneous System

A list may contain vectors that contribute no new information: one vector might be obtainable as a linear combination of the others. Row reduction gives a systematic way to detect this redundancy. The central point is to put the vectors in the columns of a matrix. The unknowns in the resulting homogeneous system are the coefficients of a possible dependence relation.

Work over \(\mathbb{R}\), and let \(\mathbf{v}_1,\dots,\mathbf{v}_p\) be a finite ordered list of vectors in \(\mathbb{R}^n\), with \(p\geq 1\). The order matters because the coefficient \(c_j\) is attached to the \(j\)th vector. A linear combination is an expression \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p\), where each \(c_j\in\mathbb{R}\).

Form the matrix \(\mathbf{A}\in\mathbb{R}^{n\times p}\) by using the vectors as its columns, and let \(\mathbf{c}=(c_1,\dots,c_p)^{\top}\). By the definition of matrix multiplication, \(\mathbf{A}\mathbf{c}\) is the linear combination whose coefficients are the entries of \(\mathbf{c}\).

Proof. For any coefficient vector \(\mathbf{c}=(c_1,\dots,c_p)^{\top}\), matrix multiplication gives \(\mathbf{A}\mathbf{c}=c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p\). Therefore \(\mathbf{A}\mathbf{c}=\mathbf{0}\) holds exactly when the coefficients give a linear combination equal to the zero vector. By the definition of independence, the list is independent exactly when the only such coefficient vector is \(\mathbf{0}\). This proves both directions. \(\square\)

The Pivot Test

Row operations preserve the solution set of a homogeneous system: each operation replaces its equations with equivalent equations. Reduce \(\mathbf{A}\) to reduced row echelon form (RREF). A pivot column is a column containing a leading \(1\) in the RREF; a column without a pivot is a free column. The corresponding coefficient is called a free variable. Variables in pivot columns are called pivot variables.

Proof. Let \(\mathbf{R}\) be the RREF of \(\mathbf{A}\). Since row operations preserve solutions, \(\mathbf{A}\mathbf{c}=\mathbf{0}\) and \(\mathbf{R}\mathbf{c}=\mathbf{0}\) have the same solutions. In the latter system, each pivot variable is determined by the free variables in its row. If every column is a pivot column, there are no free variables. Each pivot row then sets its pivot variable to zero, so \(\mathbf{c}=\mathbf{0}\) is the only solution. The first theorem implies that the list is independent.

Conversely, suppose there is a free column. Set one corresponding free variable equal to \(1\) and all other free variables equal to \(0\). The equations in the pivot rows determine the pivot variables, so this choice extends to a solution of \(\mathbf{R}\mathbf{c}=\mathbf{0}\). That solution is nonzero because one of its free variables is \(1\). It is therefore also a nonzero solution of \(\mathbf{A}\mathbf{c}=\mathbf{0}\), and the list is dependent. Thus independence holds exactly when every column has a pivot. \(\square\)

This argument gives a practical way to find a dependence relation, not just detect one. When a free variable is set to a nonzero value, solve for the pivot variables and read all the coefficients from the resulting vector \(\mathbf{c}\). Check the relation using the original columns; row operations help solve for the coefficients, but do not change which original vectors the coefficients multiply.

Worked Examples

Reading the Result Correctly

The pivot test concerns the columns of the matrix, in the order the vectors were given. A pivot in column \(j\) means that the coefficient \(c_j\) is a pivot variable in the homogeneous system; a column without a pivot gives a free coefficient. The locations of the free columns indicate where to start when constructing a relation. The values of the other coefficients must still be obtained from the reduced equations.

One free variable set to \(1\), with the other free variables set to \(0\), gives one nonzero solution. If there are several free variables, other choices can give additional relations. A dependence relation need not use every vector: some of its coefficients may be zero. Conversely, a list may be independent even if one or more of its vectors have zero entries; the test concerns the whole columns, not whether individual entries vanish.

When the list has just one vector, the same test applies. A nonzero column has a pivot and is independent. A zero column has no pivot; its coefficient is free, and setting it to \(1\) gives a nontrivial relation. Thus the method includes this basic case without a separate rule.

Common Pitfall: Reducing the Vectors as Rows

Consider the three vectors \((1,0)^{\top}\), \((0,1)^{\top}\), and \((1,1)^{\top}\) in \(\mathbb{R}^2\). A wrong approach is to put them in rows, row reduce that matrix, and then conclude that the original list is independent because both columns of the transposed matrix have pivots. The calculation is

That matrix has two pivot columns, but its rows represent three vectors; the pivot test for the original list does not ask whether every column of this transposed matrix has a pivot. It asks whether every column of the matrix formed from the vectors as columns has a pivot. That matrix is

with a free third column. The reduced equations give \(c_1=-c_3\), \(c_2=-c_3\); choosing \(c_3=1\) yields \((-1,-1,1)^{\top}\). Checking the original vectors, \(-(1,0)^{\top}-(0,1)^{\top}+(1,1)^{\top}=(0,0)^{\top}\), so the list is dependent. The correction is simple: always place the given vectors in columns before applying the pivot test.