Testing Independence by Row Reduction

From a List of Vectors to a Test

To decide whether a list of vectors is linearly independent, we ask whether any nonzero choice of coefficients combines them to give the zero vector. Row reduction turns that question into a system of equations that can be solved in a systematic way. The essential point is to keep track of the coefficients of the original vectors: they are the unknowns in the homogeneous system.

Throughout, the vectors and scalars are in \(\mathbb{R}^n\) and \(\mathbb{R}\), respectively. A linear combination of an ordered list \(\mathbf{v}_1,\dots,\mathbf{v}_p\) is \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p\), where each \(c_i\in\mathbb{R}\). The list is linearly independent when the only way this combination equals \(\mathbf{0}\) is to choose every coefficient equal to zero. Otherwise it is linearly dependent.

Make the matrix \(\mathbf{A}\) whose columns are the listed vectors, in their given order. If \(\mathbf{c}=(c_1,\dots,c_p)^\top\), the definition of matrix multiplication gives \(\mathbf{A}\mathbf{c}=c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p\). Thus the independence question is whether the homogeneous system \(\mathbf{A}\mathbf{c}=\mathbf{0}\) has only the solution \(\mathbf{c}=\mathbf{0}\).

This test builds on the connection between homogeneous systems and independence. Row reduction is useful because it gives an equivalent system whose equations are easier to solve. We do not row-reduce the vectors one at a time as separate objects: we row-reduce the matrix with those vectors as its columns, and the variables in the homogeneous system record their coefficients.

Why Row Reduction Gives the Same Answer

Each elementary row operation preserves the solution set of a homogeneous system. A row swap merely changes the order of two equations. Multiplying a row by a nonzero scalar replaces an equation by an equivalent equation. Adding a multiple of one row to another replaces an equation by a combination that can be reversed by subtracting that same multiple. In every case, the operation has an inverse of the same type, so the original and transformed systems have exactly the same solutions.

Proof. For one row swap, a vector \(\mathbf{c}\) satisfies the original system if and only if it satisfies the same equations in the swapped order. For a row scaling by a nonzero number \(a\), the new equation is \(a\) times the old equation; it equals zero if and only if the old equation equals zero, because \(a\ne0\). For the operation that adds \(a\) times row \(j\) to row \(i\), every solution of the original system satisfies the new row equation. Conversely, from the new row and the unchanged row \(j\), subtracting \(a\) times row \(j\) recovers the original row \(i\). Thus the solution sets agree for each elementary operation, and therefore agree after any finite sequence of them. \(\square\)

Consequently, it is valid to row-reduce \(\mathbf{A}\) and solve the homogeneous system given by the resulting matrix. The answer concerns the coefficient vector \(\mathbf{c}\), not whether the transformed matrix has the same columns as the original matrix.

Proof. Write the columns of \(\mathbf{A}\) as \(\mathbf{v}_1,\dots,\mathbf{v}_p\). By the definition of matrix multiplication, \(\mathbf{A}\mathbf{c}=\mathbf{0}\) means \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p=\mathbf{0}\). By the definition of linear independence, this equation has only the solution with every \(c_i=0\) exactly when the column list is independent. If some solution has a nonzero coefficient, it is a nontrivial linear combination equal to \(\mathbf{0}\), so the columns are dependent. \(\square\)

Worked Examples

A Reliable Procedure and a Common Mistake

The same steps apply whether the matrix is square or rectangular. There are \(p\) coefficient variables when the list has \(p\) vectors, regardless of the number \(n\) of coordinates in each vector. The row-reduced equations determine which coefficient choices work. A single nonzero solution proves dependence; to prove independence, the reduced equations must force every coefficient to be zero.

Common mistake: treating a zero right-hand side as proof that all variables are zero. For example, in the third worked example the reduced equations are \(c_1+2c_2=0\) and \(c_3=0\). It would be wrong to conclude that the system has only the zero solution merely because its right-hand side is zero. Taking \(c_2=1\) gives \(c_1=-2\) and \(c_3=0\), which is a nonzero solution. The correction is to solve the homogeneous system, allowing free choices of variables, and check whether any such choice produces a nonzero coefficient vector.

Another safeguard is to distinguish the matrix used to test independence from the original list. Row operations preserve the solutions for the coefficients, which is why the test works; they do not in general leave the matrix’s columns unchanged. The conclusion about the original vectors comes from the solutions to \(\mathbf{A}\mathbf{c}=\mathbf{0}\), not from treating the reduced matrix as a new list of vectors.