4.2 Set language and solution sets

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 4.2.1

(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 4.2.2

(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 4.2.3

(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 4.2.4

(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 4.2.5

(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 4.2.6

(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 4.2.7

(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 4.2.8

(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.

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 4.2.9

(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 4.2.10

(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 4.2.11

(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 4.2.12

(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 4.2.13

(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

Quick check

(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.

Quick check

(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\}.$$

Quick check

(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

Quick check

(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 6.4 Linear dependence and independence and 6.5 Basis and dimension. Keeping these questions separate avoids using equality of spans as if it were a claim of unique coefficients.

Related notes

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