maths.free › Linear Algebra › 2. Vectors › Spanning Sets

Spanning Sets

In this section we will provide an extremely compact way to describe an infinite set of vectors, making use of linear combinations.

Spanning Sets

In this section we will provide an extremely compact way to describe an infinite set of vectors, making use of linear combinations. This will give us a convenient way to describe the solution set of a linear system, the null space of a matrix, and many other sets of vectors.

S=\set{\colvector{1\\2\\-1},\,\colvector{3\\-4\\2},\,\colvector{4\\-2\\1}}
Use $S$ and $W$ from the previous question. Is the vector $\colvector{6\\5\\-1}$ in $W$? Give an explanation of the reason for your answer.
A= \begin{bmatrix} 1 & 3 & 1 & 9\\ 2 & 1 & -3 & 8\\ 1 & 1 & -1 & 5 \end{bmatrix}

Span of a Set of Vectors

In we saw the solution set of a homogeneous system described as all possible linear combinations of two particular vectors. This is a useful way to construct or describe infinite sets of vectors, so we encapsulate the idea in a definition.

The span is just a set of vectors, though in all but one situation it is an infinite set. (Just when is it not infinite?) So we start with a finite collection of vectors $S$ ($p$ of them to be precise), and use this finite set to describe an infinite set of vectors, $\spn{S}$. Confusing the finite set $S$ with the infinite set $\spn{S}$ is one of the most persistent problems in understanding introductory linear algebra. We will see this construction repeatedly, so let us work through some examples to get comfortable with it. The most obvious question about a set is if a particular item of the correct type is in the set, or not in the set.

Having analyzed in , we will of course subject to a similar investigation.

Consistent Systems and Spans

With the notion of a span, we can expand our techniques for checking the consistency of a linear system. tells us a system is consistent if and only if the vector of constants is a linear combination of the columns of the coefficient matrix. This is because says that any solution to the system will provide a linear combination of the columns of the coefficient that equals the vector of constants. So consistency of a system is equivalent to the membership of the vector of constants in the span of the columns of the coefficient matrix. Read that last sentence again carefully. We will see this idea again, but more formally, in .

We will reprise , which is based on . We again make use of the matrix method .columns() to get all of the columns into a list at once.

You could try to find an example of a vector of constants which would create an inconsistent system with this coefficient matrix. But there is no such thing. Here is why the null space of coeff is trivial, just the zero vector.

The system is consistent, as we have shown, so we can apply . We can read as saying any two different solutions of the system will differ by an element of the null space, and the only possibility for this null space vector is just the zero vector. In other words, any two solutions cannot be different.

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Spanning Sets of Null Spaces

We saw in that when a system of equations is homogeneous the solution set can be expressed in the form described by where the vector $\vect{c}$ is the zero vector. We can essentially ignore this vector, so that the remainder of the typical expression for a solution looks like an arbitrary linear combination, where the scalars are the free variables and the vectors are $\vectorlist{u}{n-r}$. Which sounds a lot like a span. This is the substance of the next theorem.

Theorem: Spanning Sets for Null Spaces

Suppose that $A$ is an $m\times n$ matrix, and $B$ is a row-equivalent matrix in reduced row-echelon form. Suppose that $B$ has $r$ pivot columns, with indices given by $D=\set{d_1,\,d_2,\,d_3,\,\ldots,\,d_r}$, while the $n-r$ non-pivot columns have indices $F=\set{f_1,\,f_2,\,f_3,\,\ldots,\,f_{n-r},\,n+1}$. Construct the $n-r$ vectors $\vect{z}_j$, $1\leq j\leq n-r$ of size $n$, \vectorentry{\vect{z}_j}{i}= \begin{cases} 1&\text{if $i\in F$, $i=f_j$}\\ 0&\text{if $i\in F$, $i\neq f_j$}\\ -\matrixentry{B}{k,f_j}&\text{if $i\in D$, $i=d_k$} \end{cases}

Then the null space of $A$ is given by \nsp{A}=\spn{\left\{\vectorlist{z}{n-r}\right\}}

Proof

Consider the homogeneous system with $A$ as a coefficient matrix, $\homosystem{A}$. Its set of solutions, $S$, is by , the null space of $A$, $\nsp{A}$. Let $B^{\prime}$ denote the result of row-reducing the augmented matrix of this homogeneous system. Since the system is homogeneous, the final column of the augmented matrix will be all zeros, and after any number of row operations (), the column will still be all zeros. So $B^{\prime}$ has a final column that is totally zeros.

Now apply to $B^{\prime}$, after noting that our homogeneous system must be consistent (). The vector $\vect{c}$ has zeros for each entry that has an index in $F$. For entries with their index in $D$, the value is $-\matrixentry{B^{\prime}}{k,{n+1}}$, but for $B^{\prime}$ any entry in the final column (index $n+1$) is zero. So $\vect{c}=\zerovector$. The vectors $\vect{z}_j$, $1\leq j\leq n-r$ are identical to the vectors $\vect{u}_j$, $1\leq j\leq n-r$ described in . Putting it all together and applying in the final step, \nsp{A} &=S\\ &=\setparts{ \vect{c}+\alpha_1\vect{u}_1+\alpha_2\vect{u}_2+\alpha_3\vect{u}_3+\cdots+\alpha_{n-r}\vect{u}_{n-r} }{ \alpha_1,\,\alpha_2,\,\alpha_3,\,\ldots,\,\alpha_{n-r}\in\complex{\null} }\\ &=\setparts{ \alpha_1\vect{u}_1+\alpha_2\vect{u}_2+\alpha_3\vect{u}_3+\cdots+\alpha_{n-r}\vect{u}_{n-r} }{ \alpha_1,\,\alpha_2,\,\alpha_3,\,\ldots,\,\alpha_{n-r}\in\complex{\null} }\\ &=\spn{\set{\vectorlist{z}{n-r}}}

Here is an example that will simultaneously exercise the span construction and , while also pointing the way to the next section.

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Symbols used here

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

matrix
A rectangular array of numbers; a linear map.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

\mathbf{v},\ \vec{v}

vector
A quantity with magnitude and direction; a column of numbers.

\det A,\ |A|

determinant
Scaling factor of area/volume under A; zero means singular.

A^{-1},\ A^{T}

inverse, transpose
The matrix that undoes A; A with rows and columns swapped.

\lambda

lambda (eigenvalue)
The factor by which an eigenvector is stretched: Av = λv.

\mathbf{u} \cdot \mathbf{v},\ \|\mathbf{v}\|

dot product, norm
Σ u_i v_i; the length of v, √(v·v).

Questions people ask

What does a determinant mean geometrically?

It is the factor by which the matrix scales area (2×2) or volume (3×3), with a negative sign if orientation flips. Zero means the matrix flattens space and cannot be undone.

What is an eigenvector?

A direction the matrix does not turn — it only stretches it by the eigenvalue. Along eigenvectors a complicated matrix acts like multiplication by a number.

Why is matrix multiplication not commutative?

Because a matrix is a transformation and AB means "do B, then A". Rotating then reflecting is not the same as reflecting then rotating.

নিজের চেষ্টা করো

Parts of this page are adapted from Beezer, A First Course in Linear Algebra (GFDL 1.2). Condensed and re-explained here; errors are ours.

আরও Linear Algebra

Determinants Matrix inverse Eigenvalues and eigenvectors Matrix multiplication Row reduction Vector spaces, span and linear independence Orthogonality, projections and least squares Diagonalisation and matrix powers Linear transformations and change of basis