5.1: Column space

Example: A plane¶

Let’s start with the $3\times2$ matrix

A=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}.

Suppose we multiply $A$ by $\vec v=\begin{bmatrix}v_1\\v_2\end{bmatrix}$ . What are the components of the output?

A\vec v=\begin{bmatrix}v_1\\v_1+v_2\\v_2\end{bmatrix}.

Notice that any vector $\begin{bmatrix}x\\y\\z\end{bmatrix}$ that could be an output of $A\vec v$ satisfies

y=x+z,\qquad\text{or equivalently,}\qquad x-y+z=0.

Remember, a plane in $\mathbb R^3$ is a set of vectors whose entries satisfy a linear equation involving $x$ , $y$ , and $z$ . Here, the plane is

P=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\in\mathbb R^3:x-y+z=0\right\}.

Every output of $A$ lies on this plane: plugging in the entries of $\begin{bmatrix}v_1\\v_1+v_2\\v_2\end{bmatrix}$ gives

v_1-(v_1+v_2)+v_2=0.

And every vector on this plane is an output of $A$ . For example, $\begin{bmatrix}2\\5\\3\end{bmatrix}$ is on the plane, since $2-5+3=0$ , and

A\begin{bmatrix}2\\3\end{bmatrix} =\begin{bmatrix}2\\2+3\\3\end{bmatrix} =\begin{bmatrix}2\\5\\3\end{bmatrix}.

The same idea works for any vector on the plane: use its first and third entries as the input, and the middle entry takes care of itself because $y=x+z$ . So the set of possible outputs of $A$ is exactly this plane.

import numpy as np
import plotly.graph_objects as go
from pathlib import Path
import sys

_notes_root = next(p for p in [Path.cwd(), *Path.cwd().parents] if (p / 'myst.yml').exists())
if str(_notes_root) not in sys.path:
    sys.path.insert(0, str(_notes_root))
from plot_style import style_plotly

BLUE, ORANGE = '#3d81f6', 'orange'


def line3(fig, start, end, color, width=2):
    fig.add_trace(go.Scatter3d(
        x=[start[0], end[0]], y=[start[1], end[1]], z=[start[2], end[2]],
        mode='lines', line=dict(color=color, width=width),
        hoverinfo='skip', showlegend=False))


def vector3(fig, end, label, color, offset):
    end = np.asarray(end, dtype=float)
    direction = end / np.linalg.norm(end)
    line3(fig, np.zeros(3), end - .07 * direction, color, width=7)
    fig.add_trace(go.Cone(
        x=[end[0]], y=[end[1]], z=[end[2]],
        u=[direction[0]], v=[direction[1]], w=[direction[2]],
        anchor='tip', sizemode='absolute', sizeref=.2,
        colorscale=[[0, color], [1, color]], showscale=False,
        hoverinfo='skip', showlegend=False))
    pos = end + np.asarray(offset)
    # Scene annotations render LaTeX and follow their 3D positions when rotated.
    fig.layout.scene.annotations += (dict(
        x=pos[0], y=pos[1], z=pos[2], text=label,
        showarrow=False, font=dict(family='Palatino', color=color, size=22)),)


fig = style_plotly(go.Figure(), renderer='plotly_mimetype')
axis = dict(range=[-2.2, 2.2], dtick=1, tickfont=dict(size=11),
            showbackground=True, showspikes=False, backgroundcolor='white',
            gridcolor='#e5e7eb', zerolinecolor='#9ca3af')
fig.update_layout(
    autosize=True, height=520, showlegend=False, font=dict(size=16),
    margin=dict(l=0, r=0, t=15, b=0),
    scene=dict(
        bgcolor='white', aspectmode='cube',
        xaxis=dict(title=dict(text='x', font=dict(size=13)), **axis),
        yaxis=dict(title=dict(text='y', font=dict(size=13)), **axis),
        zaxis=dict(title=dict(text='z', font=dict(size=13)), **axis),
        camera=dict(eye=dict(x=1.6, y=-2.1, z=1.3))))
for direction in np.eye(3):
    line3(fig, -2.2 * direction, 2.2 * direction, '#9ca3af')

# Match Chapter 2's complete rectangular plane patch and visible boundary.
normal = np.array([1., -1., 1.])
unit = normal / np.linalg.norm(normal)
reference = np.eye(3)[np.argmin(np.abs(unit))]
u = np.cross(unit, reference)
u /= np.linalg.norm(u)
v = np.cross(unit, u)
corners = np.array([s*u + t*v for s, t in
                    [(-1.8, -1.8), (1.8, -1.8), (1.8, 1.8), (-1.8, 1.8)]])
fig.add_trace(go.Mesh3d(
    x=corners[:, 0].tolist(), y=corners[:, 1].tolist(), z=corners[:, 2].tolist(),
    i=[0, 0], j=[1, 2], k=[2, 3], color=BLUE, opacity=.24,
    flatshading=True,
    lighting=dict(ambient=1, diffuse=0, specular=0, fresnel=0, roughness=1),
    showscale=False, hoverinfo='skip', showlegend=False))
for i in range(4):
    line3(fig, corners[i], corners[(i+1) % 4], BLUE)

vector3(fig, [1, 1, 0], r'$\vec{a}_1$', BLUE, (.14, .06, .16))
vector3(fig, [0, 1, 1], r'$\vec{a}_2$', ORANGE, (-.14, .06, .16))
plane_label = .8 * corners[2]
fig.layout.scene.annotations += (dict(
    x=plane_label[0], y=plane_label[1], z=plane_label[2],
    text=r'$P$', showarrow=False,
    font=dict(family='Palatino', color=BLUE, size=24)),)
fig.add_trace(go.Scatter3d(x=[0], y=[0], z=[0], mode='markers',
                         marker=dict(color='black', size=3),
                         hoverinfo='skip', showlegend=False))
# Keep the plot interactive and load MathJax for its LaTeX labels.
import html
import warnings
from IPython.display import HTML, display

doc = fig.to_html(include_plotlyjs='cdn', include_mathjax='cdn',
                  config=dict(responsive=True, displaylogo=False, scrollZoom=False),
                  div_id='column-space-plane')
doc = doc.replace('html, body {height: 100%;}',
                  'html, body {height: 100%; margin: 0; background: white;}')
with warnings.catch_warnings():
    warnings.simplefilter('ignore', UserWarning)
    display(HTML('<iframe title="The plane P and the two columns of A" srcdoc="'
                 + html.escape(doc, quote=True)
                 + '" style="width:100%;height:530px;border:0;display:block;background:white;"></iframe>'))

Loading...

Drag to rotate. The two columns, $\vec a_1=\begin{bmatrix}1\\1\\0\end{bmatrix}$ and $\vec a_2=\begin{bmatrix}0\\1\\1\end{bmatrix}$ , lie on the plane $x-y+z=0$ .

Span and column space¶

Recall the column perspective on matrix-vector multiplication. If we call the columns of $A$ $\vec a_1$ and $\vec a_2$ , then

A\begin{bmatrix}v_1\\v_2\end{bmatrix} =v_1\underbrace{\begin{bmatrix}1\\1\\0\end{bmatrix}}_{\vec a_1} +v_2\underbrace{\begin{bmatrix}0\\1\\1\end{bmatrix}}_{\vec a_2}.

Each input gives us a linear combination of the columns. Letting the input vary gives us all possible linear combinations. This set is called their span.

This isn’t your first time seeing the idea of a span:

The span of a single nonzero vector is a line through the origin.
The span of two nonzero vectors $\vec u$ and $\vec v$ is either a line through the origin if the vectors are linearly dependent (one is a scalar multiple of the other), or a plane through the origin if they are linearly independent (they don’t lie along the same line).

The new thing is that we’ve generalized the definition to an arbitrary number of vectors, with any number of entries. Intuitively, think of the span as the set of all new vectors you can produce using $\vec v_1,\ldots,\vec v_d$ as building blocks.

When the vectors are the columns of a matrix, we give their span a special name.

Pay attention to the two numbers in the shape $n\times d$ . Inputs have $d$ entries, while outputs have $n$ entries. So the column space is a subset of $\mathbb R^n$ , regardless of how many columns there are.

For our matrix

A=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix},

we found that

\operatorname{colsp}(A) =\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\in\mathbb R^3:x-y+z=0\right\}=P,

a plane in $\mathbb R^3$ .

This gives us a way to connect our new question back to the one from Chapter 4. Asking whether $A\vec x=\vec b$ has a solution is asking whether $\vec b$ is one of the outputs $A$ can produce. In our new terminology:

Adding a column¶

What happens to the column space if we add another column to $A$ ? It depends on whether that column can already be made using the original columns.

A redundant column¶

Now consider the matrix

B=\begin{bmatrix}1&0&2\\1&1&1\\0&1&-1\end{bmatrix}.

Its first two columns are the same as $A$ ’s. Its third column is a linear combination of the first two:

\vec a_3=\begin{bmatrix}2\\1\\-1\end{bmatrix} =2\begin{bmatrix}1\\1\\0\end{bmatrix}-\begin{bmatrix}0\\1\\1\end{bmatrix} =2\vec a_1-\vec a_2.

Does this column give us any new outputs? Let’s write a general output:

B\begin{bmatrix}p\\q\\r\end{bmatrix} =p\vec a_1+q\vec a_2+r(2\vec a_1-\vec a_2) =(p+2r)\vec a_1+(q-r)\vec a_2.

This is still a combination of the first two columns. Conversely, we can produce any output of $A$ using $B$ by putting a zero in the third input entry. For example,

A\begin{bmatrix}4\\5\end{bmatrix} =B\begin{bmatrix}4\\5\\0\end{bmatrix} =\begin{bmatrix}4\\9\\5\end{bmatrix}.

Thus $\operatorname{colsp}(B)=\operatorname{colsp}(A)=P$ . We call the third column redundant because removing it does not change the span.

But $\begin{bmatrix}4\\5\\0\end{bmatrix}$ is not the only input that $B$ sends to $\begin{bmatrix}4\\9\\5\end{bmatrix}$ . There are infinitely many! How can we find them? We solve

B\vec x=\begin{bmatrix}4\\9\\5\end{bmatrix}.

An LU factorization is

B=\underbrace{\begin{bmatrix}1&0&0\\1&1&0\\0&1&1\end{bmatrix}}_L \underbrace{\begin{bmatrix}1&0&2\\0&1&-1\\0&0&0\end{bmatrix}}_U.

Forward substitution in $L\vec y=\begin{bmatrix}4\\9\\5\end{bmatrix}$ gives $\vec y=\begin{bmatrix}4\\5\\0\end{bmatrix}$ . Then $U\vec x=\vec y$ gives

x_1+2x_3=4,\qquad x_2-x_3=5,\qquad 0=0.

Setting the free variable $x_3=t$ , the complete set of solutions is

\boxed{\vec x=\begin{bmatrix}4\\5\\0\end{bmatrix} +t\begin{bmatrix}-2\\1\\1\end{bmatrix} =\begin{bmatrix}4-2t\\5+t\\t\end{bmatrix},\qquad t\in\mathbb R.}

The input $\begin{bmatrix}4\\5\\0\end{bmatrix}$ corresponds to $t=0$ . For example, $t=1$ gives the different input $\begin{bmatrix}2\\6\\1\end{bmatrix}$ , with the same output $\begin{bmatrix}4\\9\\5\end{bmatrix}$ .

For $A$ , the only input producing this output is $\begin{bmatrix}4\\5\end{bmatrix}$ : the first and third output entries determine its two input entries. The extra column of $B$ gives us infinitely many ways to produce the same output, without changing which outputs are possible.

import html
import warnings
from IPython.display import HTML, display

# A is static; B cycles through eight inputs with the same output.
_machine_doc = r'''<!doctype html>
<html><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1">
<script>window.MathJax={tex:{inlineMath:[['$','$']]},svg:{fontCache:'local'}};</script>
<script defer src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js"></script>
<style>
*{box-sizing:border-box}body{margin:0;background:white;color:#253047;font:17px Palatino,'Palatino Linotype',serif}
.panel{position:relative;height:180px;margin:10px 8px;border:1px solid #e2e6ed;border-radius:12px;overflow:hidden;background:#fff}
.label{position:absolute;top:12px;left:16px;font-size:16px}.track{position:absolute;left:8%;right:8%;top:108px;border-top:2px solid #dce3ed}
.machine{position:absolute;left:44%;top:65px;width:22%;height:85px;display:flex;align-items:center;justify-content:center;gap:5px;border:2px solid var(--color);border-radius:10px;background:var(--fill);z-index:3;font-size:19px}
.vector{position:absolute;top:72px;left:7%;height:72px;min-width:60px;display:flex;align-items:center;justify-content:center;border-radius:8px;background:white;color:var(--color);z-index:2;animation:travel 16s linear infinite;animation-delay:var(--delay,0s);opacity:0}
.output{position:absolute;left:77%;top:71px;height:80px;display:flex;align-items:center;justify-content:center;color:#253047;background:white;padding:0 8px;z-index:4}
.arrow{position:absolute;top:94px;left:70%;font-size:24px;color:var(--color)}
.panel:not(.many) .vector{animation:none;opacity:1;left:16%}
@keyframes travel{0%{left:6%;opacity:0}2%{opacity:1}27%{left:40%;opacity:1}31%,100%{left:44%;opacity:0}}
.caption{margin:12px 12px 6px;text-align:center;font-size:16px;line-height:1.5}.controls{text-align:center;margin:8px}button{font:15px Palatino,serif;background:white;border:1px solid #b8c1d0;border-radius:6px;padding:5px 16px;cursor:pointer}.paused .vector{animation-play-state:paused}
@media(prefers-reduced-motion:reduce){.vector{animation:none;opacity:1;left:9%}.many .vector{display:none}.many .vector:nth-child(3){display:flex}}
</style></head><body>
<div class="panel" style="--color:#3d81f6;--fill:#edf4ff">
<div class="label">One input produces this output</div><div class="track"></div>
<div class="vector">$\begin{bmatrix}4\\5\end{bmatrix}$</div>
<div class="machine">Multiply by $A$</div><div class="arrow">→</div>
<div class="output">$\begin{bmatrix}4\\9\\5\end{bmatrix}$</div></div>
<div class="panel many" style="--color:orange;--fill:#fff5e5">
<div class="label">Infinitely many inputs produce this output</div><div class="track"></div>
<div class="vector" style="--delay:-14s">$\begin{bmatrix}10\\2\\-3\end{bmatrix}$</div>
<div class="vector" style="--delay:-12s">$\begin{bmatrix}8\\3\\-2\end{bmatrix}$</div>
<div class="vector" style="--delay:-10s">$\begin{bmatrix}6\\4\\-1\end{bmatrix}$</div>
<div class="vector" style="--delay:-8s">$\begin{bmatrix}4\\5\\0\end{bmatrix}$</div>
<div class="vector" style="--delay:-6s">$\begin{bmatrix}2\\6\\1\end{bmatrix}$</div>
<div class="vector" style="--delay:-4s">$\begin{bmatrix}0\\7\\2\end{bmatrix}$</div>
<div class="vector" style="--delay:-2s">$\begin{bmatrix}-2\\8\\3\end{bmatrix}$</div>
<div class="vector" style="--delay:0s">$\begin{bmatrix}-4\\9\\4\end{bmatrix}$</div>
<div class="machine">Multiply by $B$</div><div class="arrow">→</div>
<div class="output">$\begin{bmatrix}4\\9\\5\end{bmatrix}$</div></div>
<div class="caption">Eight examples are shown. The complete family of inputs is<br> $\begin{bmatrix}4-2t\\5+t\\t\end{bmatrix}$, $t\in\mathbb R$.</div>
<div class="controls"><button type="button" onclick="document.body.classList.toggle('paused');this.textContent=document.body.classList.contains('paused')?'Play':'Pause'">Pause</button></div>
</body></html>'''
with warnings.catch_warnings():
    warnings.simplefilter('ignore', UserWarning)
    display(HTML('<iframe title="One input for A and infinitely many inputs for B" srcdoc="'
                 + html.escape(_machine_doc, quote=True)
                 + '" style="width:100%;height:540px;border:0;display:block;background:white;"></iframe>'))

Loading...

A column outside the span¶

Now consider the matrix

C=\begin{bmatrix}1&0&2\\1&1&4\\0&1&3\end{bmatrix}.

The third column is $\begin{bmatrix}2\\4\\3\end{bmatrix}$ . It is not on $P$ , since $2-4+3\ne0$ . So it cannot be written as a linear combination of the first two columns. The three columns are linearly independent: none can be made using the other two. The span of all three columns is larger than the span of just the first two. We will formally define linear independence in Chapter 5.2.

All the old outputs are still available: $C\begin{bmatrix}4\\5\\0\end{bmatrix}=A\begin{bmatrix}4\\5\end{bmatrix}$ . But now there are new outputs, too.

Do we get all of $\mathbb R^3$ ? An LU factorization of $C$ answers this:

C= \underbrace{\begin{bmatrix}1&0&0\\1&1&0\\0&1&1\end{bmatrix}}_L \underbrace{\begin{bmatrix}1&0&2\\0&1&2\\0&0&1\end{bmatrix}}_U.

For any right-hand side, forward substitution determines one intermediate vector, and back substitution determines one input. There are no free variables or consistency conditions. Therefore,

\operatorname{colsp}(C)=\mathbb R^3.

Geometrically, the first two columns span a plane, and the third adds a direction outside that plane. Their linear combinations fill all of $\mathbb R^3$ .

Adding a column can change which outputs are possible, how many inputs produce them, or both. In Chapter 5.2, we’ll connect these observations to linear independence and invertibility.

More examples¶

Example: A line or all of $\mathbb R^2$ ¶

For $D=\begin{bmatrix}2&-6\\3&-9\end{bmatrix}$ , the second column is -3 times the first, so $\operatorname{colsp}(D)$ is a line:

\operatorname{colsp}(D) =\left\{t\begin{bmatrix}2\\3\end{bmatrix}:t\in\mathbb R\right\} =\left\{\begin{bmatrix}x\\y\end{bmatrix}\in\mathbb R^2:3x-2y=0\right\}.

This is what we mean by the line $3x-2y=0$ : the set of vectors whose entries satisfy that equation.

For $E=\begin{bmatrix}2&-1\\1&3\end{bmatrix}$ , the columns are not scalar multiples, so

\operatorname{colsp}(E)=\mathbb R^2.

We can also see this using the inverse. The matrix $E$ is invertible, with

E^{-1}=\frac{1}{2(3)-(-1)(1)}\begin{bmatrix}3&1\\-1&2\end{bmatrix} =\frac17\begin{bmatrix}3&1\\-1&2\end{bmatrix}.

For any $\vec b=\begin{bmatrix}b_1\\b_2\end{bmatrix}\in\mathbb R^2$ , the equation $E\vec x=\vec b$ has the unique solution

\vec x=E^{-1}\vec b =\frac17\begin{bmatrix}3&1\\-1&2\end{bmatrix}\begin{bmatrix}b_1\\b_2\end{bmatrix} =\begin{bmatrix}(3b_1+b_2)/7\\(-b_1+2b_2)/7\end{bmatrix}.

Every vector in $\mathbb R^2$ is therefore an output of $E$ .

$D$ , on the other hand, is not invertible. Trying the same inverse formula would require

\frac{1}{2(-9)-(-6)(3)}\begin{bmatrix}-9&6\\-3&2\end{bmatrix} =\frac{1}{0}\begin{bmatrix}-9&6\\-3&2\end{bmatrix},

which is undefined. Its columns only produce vectors on the line $3x-2y=0$ , so we cannot solve $D\vec x=\vec b$ for every $\vec b\in\mathbb R^2$ .

Activity 3

Let $Q=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\in\mathbb R^3:2x-y+z=0\right\}$ . Which matrices have column space equal to $Q$ ?

F_1=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix},\qquad F_2=\begin{bmatrix}1&0\\2&1\\0&1\end{bmatrix},\qquad F_3=\begin{bmatrix}1&0&2\\2&1&3\\0&1&-1\end{bmatrix},

F_4=\begin{bmatrix}1&3&-2\\2&6&-4\\0&0&0\end{bmatrix},\qquad F_5=\begin{bmatrix}1&0\\2&2\\0&1\end{bmatrix}.

Solution

$F_2$ and $F_3$ . Here’s why each choice does or doesn’t work:

$F_1$ has two rows, so its outputs belong to $\mathbb R^2$ . Its column space cannot be a plane in $\mathbb R^3$ .
$F_2\begin{bmatrix}s\\t\end{bmatrix}=\begin{bmatrix}s\\2s+t\\t\end{bmatrix}$ . These outputs satisfy $2x-y+z=0$ . Conversely, every vector on $Q$ is obtained by choosing $s=x$ and $t=z$ .
$F_3$ has the same first two columns as $F_2$ , and its third column is twice the first minus the second. It has the same column space.
All three columns of $F_4$ are on $Q$ , but they are multiples of a single vector. Their span is only a line. For example, $\begin{bmatrix}0\\1\\1\end{bmatrix}$ is on $Q$ but cannot be an output of $F_4$ .
The second column of $F_5$ is itself a possible output, but it is not on $Q$ : $2(0)-2+1\ne0$ .

Having all columns on a plane is necessary for that plane to be the column space, but it is not sufficient. The columns must produce every vector on the plane.