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.

$R^n$ is the set of real column vectors with n entries.
$M_{m,n}(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 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

Assignment problems often ask you to prove a set inclusion directly from the definitions rather than by quoting a larger theorem. The following pattern is a good model.

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

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:

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

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

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

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

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

Worked example: proving two spans are equal

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

The vector v may still be useful computationally, but it does not enlarge the set of vectors that can be produced.

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 $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

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

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

Exercises

Quick check

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

Use both inclusions, even if one direction feels obvious.

Solution

Guided solution

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.

4.2 Set language and solution sets

MATH1030: Linear algebra I

Why sets enter linear algebra

Membership

Ambient spaces

Solution sets

Solution set of a linear system

Reading a parameterized solution set

Null space and span as sets

Null space

Span

A subset proof with stacked matrices

A stacked null space is contained in a combined null space

Proof from the definitions

Set equality means two directions

Set equality

Intersections of solution sets with the same coefficient matrix

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

Why one common solution forces equality

A core span argument

Adding a redundant vector does not change the span

Proof by set equality

Worked example: proving two spans are equal

Common mistakes

Confusing a vector with a set containing that vector

Forgetting the ambient space

Proving only one inclusion

Forgetting that a common solution fixes the right-hand side

Quick checks

If S(A,b)=∅S(A,b)=\varnothingS(A,b)=∅, what does that say about the system Ax=bAx=bAx=b?

Answer

Suppose w=3u1−u2w=3u_1-u_2w=3u1​−u2​. Does adding w to the list {u1,u2}\{u_1,u_2\}{u1​,u2​} change the span?

Answer

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

Answer

Exercises

Let S=Span⁡{(1,0),(0,1),(1,1)}S=\operatorname{Span}\{(1,0),(0,1),(1,1)\}S=Span{(1,0),(0,1),(1,1)} and T=R2T=R^2T=R2. Prove that S=TS=TS=T.

Guided solution

Read this first

Section mastery checkpoint

Prerequisites

Key terms in this unit

More notes in this series

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

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

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

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