Testing Whether One Generated Span Lies Inside Another

Containment of Spans Is a Generator-by-Generator Question

Suppose two lists of vectors generate two subspaces of \(\mathbb{R}^n\). To decide whether one generated span lies inside the other, we do not need to describe every vector in the first span separately. It is enough to check its generators: if each generator can be built from the second list, then every combination of the first generators can also be built from the second list. This turns a question about whole sets of vectors into a finite collection of membership questions whenever the generating lists are finite.

For a set \(S\subseteq\mathbb{R}^n\), its span, \(\operatorname{span}(S)\), is the set of all finite linear combinations of vectors in \(S\). Thus, a vector in \(\operatorname{span}(S)\) has the form \(c_1\mathbf{s}_1+\cdots+c_k\mathbf{s}_k\), where \(k\) is a nonnegative integer, each \(\mathbf{s}_i\in S\), and the coefficients are real. The zero vector is included; in particular, \(\operatorname{span}(\varnothing)=\{\mathbf{0}\}\). A span is always considered as a set of vectors, regardless of whether its displayed generators form a list with repetitions.

Proof. First suppose \(\operatorname{span}(S)\subseteq\operatorname{span}(T)\). Each \(\mathbf{s}\in S\) belongs to \(\operatorname{span}(S)\), since \(\mathbf{s}=1\mathbf{s}\). The assumed containment therefore gives \(\mathbf{s}\in\operatorname{span}(T)\). Conversely, suppose every \(\mathbf{s}\in S\) belongs to \(\operatorname{span}(T)\). Any \(\mathbf{x}\in\operatorname{span}(S)\) is a finite sum \(\mathbf{x}=c_1\mathbf{s}_1+\cdots+c_k\mathbf{s}_k\). For each \(i\), write \(\mathbf{s}_i\) as a finite linear combination of vectors in \(T\). Substituting those combinations into the expression for \(\mathbf{x}\) shows that \(\mathbf{x}\) is itself a finite linear combination of vectors in \(T\). Hence \(\mathbf{x}\in\operatorname{span}(T)\), proving the containment. If \(S\) is empty, there are no generators to check and \(\operatorname{span}(S)=\{\mathbf{0}\}\), which is contained in every span. \(\square\)

The theorem is about the generators of the proposed smaller span. It does not say that every vector in \(\operatorname{span}(S)\) must be tested individually. Nor does it say that every generator in \(T\) must belong to \(\operatorname{span}(S)\); that would be an additional condition in the opposite direction.

Turning Each Membership Check into a System

Let \(\mathbf{t}_1,\ldots,\mathbf{t}_q\in\mathbb{R}^n\) be the list generating the proposed containing span, and place them as columns of \(\mathbf{A}=\begin{bmatrix}\mathbf{t}_1&\cdots&\mathbf{t}_q\end{bmatrix}\). A target vector \(\mathbf{s}\) belongs to \(\operatorname{span}\{\mathbf{t}_1,\ldots,\mathbf{t}_q\}\) exactly when there are coefficients \(x_1,\ldots,x_q\) such that \(x_1\mathbf{t}_1+\cdots+x_q\mathbf{t}_q=\mathbf{s}\). By the definition of matrix-vector multiplication, this is exactly the system \(\mathbf{A}\mathbf{x}=\mathbf{s}\), where \(\mathbf{x}=(x_1,\ldots,x_q)^\top\).

This test requires no assumption that the generators in \(T\) are independent or that the representation is unique. The question is only whether at least one coefficient vector produces the target. If the systems are inconsistent for even one generator in \(S\), the generator test proves that the proposed containment fails. If they are all consistent, the generator test proves the containment.

One Failed Generator Is Enough

To disprove containment, it is enough to find one generator of the proposed smaller span that cannot be expressed using the proposed containing list. In a coefficient system, this appears as inconsistency: row reduction produces a row asserting that a linear combination of the unknowns equals a nonzero number, even though the left side is zero.

The conclusion concerns the spans, not whether one particular expression was found. A successful expression certifies membership; a failed guess at coefficients does not certify nonmembership. To show nonmembership, the full coefficient system must be inconsistent, or another valid reason must rule out every possible choice of coefficients.

Containment, Equality, and Nonunique Coefficients

Proof. If the spans are equal, each is a subset of the other. Since every generator belongs to the span of its own set, every vector in \(S\) belongs to \(\operatorname{span}(T)\), and every vector in \(T\) belongs to \(\operatorname{span}(S)\). Conversely, if both generator conditions hold, the generator test gives \(\operatorname{span}(S)\subseteq\operatorname{span}(T)\) and \(\operatorname{span}(T)\subseteq\operatorname{span}(S)\). Two sets contained in each other are equal, so the spans are equal. \(\square\)

A Common Direction Error

A frequent mistake is to check that every generator of \(S\) lies in \(\operatorname{span}(T)\), then conclude that the spans are equal. That work proves only \(\operatorname{span}(S)\subseteq\operatorname{span}(T)\). For a concrete counterexample, take \(S\) to consist of \(\begin{bmatrix}1\\0\end{bmatrix}\), and \(T\) to consist of \(\begin{bmatrix}1\\0\end{bmatrix}\) and \(\begin{bmatrix}0\\1\end{bmatrix}\). The generator of \(S\) belongs to \(\operatorname{span}(T)\), since it is \(1\begin{bmatrix}1\\0\end{bmatrix}+0\begin{bmatrix}0\\1\end{bmatrix}\). But the second generator of \(T\) is not in \(\operatorname{span}(S)\): an equation \(c\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}0\\1\end{bmatrix}\) would require both \(c=0\) and \(0=1\). Thus the spans are not equal. The correction is to test both directions if equality is the goal, and only the specified direction if the goal is containment.

For finite lists, a reliable procedure is to keep the direction visible throughout: put the generators of the proposed containing span in the coefficient matrix, then use each generator of the proposed smaller span as a right-hand side. Every system must be consistent. A single inconsistent system disproves containment; if all are consistent, the generator test proves it. If the problem asks whether the spans are equal, repeat the test with the roles of the lists reversed.