Row Reduction for Testing Span Membership

From Span Membership to a Row-Reduction Test

To decide whether a target vector can be made from a given list, we need to check whether some choice of coefficients produces it. Row reduction turns that question into a systematic test: a particular row in the reduced augmented matrix can prove that no such coefficients exist. If no such row appears, the system is consistent and the target belongs to the span.

Let \(\mathbf{a}_1,\dots,\mathbf{a}_p\) be vectors in \(\mathbb{R}^m\). Their span is the set of all their linear combinations:

Put the given vectors in the columns of \(\mathbf{A}\in\mathbb{R}^{m\times p}\), and let the target be \(\mathbf{b}\in\mathbb{R}^m\). A coefficient vector \(\mathbf{x}=(x_1,\dots,x_p)^\top\) satisfies \(\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_p\mathbf{a}_p\). Thus membership asks whether some \(\mathbf{x}\) satisfies \(\mathbf{A}\mathbf{x}=\mathbf{b}\). In the augmented matrix \([\mathbf{A}\ \mathbf{b}]\), the target is the final column. The dimensions matter: \(\mathbf{A}\) has one row for each coordinate of a vector and one column for each given vector; the appended target adds one more column.

Proof. By the definition of span, \(\mathbf{b}\) belongs to the span exactly when there are real numbers \(c_1,\dots,c_p\) such that \(c_1\mathbf{a}_1+\cdots+c_p\mathbf{a}_p=\mathbf{b}\). The definition of matrix multiplication gives \(\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_p\mathbf{a}_p\). Taking \(x_j=c_j\) for each \(j\), the span equation is exactly \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Therefore a suitable linear combination exists exactly when the system has a solution. \(\square\)

What to Look for After Row Reduction

Row reduction applies elementary row operations: swapping two rows, multiplying a row by a nonzero scalar, or adding a multiple of one row to another. Each operation is reversible. A swap can be undone by swapping back; scaling by \(c\ne0\) can be undone by scaling by \(1/c\); and adding a multiple of a row can be undone by subtracting that same multiple. Consequently, these operations preserve the solutions of the system represented by the augmented matrix.

Once the augmented matrix is in reduced row echelon form (RREF), each row represents an equation. A row whose coefficient entries are all zero but whose final, augmented entry is nonzero represents an impossible equation, such as \(0=1\). If there is no such row, the system is consistent: assign zero to any free variables, and the pivot equations determine values for the pivot variables. In RREF, each pivot variable appears with coefficient \(1\) in its pivot row and with coefficient \(0\) in the other pivot rows, so these assignments satisfy the equations.

Proof. By the preceding theorem, membership is equivalent to consistency of \(\mathbf{A}\mathbf{x}=\mathbf{b}\). The reversible row operations used to reduce the augmented matrix preserve its solution set, so the original system is consistent exactly when the reduced system is consistent. A row \([0\ \cdots\ 0\mid d]\), with \(d\ne0\), says \(0=d\), which has no solution; therefore its presence implies inconsistency. Conversely, suppose no such row occurs. Every zero coefficient row then has zero on the right as well, so it gives the valid equation \(0=0\). In each remaining row, the pivot variable equals the right-hand entry minus a sum of terms involving free variables. Set every free variable to zero; each pivot variable can then be assigned the right-hand entry in its row. These assignments satisfy every nonzero row, and the zero rows are already satisfied. The reduced system, and hence the original system, is consistent. Combining this with the membership-solvability equivalence proves the criterion in both directions. \(\square\)

In practice, row-reduce the whole augmented matrix, including the target column. Do not decide membership merely by counting pivots in \(\mathbf{A}\), or by reducing \(\mathbf{A}\) while ignoring \(\mathbf{b}\). The target determines the right-hand side of the equations, and a contradiction can appear only when that column is included.

Worked Membership Tests

Common Mistake: Reducing Only the Given-Vector Matrix

A tempting but incorrect argument is: “The matrix of given vectors has two pivot columns, so every target in \(\mathbb{R}^3\) is in their span.” The second worked example disproves this claim. Its two columns each give a pivot, but the augmented reduction for \((1,1,3)^\top\) produces the row \([0\ 0\mid1]\). Two pivots in the coefficient matrix do not make every possible right-hand side consistent. For the specific target, the augmented matrix—not the pivot count of \(\mathbf{A}\) alone—provides the test.

Another construction error is to append the target as a row rather than as a column. If \(\mathbf{A}\) is \(m\times p\), then \(\mathbf{b}\) has \(m\) entries and must be appended as a final column, producing an \(m\times(p+1)\) matrix. Appending it as a row changes the equation being represented and may not even give a matrix with matching row lengths.

Why the Test Is Useful

Span membership is a yes-or-no question about whether a target can be produced by a specified set of vectors. The augmented matrix makes the relationship between the vectors and the target explicit in one calculation. A contradictory row gives a precise reason for a negative answer; in its absence, consistency establishes a positive answer. In later problems, the reduced system can also be used to determine coefficients, but the test here needs only the presence or absence of a contradictory row.

Keep the direction of the conclusion tied to the system: consistent means that at least one coefficient choice produces the target, so it is in the span. Inconsistent means that no coefficient choice works, so it is not in the span. A row \([0\ \cdots\ 0\mid0]\) is not a contradiction; only a zero coefficient row with a nonzero final entry rules out membership.