From a Free Variable to a Dependence Relation
Row reduction can show that a list of columns is dependent, but it can also give the actual coefficients in a dependence relation. The key is to keep track of the variables in the homogeneous system: a free variable can be assigned a value, and the pivot equations then determine the remaining coefficients. Those coefficients form a vector \(\mathbf{x}\) satisfying \(\mathbf{A}\mathbf{x}=\mathbf{0}\), which is exactly the equation needed for a dependence relation.
Let \(\mathbf{v}_1,\dots,\mathbf{v}_p\) be columns in \(\mathbb{R}^m\), and place them in \(\mathbf{A}=\begin{bmatrix}\mathbf{v}_1&\cdots&\mathbf{v}_p\end{bmatrix}\). A coefficient vector is a column \(\mathbf{x}=(x_1,\dots,x_p)^{\top}\). By matrix multiplication, \(\mathbf{A}\mathbf{x}=x_1\mathbf{v}_1+\cdots+x_p\mathbf{v}_p\). The list is linearly dependent if some choice of coefficients, not all zero, makes this combination equal to \(\mathbf{0}\).
The equivalence follows directly from the definition of matrix multiplication. If \(\mathbf{A}\mathbf{x}=\mathbf{0}\), expanding the product gives the dependence equation; if the dependence equation holds, collecting its coefficients into \(\mathbf{x}\) gives \(\mathbf{A}\mathbf{x}=\mathbf{0}\). Thus the task is to find a nonzero solution, not merely to announce that one exists.
How Free Variables Produce Solutions
Reduce \(\mathbf{A}\) to reduced row echelon form (RREF). Row operations preserve the solutions of a homogeneous system: swapping equations, scaling an equation by a nonzero number, or adding a multiple of one equation to another does not change which \(\mathbf{x}\) satisfy all the equations. In the RREF, a variable in a pivot column is a pivot variable; a variable in a column without a pivot is a free variable.
Proof. Write \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\). In each nonzero row of \(\mathbf{R}\), the entry in its pivot column is \(1\), and every other pivot-column entry in that row is \(0\). Therefore, if row \(i\) has pivot in column \(k\), its equation has the form \(x_k+\sum_{j\text{ free}}r_{ij}x_j=0\). Once values are assigned to all free variables, this equation determines \(x_k\) uniquely as \(-\sum_{j\text{ free}}r_{ij}x_j\). Each pivot variable belongs to one pivot row, so all pivot variables are determined, and zero rows impose no further condition. This proves existence and uniqueness for every free-variable assignment. The solution also solves the original system because row operations preserve its solutions. If there are no free variables, every variable is a pivot variable and each pivot equation gives \(x_k=0\), so the only solution is \(\mathbf{0}\). If a free variable exists, set one free variable to \(1\) and all other free variables to \(0\); solve for the pivot variables as above. The resulting solution is nonzero because its chosen free coordinate is \(1\). Hence a nonzero solution exists exactly when at least one free variable exists. \(\square\)
To obtain a dependence relation, choose at least one free-variable value to be nonzero, solve the pivot equations, and read the resulting entries of \(\mathbf{x}\) as coefficients on the original columns. An assignment in which all free variables are zero gives the zero solution, so it does not provide a dependence relation. The checks below multiply the coefficient vector by the original matrix, or equivalently evaluate the combination of the original columns.
Worked Examples
Worked Example: One Free Variable
Find a dependence relation among the columns of \(\mathbf{A}=\begin{bmatrix}1&2&0\\2&4&1\\1&2&1\end{bmatrix}\).
Write \(\mathbf{A}\mathbf{x}=\mathbf{0}\) with \(\mathbf{x}=(x_1,x_2,x_3)^{\top}\), and row-reduce. First use \(R_2\to R_2-2R_1\) and \(R_3\to R_3-R_1\):
Next use \(R_3\to R_3-R_2\):
The nonzero rows give \(x_1+2x_2=0\) and \(x_3=0\). Columns 1 and 3 are pivot columns, so \(x_2\) is free. Choose \(x_2=1\). Then \(x_1=-2\) and \(x_3=0\), giving \(\mathbf{x}=(-2,1,0)^{\top}\).
Check: The original columns are \(\mathbf{v}_1=(1,2,1)^{\top}\), \(\mathbf{v}_2=(2,4,2)^{\top}\), and \(\mathbf{v}_3=(0,1,1)^{\top}\). Substitution gives \(-2\mathbf{v}_1+\mathbf{v}_2+0\mathbf{v}_3=(-2+2,-4+4,-2+2)^{\top}=\mathbf{0}\). The nonzero coefficients therefore give a valid dependence relation.
Worked Example: Two Free Variables
Find two dependence relations among the columns of \(\mathbf{A}=\begin{bmatrix}1&0&1&2\\0&1&1&1\end{bmatrix}\).
This matrix is already in RREF. The pivot variables are \(x_1,x_2\), and the free variables are \(x_3,x_4\). The system reads \(x_1+x_3+2x_4=0\) and \(x_2+x_3+x_4=0\). Assign \(x_3=s\) and \(x_4=t\). Solving both equations gives \(x_1=-s-2t\) and \(x_2=-s-t\), so all solutions have the form
Choose \(s=1\) and \(t=-1\). Then \(\mathbf{x}=(1,0,1,-1)^{\top}\). The columns are \(\mathbf{v}_1=(1,0)^{\top}\), \(\mathbf{v}_2=(0,1)^{\top}\), \(\mathbf{v}_3=(1,1)^{\top}\), and \(\mathbf{v}_4=(2,1)^{\top}\). Thus the proposed relation is \(\mathbf{v}_1+\mathbf{v}_3-\mathbf{v}_4=\mathbf{0}\).
Check: \((1,0)^{\top}+(1,1)^{\top}-(2,1)^{\top}=(1+1-2,0+1-1)^{\top}=(0,0)^{\top}\). A different nonzero assignment, \(s=0,t=1\), gives \(\mathbf{x}=(-2,-1,0,1)^{\top}\). It also checks: \(-2(1,0)^{\top}-(0,1)^{\top}+(2,1)^{\top}=(0,0)^{\top}\). Different free-variable choices can therefore give different valid relations.
Worked Example: Pivot Variables Can Be Negative
Find a dependence relation among the columns of \(\mathbf{A}=\begin{bmatrix}1&2&3\\2&5&8\\1&3&5\end{bmatrix}\).
Apply \(R_2\to R_2-2R_1\) and \(R_3\to R_3-R_1\):
Now use \(R_3\to R_3-R_2\), followed by \(R_1\to R_1-2R_2\):
The equations are \(x_1-x_3=0\) and \(x_2+2x_3=0\). Set the free variable \(x_3=1\). Then \(x_1=1\) and \(x_2=-2\), so \(\mathbf{x}=(1,-2,1)^{\top}\). The negative value is simply a coefficient in the relation; it does not need to be positive.
Check: The original columns are \((1,2,1)^{\top}\), \((2,5,3)^{\top}\), and \((3,8,5)^{\top}\). Their combination is \((1,2,1)^{\top}-2(2,5,3)^{\top}+(3,8,5)^{\top}=(1-4+3,2-10+8,1-6+5)^{\top}=(0,0,0)^{\top}\). Thus the relation is verified in the original coordinates.
Why the Construction Works
Proof. Suppose \(\mathbf{x}\ne\mathbf{0}\) and \(\mathbf{A}\mathbf{x}=\mathbf{0}\). Expanding the matrix product by its columns gives \(x_1\mathbf{v}_1+\cdots+x_p\mathbf{v}_p=\mathbf{0}\). Since \(\mathbf{x}\ne\mathbf{0}\), at least one \(x_j\ne0\), so this is a dependence relation. Conversely, suppose \(x_1\mathbf{v}_1+\cdots+x_p\mathbf{v}_p=\mathbf{0}\) is a dependence relation. Its coefficients are not all zero, so the coefficient vector \(\mathbf{x}\) is nonzero. The same expansion of matrix multiplication gives \(\mathbf{A}\mathbf{x}=\mathbf{0}\). This proves both directions. \(\square\)
Together, the theorem and proposition explain the complete procedure: a free variable provides a way to construct a nonzero solution, and that solution supplies the coefficients. A correct calculation should finish with a substitution into the original columns. The reduced matrix is used to solve for the coefficients; the original matrix is used to check the resulting relation.
Common Pitfall: Choosing Pivot Variables Arbitrarily
A free variable may be assigned, but a pivot variable must satisfy its equation. In the third example, choosing \(x_3=1\) and then setting \(x_1=0,x_2=0\) would give the incorrect coefficient vector \((0,0,1)^{\top}\). The RREF equations show why this fails: \(x_1-x_3=0\) becomes \(0-1\ne0\), and \(x_2+2x_3=0\) becomes \(0+2\ne0\). Indeed, \(\mathbf{A}(0,0,1)^{\top}=(3,8,5)^{\top}\ne\mathbf{0}\).
The correction is to use the chosen value \(x_3=1\) in both pivot equations: \(x_1=1\) and \(x_2=-2\). Then test the resulting vector against the original matrix. Assigning free variables is not permission to choose every coordinate independently; the pivot equations constrain the other coordinates.
A Reliable Calculation Routine
Form \(\mathbf{A}\) with the given vectors as columns and row-reduce the homogeneous system \(\mathbf{A}\mathbf{x}=\mathbf{0}\) to RREF.
Mark variables in columns without pivots. If there are none, this system has no nonzero solution and this method produces no dependence relation.
Set at least one free variable to a nonzero value. For multiple free variables, choose values for each of them.
Substitute the free-variable values into the RREF equations and compute every pivot variable.
Use the coordinates of \(\mathbf{x}\) as coefficients on the original columns and check that their combination is \(\mathbf{0}\).
It is useful to keep the coefficient vector visible throughout the calculation. Its \(j\)-th entry always multiplies the \(j\)-th original column, even if row reduction has changed the appearance of the matrix. The check against the original columns catches sign errors, misplaced coefficients, and incorrect pivot-variable values.
Check Your Understanding
For each proposed relation, use the homogeneous system and then verify with the original columns.
- If the RREF equations are \(x_1+3x_3=0\) and \(x_2-x_3=0\), choose \(x_3=1\). What coefficient vector results?
- For the system \(x_1-2x_3+x_4=0\), \(x_2+x_3+3x_4=0\), identify the free variables and give a nonzero solution by choosing their values.
- Explain why assigning zero to every free variable cannot produce a dependence relation.
- Suppose a proposed coefficient vector is \((2,-1,1)^{\top}\). State the matrix equation that must be checked to confirm it gives a dependence relation for three columns.
- For \(\mathbf{A}=\begin{bmatrix}1&1\\2&2\end{bmatrix}\), find a nonzero solution of \(\mathbf{A}\mathbf{x}=\mathbf{0}\) and check it using the original columns.
