4.2 Set language and solution sets

Linear algebra does not only study individual vectors. It often studies whole collections of vectors or matrices at once: all solutions of a system, all linear combinations of a list, all matrices satisfying an equation, or all vectors killed by a matrix.

Set language is the grammar that lets us say these things precisely. Without it, phrases such as "the same solution set", "belongs to the null space", and "these vectors span the same subspace" stay too vague to support proofs.

Why sets enter linear algebra

When you row-reduce a system, you are not trying to preserve the visible list of equations. You are trying to preserve the collection of solutions. Two systems may look different and still have exactly the same solutions.

Likewise, when you replace a spanning list by a shorter one, you are not trying to preserve the list. You are trying to preserve the set of vectors that can be built from the list.

Definition

Membership

If an object $x$ is an element of a set $S$, we write

$$x \in S.$$

If $x$ is not an element of $S$, we write

$$x \notin S.$$

The symbol $\in$ should be read as "belongs to". It is not the same as subset language. A vector may belong to a set; a smaller collection may be a subset of a larger collection.

Ambient spaces

Before writing a set in linear algebra, identify the kind of object being collected.

• $\mathbb R^n$ is the set of real column vectors with $n$ entries.
• $M_{m,n}(\mathbb R)$ is the set of real $m \times n$ matrices.
• $P_n$ is the set of real polynomials of degree at most $n$.

This ambient space matters. The expression

$$\{x : Ax=b\}$$

is incomplete unless we know the size and type of $x$. A careful version is

$$\{x\in R^n : Ax=b\}.$$

The part before the colon tells us where the objects live. The part after the colon gives the condition used to select them.

Solution sets

Let $A$ be an $m \times n$ matrix and let $b\in \mathbb R^m$.

Definition

Solution set of a linear system

The solution set of $Ax=b$ is

$$S(A,b)=\{x\in R^n : Ax=b\}.$$

So a statement such as $t\in S(A,b)$ has exact meaning:

$$t\in R^n \qquad\text{and}\qquad At=b.$$

This notation also handles the three familiar possibilities.

• If the system has a unique solution $x_0$, then $S(A,b)=\{x_0\}$.
• If the system is inconsistent, then $S(A,b)=\varnothing$.
• If the system has infinitely many solutions, then $S(A,b)$ is often written parametrically.

Worked example

Reading a parameterized solution set

Suppose the solutions of a system are described by

$$x= \begin{bmatrix}1\\0\\2\end{bmatrix} +s\begin{bmatrix}1\\1\\0\end{bmatrix} +t\begin{bmatrix}-1\\0\\1\end{bmatrix}, \qquad s,t\in R.$$

As a set, this is

$$\left\{ \begin{bmatrix}1\\0\\2\end{bmatrix} +s\begin{bmatrix}1\\1\\0\end{bmatrix} +t\begin{bmatrix}-1\\0\\1\end{bmatrix} : s,t\in R \right\}.$$

The fixed vector is one particular solution. The two direction vectors record the freedoms that can be added without leaving the solution set.

Null space and span as sets

Two set constructions recur throughout the course.

Definition

Null space

For an $m \times n$ matrix $A$,

$$N(A)=\{x\in R^n : Ax=0\}.$$

This is the solution set of the homogeneous system $Ax=0$.

Definition

Span

For vectors $u_1,\dots,u_q$ in the same vector space,

$$\operatorname{Span}\{u_1,\dots,u_q\} = \{\alpha_1u_1+\cdots+\alpha_qu_q : \alpha_1,\dots,\alpha_q\in R\}.$$

The span is a set, not the list itself. Reordering the vectors does not change the span, and adding a vector that was already a linear combination of the old ones does not change the span.

A subset proof with stacked matrices

To prove a set inclusion, translate membership into the defining equations and derive the condition for the target set. Stacking two coefficient matrices gives a useful first example of this method.

Theorem

A stacked null space is contained in a combined null space

Let $A$ and $B$ be $p \times q$ matrices, and let

$$C=\begin{bmatrix} A \\ B \end{bmatrix}.$$

For any real numbers $\alpha,\beta$,

$$N(C)\subseteq N(\alpha A+\beta B).$$

Proof

Proof from the definitions

To prove the subset relation, take an arbitrary $t\in N(C)$. By the definition of null space,

$$Ct=0.$$

Since $C$ is the matrix obtained by stacking $A$ above $B$, this says

$$\begin{bmatrix} At \\ Bt \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}.$$

Therefore $At=0$ and $Bt=0$. Hence

$$(\alpha A+\beta B)t = \alpha At+\beta Bt = 0.$$

By the definition of null space again, $t\in N(\alpha A+\beta B)$. Since the choice of $t\in N(C)$ was arbitrary, the inclusion follows.

The exact stacked-null-space identity proved in the preceding note says $N(C)=N(A)\cap N(B)$. Thus the inclusion above says that satisfying both homogeneous equations implies satisfying any fixed linear combination of them. It does not say that the combination retains both equations.

Worked example

A combined equation loses information

Take $A=[1\ 0]$ and $B=[0\ 1]$. Their stacked matrix is $C=I_2$, so $N(C)=\{0_2\}$. For $\alpha=\beta=1$, however, $A+B=[1\ 1]$, giving

$$N(A+B)=\left\{\begin{bmatrix}t\\-t\end{bmatrix}:t\in\mathbb R\right\}.$$

To prove this description, any vector in the null space must satisfy $x_1+x_2=0$, hence has the displayed form with $t=x_1$. Conversely, substituting any displayed vector makes the sum zero. The vector $(1,-1)^T$ therefore belongs to $N(A+B)$ but not to $N(C)$: its individual outputs under $A$ and $B$ are one and minus one, which cancel only after addition. The inclusion is strict, so replacing it by equality would be false.

The correct equality uses an intersection, $N(C)=N(A)\cap N(B)$. Cancellation between outputs is allowed in the combined equation, but satisfying both original equations requires each output separately to be zero. Checking this single witness establishes strictness; the parameter calculation describes all the extra solutions as well.

Set equality means two directions

Definition

Set equality

Two sets $S$ and $T$ are equal if every element of each set belongs to the other:

$$S=T \quad\Longleftrightarrow\quad \bigl(x\in S \text{ if and only if } x\in T\bigr) \text{ for every object }x.$$

In proofs, this usually becomes a two-inclusion routine:

1. prove that every element of $S$ belongs to $T$;
2. prove that every element of $T$ belongs to $S$.

The first direction alone proves only $S\subseteq T$, not equality.

Proof X-Ray

Membership supplies the data needed by each inclusion

To prove $S\subseteq T$, start with an arbitrary $x\in S$ and translate that membership into equations or coefficients. The target $x\in T$ has its own defining condition. The proof must transform the supplied information into that condition for the same vector, without assuming the conclusion.

For a span, the supplied information is the existence of a coefficient list; proving membership in another span requires constructing a new coefficient list. For a null space, the supplied information is a homogeneous equation; proving membership in another null space requires checking its matrix equation. Testing several numerical vectors cannot replace this arbitrary-vector step.

Then reverse the roles of the two sets and make a second argument. That argument may be shorter—for example, one can insert a zero coefficient for an added generator—but it must still be present. The two inclusions can use different representations; what remains fixed is the vector being shown to belong.

Follow the grammar that turns algebraic constraints into solution sets, then use one arbitrary element to prove subsets and set equality.

1. Membership versus subset

   The statement x in S says one object belongs to S. The statement S subset T compares two collections.

2. Set-builder grammar

   In {x in R^n : Ax=b}, R^n names the ambient space and Ax=b is the condition selecting the elements.

3. Solution set

   S(A,b)={x in R^n : Ax=b} is one set statement, whether the set is empty, a singleton, or a parameter family.

4. Null space and span

   N(A) is equation-defined, while Span{u1,...,uq} is parameter-defined. In both cases the notation describes a whole set.

5. Subset proof routine

   To prove S subset T, take an arbitrary element of S, unpack the definition of S, and show the condition defining T.

6. Equality proof routine

   Set equality needs both inclusions. This is the proof grammar behind removing redundant vectors from a spanning list.

Set language turns algebra into precise collections: write the ambient space, state the condition, then prove inclusions by starting with one arbitrary element.

Intersections of solution sets with the same coefficient matrix

Set language also clarifies a useful fact about systems with the same coefficient matrix. If two solution sets for $Ax=b$ and $Ax=c$ have even one common vector, then the two right-hand sides must actually be the same.

Theorem

For the same A, two nonempty-overlapping solution sets are equal

Let $A$ be an $m \times n$ matrix, and let $b,c\in \mathbb R^m$. If

$$S(A,b)\cap S(A,c)\ne\varnothing,$$

then

$$S(A,b)=S(A,c).$$

Proof

Why one common solution forces equality

Because the intersection is nonempty, there is some vector $x_0$ such that

$$x_0\in S(A,b) \qquad\text{and}\qquad x_0\in S(A,c).$$

By the definition of solution set,

$$Ax_0=b \qquad\text{and}\qquad Ax_0=c.$$

Therefore $b=c$. But if the two right-hand sides are the same, the two defining conditions are identical:

$$Ax=b \qquad\Longleftrightarrow\qquad Ax=c.$$

Thus every element of $S(A,b)$ belongs to $S(A,c)$, and every element of $S(A,c)$ belongs to $S(A,b)$. Hence $S(A,b)=S(A,c)$.

The contrapositive reading is often just as important: for a fixed matrix $A$, two consistent systems $Ax=b$ and $Ax=c$ either have disjoint solution sets or exactly the same solution set. They cannot share one solution but disagree elsewhere.

A core span argument

The following argument appears repeatedly in linear algebra, often hidden inside larger computations.

Theorem

Adding a redundant vector does not change the span

Suppose $v$ is a linear combination of $u_1,\dots,u_q$. Then

$$\operatorname{Span}\{u_1,\dots,u_q,v\} = \operatorname{Span}\{u_1,\dots,u_q\}.$$

Proof

Proof by set equality

Write

$$v=\beta_1u_1+\cdots+\beta_qu_q.$$

Let

$$S=\operatorname{Span}\{u_1,\dots,u_q,v\}, \qquad T=\operatorname{Span}\{u_1,\dots,u_q\}.$$

First take any $x\in S$. Then there are scalars $a_1,\dots,a_q,c$ such that

$$x=a_1u_1+\cdots+a_qu_q+cv.$$

Substitute the formula for $v$:

$$x=(a_1+c\beta_1)u_1+\cdots+(a_q+c\beta_q)u_q.$$

So $x\in T$.

Conversely, if $y\in T$, then

$$y=d_1u_1+\cdots+d_qu_q =d_1u_1+\cdots+d_qu_q+0v,$$

so $y\in S$. Therefore $S=T$.

This proof is not about a particular numerical example. It explains why removing redundant vectors from a spanning list is legitimate.

The converse identifies exactly which vectors are redundant

Suppose adjoining $v$ leaves the span unchanged. The vector $v$ certainly belongs to the enlarged span: give $v$ coefficient one and every old generator coefficient zero. Equality of the two spans then places $v$ in the old span, so the definition provides a linear combination of the original generators. This proves the converse, not merely another instance of the forward theorem.

Together the two directions say that a vector may be added without changing the span if and only if it is already generated by the old list. A vector outside the old span makes the new span strictly larger: the new span contains the old one by allowing coefficient zero on the added vector, while the added vector itself witnesses failure of the reverse inclusion.

Here $\operatorname{Span}(U)$ abbreviates the span of the vectors in the list $U$; it does not treat the whole list as one vector.

Theorem

Several redundant generators and equality of spans

Let $U=(u_1,\ldots,u_q)$ and $V=(v_1,\ldots,v_s)$ be finite nonempty lists of vectors in $\mathbb R^n$. Adding all vectors of $V$ to $U$ leaves the span unchanged if and only if each $v_j$ belongs to $\operatorname{Span}(U)$. Moreover,

$$\operatorname{Span}(U)=\operatorname{Span}(V)$$

if and only if every vector in each list is a linear combination of the vectors in the other list. The lengths $q$ and $s$ need not agree.

Proof

From one added vector to two-way generation

If every $v_j$ is generated by $U$, add the vectors of $V$ one at a time. The first addition does not change the span. Each subsequent $v_j$ is still generated by the original vectors, which remain in the enlarged list, so the one-vector theorem applies again. Induction proves the claim for any finite list. Conversely, each added vector belongs to the enlarged span; if this equals the old span, each added vector must already belong to the old span.

For the second statement, assume both directions of generation. Adding $V$ to $U$ leaves $\operatorname{Span}(U)$ unchanged; adding $U$ to $V$ leaves $\operatorname{Span}(V)$ unchanged. The combined lists contain the same vectors, and changing their order does not change which linear combinations can be formed. Both spans therefore equal the combined span.

Conversely, if the spans are equal, any generator from $U$ belongs to its own span and hence to the span of $V$. By definition it is generated by $V$. Interchanging the lists gives the other direction. No independence hypothesis is needed in any of these arguments.

Worked example: proving two spans are equal

Worked example

Removing a redundant generator with explicit coefficients

Let

$$u_1=\begin{bmatrix}1\\0\\1\end{bmatrix}, \qquad u_2=\begin{bmatrix}0\\1\\1\end{bmatrix}, \qquad v=\begin{bmatrix}2\\3\\5\end{bmatrix}.$$

Since

$$v=2u_1+3u_2,$$

the theorem gives

$$\operatorname{Span}\{u_1,u_2,v\} = \operatorname{Span}\{u_1,u_2\}.$$

For a complete direct check, an arbitrary vector in the larger span has the form $au_1+bu_2+cv$. Substituting the verified relation gives $(a+2c)u_1+(b+3c)u_2$, a vector in the smaller span. Conversely, $du_1+eu_2=du_1+eu_2+0v$ belongs to the larger span. The new coefficients are real whenever the old coefficients are real, so these expressions prove both inclusions for every vector, not only membership of the displayed three generators. The vector $v$ may remain computationally useful even though it does not enlarge the set that can be generated.

Worked example

Two different generating pairs give the same span

Let

$$u=\begin{bmatrix}1\\3\\5\end{bmatrix},\quad v=\begin{bmatrix}2\\4\\6\end{bmatrix},\quad w=\begin{bmatrix}3\\7\\11\end{bmatrix},\quad z=\begin{bmatrix}1\\1\\1\end{bmatrix}.$$

The forward relations are $w=u+v$ and $z=v-u$, verified in every coordinate. Thus $aw+bz=(a-b)u+(a+b)v$ for arbitrary real $a,b$, proving $\operatorname{Span}(w,z)\subseteq\operatorname{Span}(u,v)$. To obtain the reverse inclusion, solve these same two relations for the original generators:

$$u=\tfrac12w-\tfrac12z,\qquad v=\tfrac12w+\tfrac12z.$$

Consequently, for arbitrary real $c,d$,

$$cu+dv=\tfrac{c+d}{2}w+\tfrac{d-c}{2}z.$$

This is the required coefficient construction in the other direction. Every vector generated by either pair is therefore generated by the other, and the spans are equal. Merely observing that both lists contain two vectors would not prove this; the explicit relations do.

The same vector relations also handle a longer list. Adding $w$, $2u$, and $z$ to $(u,v)$ changes nothing because each added vector is already generated by that pair. The resulting five-vector list and the original two-vector list have the same span. Equality of spans concerns the available vectors, not the length of a chosen generating list; equal lengths, on the other hand, do not by themselves guarantee equality of spans.

Common mistakes

Common mistake

Confusing a vector with a set containing that vector

The vector $x_0$ and the singleton set $\{x_0\}$ are different objects. If a system has a unique solution, the solution is $x_0$, but the solution set is $\{x_0\}$.

Common mistake

Forgetting the ambient space

The condition $Ax=0$ does not by itself say whether $x$ is a vector in $\mathbb R^n$, a matrix variable, or some other object. Write the ambient set when the context is not already fixed.

Common mistake

Proving only one inclusion

To prove $S=T$, showing that every element of $S$ belongs to $T$ is not enough. You must also show that every element of $T$ belongs to $S$.

Common mistake

Forgetting that a common solution fixes the right-hand side

If the same matrix $A$ is used in both systems, a vector $x_0$ satisfying $Ax_0=b$ and $Ax_0=c$ forces $b=c$. The conclusion is not merely that the two systems are similar; their equations have the same right-hand side.

Quick checks

Checkpoint

If $S(A,b)=\varnothing$, what does that say about the system $Ax=b$?

Translate the empty set into solution language.

Solution · Answer

It says that the system has no solution. In other words, $Ax=b$ is inconsistent.

Checkpoint

Suppose $w=3u_1-u_2$. Does adding $w$ to the list $\{u_1,u_2\}$ change the span?

Use the redundant-vector theorem.

Solution · Answer

No. Since $w$ is already a linear combination of $u_1$ and $u_2$,

$$\operatorname{Span}\{u_1,u_2,w\} = \operatorname{Span}\{u_1,u_2\}.$$

Checkpoint

Suppose $S(A,b)\cap S(A,c)$ contains a vector $x_0$. What must be true about $b$ and $c$?

Use the definition of membership in a solution set.

Solution · Answer

Since $x_0\in S(A,b)$, we have $Ax_0=b$. Since $x_0\in S(A,c)$, we also have $Ax_0=c$. Therefore $b=c$, and the two solution sets are equal.

Exercises

Checkpoint

Let $S=\operatorname{Span}\{(1,0),(0,1),(1,1)\}$ and $T=\mathbb R^2$. Prove that $S=T$.

Use both inclusions, even if one direction feels obvious.

Solution · Guided solution

First, every vector in $S$ is a linear combination of vectors in $\mathbb R^2$, so $S\subseteq \mathbb R^2$.

Conversely, take any $(a,b)\in \mathbb R^2$. Then

$$(a,b)=a(1,0)+b(0,1)+0(1,1),$$

so $(a,b)\in S$. Therefore $\mathbb R^2\subseteq S$, and hence $S=T$.

Exercise: decide whether a new vector changes the span

Let $u_1=(1,0,1)^T$ and $u_2=(0,1,1)^T$. For which real $a,b,c$ does adjoining $w=(a,b,c)^T$ leave $\operatorname{Span}(u_1,u_2)$ unchanged? If it changes the span, identify a vector that proves the change.

Solution · Solution using the converse of redundancy

By the proved equivalence, the span is unchanged exactly when $w$ is already a linear combination of $u_1,u_2$. Every such combination has the form

$$su_1+tu_2=(s,t,s+t)^T.$$

Matching the first two coordinates forces $s=a$ and $t=b$; the third then requires $c=a+b$. If that condition holds, $w=au_1+bu_2$ explicitly verifies membership, so the old span is unchanged. If it fails, no coefficients can represent $w$ using the old pair. Yet $w$ belongs to the enlarged span by giving itself coefficient one. Thus $w$ witnesses strict enlargement.

The argument checks existence of a representation and proves the failure when none exists. It does not assume that a vector is redundant merely because its ambient dimension is the same as that of the old generators.

A useful final comparison is between a generating list and a basis. The arguments in this note only ask which vectors can be generated. They deliberately allow repetitions and unnecessary generators. In the preceding five-vector example, removing three generators changes the list but not the span. Deciding whether the remaining list is independent is a separate question, treated in the later independence and basis notes. Keeping these questions separate avoids using equality of spans as if it were a claim of unique coefficients.

Read this first

This note extends 1.1 Equations and solution sets and prepares the set-equality arguments used in 6.3 Linear combinations and span.