Why More Than n Vectors in R^n Are Dependent

More Unknowns Than Equations

A homogeneous system always has the zero solution. The key question is whether it must also have a nonzero solution. When a system has \(n\) equations but more than \(n\) unknowns, row reduction answers yes: there cannot be a pivot for every unknown, so at least one variable is free. Choosing a nonzero value for a free variable produces a nonzero solution.

This counting argument has a direct consequence for vectors. A dependence relation among \(\mathbf{v}_1,\dots,\mathbf{v}_p\) is an equation \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p=\mathbf{0}\) in which the coefficients are not all zero. Placing the vectors in the columns of a matrix turns that equation into a homogeneous system with \(p\) unknowns. Thus, when there are more vectors than coordinates, the free-variable argument supplies the coefficients of a dependence relation.

Pivot and Free Variables

Consider a homogeneous system \(\mathbf{A}\mathbf{x}=\mathbf{0}\), where \(\mathbf{A}\in\mathbb{R}^{n\times p}\) and \(\mathbf{x}=(x_1,\dots,x_p)^\top\). Row reduction uses row swaps, multiplication of a row by a nonzero scalar, and addition of a multiple of one row to another. Each operation replaces equations by equivalent equations: a row swap just reorders them; scaling by a nonzero scalar can be reversed by scaling back; and adding a multiple of one equation to another can be reversed by subtracting that multiple. Therefore, the original and row-reduced systems have exactly the same solutions.

In reduced row echelon form (RREF), each pivot is the leading \(1\) in a nonzero row, and each pivot is the only nonzero entry in its column. A variable in a pivot column is a pivot variable; a variable in any other column is a free variable. A matrix with \(n\) rows can have at most \(n\) pivots, because each pivot occupies a different row. It can therefore have at most \(n\) pivot columns.

Proof. Row-reduce \(\mathbf{A}\) to RREF. This process terminates: it moves through the finitely many columns from left to right, choosing a pivot in a column when a nonzero entry is available in the rows not yet used for pivots, and otherwise moving to the next column. Each pivot uses a new row, so there are at most \(n\) pivots. If the number of pivots is \(r\), then \(r\le n\), and among the \(p\) columns there are \(p-r\ge p-n>0\) nonpivot columns. Thus at least one variable is free, and there are at least \(p-n\) free variables.

The row operations preserve solutions, so it remains to find a nonzero solution of the RREF system. Assign the value \(1\) to one free variable and \(0\) to every other free variable. In each nonzero row, the pivot variable has coefficient \(1\), so set it equal to the negative of the sum of the other terms in that row. This satisfies that row. Any all-zero row represents \(0=0\), so it is satisfied as well. The resulting vector \(\mathbf{x}\) is a solution, and it is nonzero because one of its free-variable entries is \(1\). Hence the original system has a nonzero solution. \(\square\)

The theorem guarantees at least \(p-n\) free variables, but not exactly \(p-n\). If some rows do not contribute pivots, there can be still more free variables. What matters for the conclusion is that even the largest possible pivot count, \(n\), is smaller than the number \(p\) of unknowns.

From a Homogeneous System to a Vector Dependence

Let \(\mathbf{v}_1,\dots,\mathbf{v}_p\) be a list of vectors in \(\mathbb{R}^n\), and form the matrix whose columns are those vectors:

For \(\mathbf{c}=(c_1,\dots,c_p)^\top\), the matrix-vector product is \(\mathbf{A}\mathbf{c}=c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p\). If \(p>n\), the theorem gives a nonzero \(\mathbf{c}\) satisfying \(\mathbf{A}\mathbf{c}=\mathbf{0}\). Since \(\mathbf{c}\ne\mathbf{0}\), its entries are not all zero, so this equation is a dependence relation.

Proof. Write the vectors as the columns of \(\mathbf{A}\in\mathbb{R}^{n\times p}\), where \(p>n\). By the theorem, \(\mathbf{A}\mathbf{c}=\mathbf{0}\) has a solution \(\mathbf{c}\ne\mathbf{0}\). Expanding the matrix-vector product gives \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p=\mathbf{0}\) with coefficients not all zero. By the definition of linear dependence, the list is dependent. \(\square\)

Worked Examples

Common Pitfall: A Free Variable Must Be Chosen Nonzero

A free variable does not by itself display a dependence relation. For example, in the first worked example, setting the free variable \(c_3=0\) forces \(c_1=0\) and \(c_2=0\). That gives only the zero solution, which cannot establish dependence. The correction is to choose a nonzero value, such as \(c_3=1\), and then solve for the pivot variables. This produces \((-1,-1,1)^\top\), a nonzero solution that can be checked in the original vector equation.

Another important point is that the conclusion is about a list, not about each vector separately: dependence means that some choice of coefficients, not all zero, combines the vectors to give \(\mathbf{0}\). The relation may leave some vectors unused, as the coefficient \(0\) on \(\mathbf{a}_4\) did above. Row reduction guarantees a nontrivial relation; it does not guarantee that every vector must appear with a nonzero coefficient.