The Null Space and Column Space of a Matrix

Section 13 The Null Space and Column Space of a Matrix

Focus Questions

By the end of this section, you should be able to give precise and thorough answers to the questions listed below. You may want to keep these questions in mind to focus your thoughts as you complete the section.

What is the null space of a matrix?
What is the column space of a matrix?
What important structure do the null space and column space of a matrix have?
What is the kernel of a matrix transformation?
How is the kernel of a matrix transformation $T$ defined by $T (x) = A x$ related to the null space of $A ?$
What is the range of a matrix transformation?
How is the range of a matrix transformation $T$ defined by $T (x) = A x$ related to the column space of $A ?$
How do we find a basis for $Nul A ?$
How do we find a basis for $Col A ?$

🔗

Subsection Application: The Lights Out Game

🔗

Lights Out (LO) is a commercial game released by Tiger Toys in 1995 (later bought out by Hasbro). The game consists of a

5 \times 5

grid in which each square is either lit or unlit. Pressing a square changes the status of the square itself and all the squares to the left, right, up, or down. The player's job is to turn all the lights out. You can play a sample game at geogebra.org/m/wcmctahp. There is a method to solve any solvable Lights Out game that can be uncovered through linear algebra that we will uncover later in this section. Column spaces and null spaces play important roles in this method.

🔗

Subsection Introduction

🔗

Recall that a subspace of

R^{n}

is a subset of

R^{n}

which is a vector space in itself. More specifically, a subset

W

R^{n}

is a subspace of

R^{n}

whenever $u$ and $v$ are in $W$ it is also true that $u + v$ is in $W$ (that is, $W$ is closed under addition),
whenever $u$ is in $W$ and $a$ is a scalar it is also true that $a u$ is in $W$ (that is, $W$ is closed under scalar multiplication),
$0$ is in $W .$

🔗

Given a matrix

A,

there are several subspaces that are connected to

A .

Two specific such subspaces are the null space of

A

and the column space of

A .

We will see that these subspaces provide answers to the big questions we have been considering since the beginning of the semester, such as “Do columns of

A

span

R^{m} ?

” “Are the columns of

A

linearly independent?” “Is the transformation

T

defined by matrix multiplication by

A

one-to-one?” “Is the transformation

T

onto?”

🔗

In this preview activity, we start examining the null space.

🔗

Preview Activity 13.1.

🔗

(a)

Let $A = [\begin{array}{ccc} 2 & 1 & 3 \\ 1 & 1 & 4 \end{array}] .$

🔗

(i)

Find the general solution to the homogeneous equation $A x = 0 .$ Write your solutions in parametric vector form. (Recall that the parametric vector form expresses the solutions to an equation as linear combinations of vectors with free variables as the weights. An example would be $x_{3} [\begin{array}{r} 1 \\ 0 \\ - 1 \\ 0 \end{array}] + x_{4} [\begin{array}{r} - 2 \\ 1 \\ 0 \\ 1 \end{array}] .$ )

🔗

(ii)

Find two specific solutions $x_{1}$ and $x_{2}$ to the homogeneous equation $A x = 0 .$ Is $x_{1} + x_{2}$ a solution to $A x = 0 ?$ Explain.

🔗

(iii)

Is $3 x_{1}$ a solution to $A x = 0 ?$ Explain.

🔗

(iv)

Is $0$ a solution to $A x = 0 ?$

🔗

(v)

What does the above seem to indicate about the set of solutions to the homogeneous system $A x = 0 ?$

🔗

(b)

Let $A$ be an $m \times n$ matrix. As problem 1 implies, the set of solutions to a homogeneous matrix-vector equation $A x = 0$ appears to be a subspace. We give a special name to this set.

🔗

Definition 13.1.

The null space of an $m \times n$ matrix $A$ is the set of all solutions to $A x = 0 .$

We denote the null space of a matrix

A

Nul A .

In set notation we write

Nul A = {x : A x = 0} .

Note that since $A x = 0$ corresponds to a homogeneous system of linear equations, $Nul A$ also represents the solution set of a homogeneous system. Let $A = [\begin{array}{cccc} 2 & 1 & 3 & 0 \\ 1 & 1 & 4 & 1 \end{array}] .$ Find all vectors in $Nul A .$

🔗

(c)

So far we considered specific examples of null spaces. But what are the properties of a null space in general? Let $A$ be an arbitrary $m \times n$ matrix.

🔗

(i)

The null space of an $m \times n$ matrix is a subset of $R^{k}$ for some integer $k .$ What is $k ?$

🔗

(ii)

Now suppose $u$ and $v$ are two vectors in $Nul A .$ By definition, that means $A u = 0,$ $A v = 0 .$ Use properties of the matrix-vector product to show that $u + v$ is also in $Nul A .$

🔗

(iii)

Now suppose $u$ is a vector in $Nul A$ and $a$ is a scalar. Explain why $a u$ is also in $Nul A .$

🔗

(iv)

Explain why $Nul A$ is a subspace of $R^{n} .$

🔗

Subsection The Null Space of a Matrix and the Kernel of a Matrix Transformation

🔗

In this section we explore the null space and see how the null space of a matrix is related to the matrix transformation defined by the matrix.

🔗

Let

A

be an

m \times n

matrix. In Preview Activity 13.1 we defined the null space of a matrix

A

(see Definition 13.1) as the set of solutions to the matrix equation

A x = 0 .

Note that the null space of an

m \times n

matrix is a subset of

R^{n} .

We saw that the null space of

A

is closed under addition and scalar multiplication — that is, if

u

and

v

are in

Nul A

and

a

and

b

are any scalars, then

u + v

and

a u

are also in

Nul A .

Since the zero vector is always in

Nul A,

we can conclude that the null space of

A

is a subspace of

R^{n} .

🔗

There is a connection between the null space of a matrix and the matrix transformation it defines. Recall that any

m \times n

matrix

A

defines a matrix transformation

T

from

R^{n}

R^{m}

T (x) = A x .

The null space of

A

is then the collection of vectors

x

R^{n}

so that

T (x) = 0 .

So if

T

is a matrix transformation from

R^{n}

R^{m},

then the set

{x in R^{n} : T (x) = 0}

🔗

is a subspace of

R^{n}

equal to the null space of

A .

This set is is given a special name.

🔗

Definition 13.2.

Let $T : R^{n} \to R^{n}$ be a matrix transformation. The kernel of $T$ is the set

Ker (T) = {x \in R^{n} : T (x) = 0} .

🔗

Activity 13.2.

If $T$ is a matrix transformation defined by a matrix $A,$ then there is a convenient way to determine if $T$ is one-to-one.

🔗

(a)

Let $T$ be the matrix transformation defined by $T (x) = A x,$ where

A = [\begin{array}{ccr} 1 & 2 & - 1 \\ 0 & 1 & 4 \end{array}] .

Find all of the vectors in $Nul A .$ If $Nul A$ contains more than one vector, can $T$ be one-to-one? Why?

🔗

(b)

Let $T$ be the matrix transformation defined by $T (x) = A x,$ where

A = [\begin{array}{rc} 1 & 0 \\ 2 & 1 \\ - 1 & 4 \end{array}] .

Find all of the vectors in $Nul A .$ Is $T$ one-to-one? Why?

🔗

(c)

To find the vectors in the null space of a matrix $A$ we solve the system $A x = 0 .$ Since a homogeneous system is always consistent, there are two possibilities for $Nul A :$ either $Nul A = {0}$ or $Nul A$ contains infinitely many vectors.

🔗

(i)

Under what conditions on $A$ is $Nul A = {0} ?$ What does that mean about $T$ being one-to-one or not? Explain.

🔗

(ii)

Under what conditions is $Nul A$ infinite? What does that mean about $T$ being one-to-one or not? Explain.

🔗

(iii)

Is is possible for $Nul A$ to be the whole space $R^{n} ?$ If so, give an example. If not, explain why not.

🔗

Recall that for a function to be one-to-one, each output must come from exactly one input. Since a matrix transformation

T

defined by

T (x) = A x

always maps the zero vector to the zero vector, for

T

to be one-to-one it must be the case that the zero vector is the only vector that

T

maps to the zero vector. This means that the null space of

A

must be

{0} .

Activity 13.2 demonstrates that if the matrix

A

that defines the transformation

T

has a pivot in every column, then

T (x) = b

will have exactly one solution for each

b

in the range of

T .

So a trivial null space is enough to characterize a one-to-one matrix transformation.

🔗

Theorem 13.3.

A matrix transformation $T$ from $R^{n}$ to $R^{m}$ defined by $T (x) = A x$ is one-to-one if and only if

Nul A = Ker (T) = {0} .

🔗

Subsection The Column Space of a Matrix and the Range of a Matrix Transformation

🔗

Given an

m \times n

matrix

A,

we have seen that the matrix-vector product

A x

is a linear combination of the columns of

A

with weights from

x .

It follows that the equation

A x = b

has a solution if and only if

b

is a linear combination of the columns of

A .

So the span of the columns of

A

tells us for which vectors the equation

A x = b

is consistent. We give the span of the columns of a matrix

A

a special name.

🔗

Definition 13.4.

The column space of an $m \times n$ matrix $A$ is the span of the columns of $A .$

🔗

We denote the column space of

A

Col A .

Given that

A x

is a linear combination of the columns of

A,

we can also write the column space of an

m \times n

matrix

A

Col A = {A x : x is in R^{n}} .

🔗

For the matrix transformation

T

defined by

T (x) = A x,

the set of all vectors of the form

A x

is also the range of the transformation

T .

So for a matrix transformation

T

with matrix

A

we have

Range (T) = Col A .

🔗

Activity 13.3.

As a span of a set of vectors, we know that $Col A$ is a subspace of $R^{k}$ for an appropriate value of $k .$

🔗

(a)

Let $M = [\begin{array}{ccccr} 1 & 1 & 1 & 0 & 2 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & - 1 \\ 0 & 1 & 0 & 1 & 1 \end{array}] .$ The space $Col M$ is a subspace of $R^{k}$ for some positive integer $k .$ What is $k$ in this case?

🔗

(b)

If $A$ is an $m \times n$ matrix, then $Col A$ is a subspace of $R^{k}$ for some positive integer $k .$ What is $k$ in this case?

🔗

(c)

Recall that a matrix transformation $T$ given by $T (x) = A x$ where $A$ is an $m \times n$ matrix is onto if for every $b$ in $R^{m}$ there exists a $x$ in $R^{n}$ for which $T (x) = b .$ How does $T$ being onto relate to the $Col A ?$

🔗

As you saw in Activity 13.3, a matrix transformation

T

defined by

T (x) = A x

is onto if the column space of

A,

which consists of the image vectors under the transformation

T,

is equal to

R^{m} .

In other words, we want the

Range (T)

to equal

R^{m} .

🔗

Theorem 13.5.

A matrix transformation $T$ from $R^{n}$ to $R^{m}$ defined by $T (x) = A x$ is onto if and only if

Col A = Range (T) = R^{m} .

🔗

Subsection The Row Space of a Matrix

🔗

As you might expect, if there is a column space for a matrix then there is also a row space for a matrix. The row space is defined just as the column space as the span of the rows of a matrix.

🔗

Definition 13.6.

The row space of an $m \times n$ matrix $A$ is the span of the row of $A .$

🔗

There is really nothing new here, though. Since the rows of

A

are the columns of

A^{T},

it follows that

Row A = Col A^{T} .

So if we want to learn anything about the row space of

A,

we can just translate all of our questions to the column space of

A^{T} .

🔗

Subsection Bases for $Nul A$ and $Col A$

🔗

When confronted with a subspace of

R^{n},

we will usually want to find a minimal spanning set — a smallest spanning set — for the space. Recall that a minimal spanning set is also called a basis for the space. So a basis for a space must span that space, and to be a minimal spanning set we have seen that a basis must also be linearly independent. So to prove that a set is a basis for a subspace of

R^{n}

we need to demonstrate two things: that the set is linearly independent, and that the set spans the subspace.

🔗

Activity 13.4.

In this activity we see how to find a basis for $Col A$ and $Nul A$ for a specific matrix $A .$ Let

A = [\begin{array}{rrrrr} 1 & 1 & 1 & 0 & 2 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & - 1 \\ 0 & 1 & 0 & 1 & 1 \end{array}] .

Assume that the reduced row echelon form of $A$ is

R = [\begin{array}{rrrrr} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}] .

🔗

(a)

First we examine $Col A .$ Recall that to find a minimal spanning set of a set of vectors ${v_{1}, v_{2}, \dots, v_{k}}$ in $R^{n}$ we just select the pivot columns of the matrix $[v_{1} v_{2} \dots v_{k}] .$

🔗

(i)

Find a basis for $Col A .$

🔗

(ii)

Does $Col A$ equal $Col R ?$ Explain.

🔗

(b)

Now we look at $Nul A .$

🔗

(i)

Write the general solution to the homogeneous system $A x = 0$ in vector form.

🔗

(ii)

Find a spanning set for $Nul A .$

🔗

(iii)

Find a basis for $Nul A .$ Explain how you know you have a basis.

🔗

You should have noticed that Activity 13.4 (a) provides a process for finding a basis for

Col A

— the pivot columns of

A

form a basis for

Col A .

Similarly, Activity 13.4 (b) shows us that we can find a basis for

Nul A

by writing the general solution to the homogeneous equation

A x = 0

as a linear combination of vectors whose weights are the variables corresponding to the non-pivot columns of

A

— and these vectors form a basis for

Nul A .

As we will argue next, these process always give us bases for

Col A

and

Nul A .

🔗

Let

A

be an

m \times n

matrix, and let

R

be the reduced row echelon form of

A .

Suppose

R

has

k

non-pivot columns and

n - k

pivot columns. We can rearrange the columns so that the non-pivot columns of

R

are the last

k

columns (this just amounts to relabeling the unknowns in the system).

🔗

Basis for $Nul A$ .

🔗

Here we argue that the method described following Activity 13.4 to find a spanning set for the null space always yields a basis for the null space. First note that

Nul R = Nul A,

since the system

A x = 0

has the same solution set as

R x = 0 .

So it is enough to find a basis for

Nul R .

If every column of

R

is a pivot column, then

R x = 0

has only the trivial solution and the null space of

R

{0} .

Let us now consider the case where

R

contains non-pivot columns. If we let

x = [x_{1} x_{2} \dots x_{n}]^{T},

and if

R x = 0

then we can write

x_{1},

x_{2},

\dots,

x_{n - k}

in terms of

x_{n - k + 1},

x_{n - k + 2},

\dots,

and

x_{n} .

From these equations we can write

x

as a linear combination of some vectors

v_{1},

v_{2},

\dots,

v_{k}

with

x_{n - k + 1},

x_{n - 2 + 2},

\dots,

x_{n}

as weights. By construction, each of the vectors

v_{1},

v_{2},

\dots,

v_{k}

has a component that is 1 with the corresponding component as 0 in all the other

v_{i} .

Therefore, the vectors

v_{1},

v_{2},

\dots,

v_{k}

are linearly independent and span

Nul R

(and

Nul A

). In other words, the method we have developed to find the general solution to

A x = 0

always produces a basis for

Nul A .

🔗

Basis for $Col A$ .

🔗

Here we explain why the pivot columns of

A

form a basis for

Col A .

Recall that the product

A x

expresses a linear combination of the columns of

A

with weights from

x,

and every such linear combination is matched with a product

R x

giving a linear combination of the columns of

R

using the same weights. So if a set of columns of

R

is linearly independent (or dependent), then the set of corresponding columns in

A

is linearly independent (or dependent) and vice versa. Since each pivot column of

R

is a vector with 1 in one entry (a different entry for different pivot columns) and zeros elsewhere, the pivot columns of

R

are clearly linearly independent. It follows that the pivot columns of

A

are linearly independent. All that remains is to explain why the pivot columns of

A

span

Col A .

Let

r_{1},

r_{2},

\dots,

r_{n}

be the columns of

R

so that

R = [r_{1} r_{2} \dots r_{n}],

and let

a_{1},

a_{2},

\dots,

a_{n}

be the columns of

A

so that

A = [a_{1} a_{2} \dots a_{n}] .

Suppose

a_{i}

is a non-pivot column for

A

and

r_{i}

the corresponding non-pivot column in

R .

Each pivot column is composed of a single 1 with the rest of its entries 0. Also, if a non-pivot column contains a nonzero entry, then there is a corresponding pivot column that contains a 1 in the corresponding position. So

r_{i}

is a linear combination of

r_{1},

r_{2},

\dots,

r_{n - k}

— the pivot columns of

R .

Thus,

r_{i} = c_{1} r_{1} + c_{2} r_{2} + \dots + c_{n - k} r_{n - k}

🔗

for some scalars

c_{1},

c_{2},

\dots,

c_{n - k} .

Let

x = [c_{1} c_{2} \dots c_{n - k} 0 \dots 0 - 1 0 \dots 0]^{T},

where the

- 1

is in position

i .

Then

R x = 0

and so

A x = 0 .

Thus,

a_{i} = c_{1} a_{1} + c_{2} a_{2} + \dots + c_{n - k} a_{n - k}

🔗

and

a_{i}

is a linear combination of the pivot columns of

A .

So every non-pivot column of

A

is in the span of

A

and we conclude that the pivot columns of

A

form a basis for

Col A .

🔗

IMPORTANT POINT.

🔗

It is the pivot columns of

A

that form a basis for

Col A,

not the pivot columns of the reduced row echelon form

R

A .

In general,

Col R \neq Col A .

🔗

We can incorporate the ideas of this section to expand the Invertible Matrix Theorem.

🔗

Theorem 13.7. The Invertible Matrix Theorem.

Let $A$ be an $n \times n$ matrix. The following statements are equivalent.

The matrix $A$ is an invertible matrix.
The matrix equation $A x = 0$ has only the trivial solution.
The matrix $A$ has $n$ pivot columns.
Every row of $A$ contains a pivot.
The columns of $A$ span $R^{n} .$
The matrix $A$ is row equivalent to the identity matrix $I_{n} .$
The columns of $A$ are linearly independent.
The columns of $A$ form a basis for $R^{n} .$
The matrix transformation $T$ from $R^{n}$ to $R^{n}$ defined by $T (x) = A x$ is one-to-one.
The matrix equation $A x = b$ has exactly one solution for each vector $b$ in $R^{n} .$
The matrix transformation $T$ from $R^{n}$ to $R^{n}$ defined by $T (x) = A x$ is onto.
There is an $n \times n$ matrix $C$ so that $A C = I_{n} .$
There is an $n \times n$ matrix $D$ so that $D A = I_{n} .$
The scalar 0 is not an eigenvalue of $A .$
The matrix $A^{T}$ is invertible.
$Nul A = {0} .$
$Col A = R^{n} .$

🔗

Subsection Examples

🔗

What follows are worked examples that use the concepts from this section.

🔗

Example 13.8.

🔗

(a)

Let $A = [\begin{array}{rrrr} 1 & 0 & - 2 & 3 \\ - 2 & - 4 & 0 & - 14 \\ 1 & 3 & 1 & 9 \end{array}] .$

🔗

(i)

Find a basis for $Col A .$

Technology shows that the reduced row echelon form of $A$ is

[\begin{array}{ccrc} 1 & 0 & - 2 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{array}] .

The first two columns of $A$ are the pivot columns of $A .$ Since the pivot columns of $A$ form a basis for $Col A,$ a basis for $Col A$ is

{[\begin{array}{r} 1 \\ - 2 \\ 1 \end{array}], [\begin{array}{r} 0 \\ - 4 \\ 3 \end{array}]} .

Solution.

We use $A = [\begin{array}{rrrr} 1 & 0 & - 2 & 3 \\ - 2 & - 4 & 0 & - 14 \\ 1 & 3 & 1 & 9 \end{array}] .$

Let $v_{1} = [\begin{array}{r} 1 \\ - 2 \\ 1 \end{array}]$ and $v_{2} = [\begin{array}{r} 0 \\ - 4 \\ 3 \end{array}] .$ Since neither $v_{1}$ nor $v_{2}$ is a scalar multiple of the other, we see that $Col A$ is the span of two linearly independent vectors in $R^{3} .$ Thus, we conclude that $Col A$ is the plane in $R^{3}$ through the origin and the points $(1, - 2, 1)$ and $(0, - 4, 3) .$

🔗

(ii)

Describe $Col A$ geometrically (e.g., as a line, a plane, a union of lines, etc.) in the appropriate larger space.

Solution.

🔗

(b)

Let $B = [\begin{array}{rrr} 0 & - 2 & 1 \\ - 1 & 0 & 1 \\ 6 & - 10 & - 1 \\ 1 & - 4 & 1 \end{array}] .$

🔗

(i)

Find a basis for $Nul B .$

Solution.

We use $B = [\begin{array}{rrr} 0 & - 2 & 1 \\ - 1 & 0 & 1 \\ 6 & - 10 & - 1 \\ 1 & - 4 & 1 \end{array}] .$

Technology shows that the reduced row echelon form of $B$ is

[\begin{array}{ccr} 1 & 0 & - 1 \\ 0 & 1 & - \frac{1}{2} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}] .

To find a basis for $Nul B,$ we must solve the homogeneous equation $B x = 0 .$ If $x = [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}]$ and $B x = 0,$ the reduced row echelon form of $B$ shows that $x_{3}$ is free, $x_{2} = \frac{1}{2} x_{3},$ and $x_{1} = x_{3} .$ So

\begin{aligned} x & = [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \end{array}] \\ = [\begin{array}{c} x_{3} \\ \frac{1}{2} x_{3} \\ x_{3} \end{array}] \\ = x_{3} [\begin{array}{c} 1 \\ \frac{1}{2} 1 \\ 1 \end{array}] . \end{aligned}

Thus, a basis for $Nul B$ is

{[\begin{matrix} 2 \\ 1 \\ 2 \end{matrix}]} .

🔗

(ii)

Describe $Nul B$ geometrically (e.g., as a line, a plane, a union of lines, etc.) in the appropriate larger space.

Solution.

We use $B = [\begin{array}{rrr} 0 & - 2 & 1 \\ - 1 & 0 & 1 \\ 6 & - 10 & - 1 \\ 1 & - 4 & 1 \end{array}] .$

Since $Nul B = Span {[\begin{matrix} 2 \\ 1 \\ 2 \end{matrix}]}$ is the span of one nonzero vector in $R^{3},$ we conclude that $Nul B$ is the line in $R^{3}$ through the origin and the point $(2, 1, 2) .$

🔗

Example 13.9.

Let $A = [\begin{array}{rr} 1 & 3 \\ - 1 & 2 \\ 0 & - 2 \\ 5 & 6 \end{array}],$ and let $T$ be the matrix transformation defined by $T (x) = A x .$

🔗

(a)

What are the domain and codomain of $T ?$ Why?

Solution.

Recall that $A x$ is a linear combination of the columns of $A$ with weights from $x .$ So $A x$ is defined only when the number of components of $x$ is equal to the number of columns of $A .$ This explains why the domain of $T$ is $R^{2} .$ Also, since each output of $T$ is a linear combination of the columns of $A,$ the codomain of $T$ is $R^{4} .$

🔗

(b)

Find all vectors $x$ such that $T (x) = 0 .$ How is this set of vectors related to $Nul A ?$ Explain.

Solution.

The set of vectors $x$ such that $0 = T (x) = A x$ is the same as $Nul A .$ The reduced row echelon form of $A$ is

[\begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{array}] .

Since both columns of $A$ are pivot columns, the columns of $A$ are linearly independent. This implies that $A x = 0$ has only the trivial solution. Therefore, the only vector $x$ such that $T (x) = 0$ is the zero vector in $R^{2} .$

🔗

(c)

Is $T$ one-to-one? Explain.

Solution.

The previous part shows that $Ker (T) = {0} .$ This means that $T$ is one-to-one by Theorem 13.3.

🔗

(d)

Is $T$ onto? If yes, explain why. If no, find a basis for the range of $T .$

Solution.

Recall that the range of $T$ is the same as $Col A .$ The reduced row echelon form of $A$ has a row of zeros, so $A x = b$ is not consistent for every $b$ in $R^{4} .$ We conclude that $T$ is not onto. To find a basis for the range of $T,$ we just need to find a basis for $Col A .$ The pivot columns of $A$ form such a basis, so a basis for the range of $T$ is

{[\begin{array}{r} 1 \\ - 1 \\ 0 \\ 5 \end{array}], [\begin{array}{r} 3 \\ 2 \\ - 2 \\ 6 \end{array}]} .

🔗

Subsection Summary

The null space of an $m \times n$ matrix $A$ is the set of vectors $x$ in $R^{n}$ so that $A x = 0 .$ In set notation

$Nul A = {x : A x = 0} .$
The column space of a matrix $A$ is the span of the columns of $A .$
A subset $W$ of $R^{n}$ is a subspace of $R^{n}$ if
1. $u + v$ is in $W$ whenever $u$ and $v$ are in $W$ (when this property is satisfied we say that $W$ is closed under addition),
2. $a u$ is in $W$ whenever $a$ is a scalar and $u$ is in $W$ (when this property is satisfied we say that $W$ is closed under multiplication by scalars),
3. $0$ is in $W .$
The null space of an $m \times n$ matrix is a subspace of $R^{n}$ while the column space of $A$ is a subspace of $R^{m} .$
The span of any set of vectors in $R^{n}$ is a subspace of $R^{n} .$
The kernel of a matrix transformation $T : R^{n} \to R^{m}$ is the set

$Ker (T) = {x \in R^{n} : T (x) = 0} .$
The kernel of a matrix transformation $T$ defined by $T (x) = A x$ is the same set as $Nul A .$
The range of a matrix transformation $T : R^{n} \to R^{m}$ is the set

$Range (T) = {T (x) : x \in R^{n}} .$
The range of a matrix transformation $T$ defined by $T (x) = A x$ is the same set as $Col A .$
A basis for the null space of a matrix $A$ can be found by writing the general solution to the homogeneous equation $A x = 0$ as a linear combination of vectors whose weights are the variables corresponding to the non-pivot columns of $A .$ The number of vectors in a basis for $Nul A$ is the number of non-pivot columns of $A .$
The pivot columns of a matrix $A$ form a basis for the column space of $A .$

🔗

Exercises Exercises

🔗

1.

Find a basis for the null space and column space of the matrix

A = [\begin{array}{cccr} 1 & 2 & 3 & 4 \\ 0 & 0 & 2 & - 2 \\ 1 & 2 & 5 & 2 \end{array}] .

Of which spaces are the null and column spaces of $A$ subspaces?

🔗

2.

If the column space of $[\begin{array}{ccr} 1 & 2 & - 1 \\ 1 & 1 & 1 \\ 1 & 2 & c \end{array}]$ has basis ${[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}], [\begin{matrix} 2 \\ 1 \\ 2 \end{matrix}]},$ what must $c$ be?

🔗

3.

If the null space of $[\begin{array}{ccc} 2 & 1 & a \\ 1 & 2 & b \end{array}]$ has basis ${[\begin{array}{r} 2 \\ - 1 \\ 1 \end{array}]},$ what must $a$ and $b$ be?

🔗

4.

Find a matrix with at least four non-zero and distinct columns for which the column space has basis ${[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}], [\begin{matrix} 2 \\ 2 \\ 3 \end{matrix}]} .$

🔗

5.

Find a matrix with at least two rows whose null space has basis ${[\begin{array}{r} 1 \\ 1 \\ - 1 \end{array}]} .$

🔗

6.

Find a matrix whose column space has basis ${[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}], [\begin{matrix} 2 \\ 2 \\ 3 \end{matrix}]}$ and whose null space has basis ${[\begin{array}{r} 2 \\ 1 \\ - 1 \end{array}]} .$

🔗

7.

If possible, find a $4 \times 4$ matrix whose column space does not equal $R^{4}$ but whose null space equals ${0} .$ Explain your answer. If not possible, explain why not.

🔗

8.

Label each of the following statements as True or False. Provide justification for your response.

🔗

(a) True/False.

For a $3 \times 4$ matrix, the null space contains vectors other than the zero vector.

🔗

(b) True/False.

For a $4 \times 3$ matrix, the null space contains vectors other than the zero vector.

🔗

(c) True/False.

If Nul $A$ is not the zero subspace, then the transformation $x \mapsto A x$ is not one-to-one.

🔗

(d) True/False.

If the transformation $x \mapsto A x$ is onto where $A$ is an $m \times n$ matrix, then Col $A = R^{m} .$

🔗

(e) True/False.

For a $4 \times 3$ matrix $A,$ Col $A$ cannot equal $R^{4} .$

🔗

(f) True/False.

For a $3 \times 4$ matrix $A,$ Col $A$ cannot equal $R^{3} .$

🔗

(g) True/False.

The null space of the matrix $[\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}]$ consists of the two vectors $[- 1 0 1]^{T}$ and $[0 - 1 1]^{T} .$

🔗

(h) True/False.

A basis for the null space of the matrix $[\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}]$ consists of the two vectors $[- 1 0 1]^{T}$ and $[0 - 1 1]^{T} .$

🔗

(i) True/False.

There does not exist a matrix whose null space equals its column space.

🔗

(j) True/False.

The column space of every $4 \times 4$ matrix is $R^{4}$ and its null space is ${0} .$

🔗

Subsection Project: Solving the Lights Out Game

🔗

The Lights Out game starts with a

5 \times 5

grid on which some of the squares are lit (on) and some are not lit (off). We will call such a state a configuration. Pressing a square that is on turns it off and changes the state of all adjacent (vertically and horizontally) squares, and pressing a square that is off turns it on and changes the state of all adjacent (vertically and horizontally) squares. To model this situation, we consider the number system

Z_{2} = {0, 1}

consisting only of 0 and 1, where 0 represents the off state and 1 the on state. We can also think of 1 as the act of pressing a square and 0 as the act of not pressing — that is,

$0 + 0 = 0$ (not pressing an off square leaves it off),
$0 + 1 = 1 = 1 + 0$ (pressing an off square turns it on or not pressing a lit square leaves it lit),
$1 + 1 = 0$ (pressing a lit square turns it off).

🔗

The numbers 0 and 1 in

Z_{2}

will be the only numbers we use when playing the Lights Out game, so all of our matrix entries will be in

Z_{2}

and all of our calculations are done in

Z_{2} .

🔗

There are two ways we can view a Lights Out game.

We can view each configuration as a $5 \times 5$ matrix. In this situation, we label the entries in the grid as shown in Figure 13.10. Each entry in the grid will be assigned a 0 or 1 according to whether the light in that entry is off or on.
For our purposes a better way to visualize a Lights Out configuration is as a $25 \times 1$ vector. The components in this vector correspond to the entries in the $5 \times 5$ grid with the correspondence given by the numbering demonstrated in Figure 13.10 (for the sake of space, this array is shown in a row instead of a column). Again, each component is assigned a 0 or 1 according to whether the light for that entry is off or on. In this view, each configuration is a vector with 25 components in $Z_{2} .$

🔗
Figure 13.10. Two representations of the Lights Out game.

🔗

We will take the latter perspective and view the Lights Out game as if it is played on a

25 \times 1

board with entries in

Z_{2} .

The space of all of these Lights Out configurations is denoted as

Z_{2}^{25}

(similar to

R^{25},

but with entries in

Z_{2}

rather than

R

). Since

Z_{2}

is a field, the space

Z_{2}^{25}

is a vector space just as

R^{25}

is. This is the environment in which we will play the Lights Out game.

🔗

If we think about the game as played on a

25 \times 1

board, then pressing a square correlates to selecting one of the 25 components of a configuration vector. Each time we press a square, we make a move that changes the status of that square and all the squares vertically or horizontally adjacent to it from the

5 \times 5

board. Recalling that adding 1 to a square has the effect of changing its status (from on to off or off to on), and each move that we make in the game can be represented as a

25 \times 1

vector that is added to a configuration. For example, the move of pressing the first square is given by adding the vector

m_{1} = [1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]^{T}

🔗

to a configuration vector and the move of pressing the second square is represented by adding the vector

m_{2} = [1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]^{T} .

🔗

Project Activity 13.5.

Let $m_{i}$ be the move of pressing the $i$ th square for $i$ from 1 to 25.

🔗

(a)

Find vector representations for $m_{9}$ and $m_{22} .$

🔗

(b)

Let $M = [m_{i j}] = [m_{1} | m_{2} | \dots | m_{25}] .$ Explain why $m_{i j} = m_{j i}$ for each $i$ and $j .$ In other words, explain why $M^{T} = M .$ (Such a matrix is called a symmetric matrix.)

🔗

The goal of the Lights Out game is to begin with an initial configuration

c

(a vector in

Z_{2}^{25}

) and determine if we can apply a sequence of moves to obtain the configuration in which all the entries are 0 (or all the lights are off). The vector in

Z_{2}^{25}

of all 0s is the zero vector in

Z_{2}^{25}

and we will denote it as

0 .

Some basic algebra of vector addition in

Z_{2}

(or mod 2) will help us understand the strategy.

🔗

Start with a configuration

c .

If we press the

i

th square, then we obtain the new configuration

c_{1} = m_{i} + c

(where each move

m_{i}

is also in

Z_{2}^{25}

🔗

Project Activity 13.6.

🔗

(a)

What happens if we press the $i$ th square twice in a row? Explain in terms of the action and the game and verify using vector addition.

🔗

(b)

Explain why applying move $m_{i}$ then move $m_{j}$ is the same as applying move $m_{j},$ then $m_{i} .$

🔗

(c)

Explain how the answers to the previous two questions show that to play the game we only need to determine which buttons to press (and only once each) without worrying about the order in which the buttons are pressed.

🔗

What we have seen is that to play the game we are really looking for scalars

x_{1},

x_{2},

\dots,

x_{25}

Z_{2}

(in other words, either 0 or 1) so that

\begin{matrix} (13.1) & x_{1} m_{1} + x_{2} m_{2} + \dots + x_{25} m_{25} + c = 0 . \end{matrix}

🔗

Project Activity 13.7.

Explain why (13.1) has the equivalent matrix equation

\begin{matrix} (13.2) & M x = c, \end{matrix}

where $M = [m_{1} | m_{2} | \dots | m_{25}],$ or

M = [\begin{array}{ccccccccccccccccccccccccc} 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \end{array}] .

Explicitly identify the vector $x .$ Also, explain why $c$ is on the right side of this equation.

🔗

To solve a Lights Out game now, all we need do is determine a solution, if one exists, to the matrix equation (13.2).

🔗

Project Activity 13.8.

For this activity you may use the fact that the reduced row echelon form of the matrix $M$ (using algebra in $Z_{2}$ ) is as shown below.

🔗

(a)

Find a basis for the column space of $M .$

🔗

(b)

Explain why not every Lights Out puzzle can be solved. That is, explain why there are some initial configurations of lights on and off for which it is not possible to turn out all the lights (without turning off the game). Relate this to the column space of $M .$

🔗

The reduced row echelon form of the matrix

M

(using algebra in

Z_{2}

[\begin{array}{ccccccccccccccccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}] .

🔗

To find conditions under which a Lights Out game is not solvable, we will demonstrate that if

A

is an

n \times n

matrix, then the scalar product of any vector in

Nul A^{T}

with any column of

A

0 .

Let

A = [a_{i j}]

be an

n \times n

matrix with columns

a_{1},

a_{2},

\dots,

a_{n} .

Represent the entries in the

i

th column as

a_{i} = [a_{1 i} a_{2 i} \dots a_{n i}]^{T}

for each

i

between 1 and

n .

Note that

a_{i}

is also the

i

th row of

A^{T} .

Also, let

x = [x_{1} x_{2} \dots x_{n}]^{T}

be a vector in

Nul A^{T} .

Then

A^{T} x = 0 .

Using the row-column method of multiplying a matrix by a vector, when we multiply the

i

th row of

A^{T}

with

x

we obtain

\begin{matrix} (13.3) & a_{1 i} x_{1} + a_{2 i} x_{2} + \dots + a_{n i} x_{n} = 0 . \end{matrix}

🔗

This equation is valid for each

i

between 1 and

n .

Recall that the sum in (13.3) is the scalar product of

a_{i}

and

x

and is denoted

a_{i} \cdot x .

That is,

a_{i} \cdot x = a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{i n} x_{n} .

🔗

The fact that

x

is in

Nul A^{T}

means

a_{i} \cdot x = 0

for every

i

between 1 and

n .

In other words, the scalar product of any vector in

Nul A^{T}

with any column of

A

0 .

(When the scalar product of two vectors is

0,

we call the vectors orthogonal — a fancy word for “perpendicular”.) Since scalar products are linear, we can extend this result to the following.

🔗

Theorem 13.11.

Let $A$ be an $n \times n$ matrix. If $x$ is any vector in $Col A$ and $y$ is any vector in $Nul A^{T},$ then $x \cdot y = 0 .$

🔗

With Theorem 13.11 in mind we can return to our analysis of the Lights Out game, applying this result to the matrix

M .

🔗

Project Activity 13.9.

🔗

(a)

Find a basis for the null space of $M^{T} .$ (Recall that $M^{T} = M,$ so you can use the reduced row echelon form of $M$ (using algebra in $Z_{2}$ ) given earlier.)

🔗

(b)

Use Theorem 13.11 to show that if $c = [c_{1} c_{2} \dots c_{25}]^{T}$ is an initial Lights Out configuration that is solvable, then $c$ must be orthogonal to each of the vectors in a basis for $Nul M^{T} .$ Then show that if $c$ is a solvable initial Lights Out configuration, $c$ must satisfy

\begin{aligned} c_{2} + c_{3} + c_{4} + c_{6} + c_{8} + c_{10} + c_{11} + c_{12} & + c_{14} + c_{15} + c_{16} + c_{18} \\ + c_{20} + c_{22} + c_{23} + c_{24} = 0 \end{aligned}

and

c_{1} + c_{3} + c_{5} + c_{6} + c_{8} + c_{10} + c_{16} + c_{18} + c_{20} + c_{21} + c_{23} + c_{25} = 0 .

Be very specific in your explanation.

🔗

Project Activity 13.10.

Now that we know which Lights Out games can be solved, let $c$ be an initial configuration to a solvable Lights Out game. Explain how to find a solution to this game. Will the solution be unique? Explain.

🔗

Now that we have a strategy for solving the Lights Out game, use it to solve random puzzles at geogebra.org/m/wcmctahp, or create your own game to solve.

Section 13 The Null Space and Column Space of a Matrix

Focus Questions

Subsection Application: The Lights Out Game

Subsection Introduction

Preview Activity 13.1.

(a)

(i)

(ii)

(iii)

(iv)

(v)

(b)

Definition 13.1.

(c)

(i)

(ii)

(iii)

(iv)

Subsection The Null Space of a Matrix and the Kernel of a Matrix Transformation

Definition 13.2.

Activity 13.2.

(a)

(b)

(c)

(i)

(ii)

(iii)

Theorem 13.3.

Subsection The Column Space of a Matrix and the Range of a Matrix Transformation

Definition 13.4.

Activity 13.3.

(a)

(b)

(c)

Theorem 13.5.

Subsection The Row Space of a Matrix

Definition 13.6.

Subsection Bases for Nul Nul A and Col Col A

Activity 13.4.

(a)

(i)

(ii)

(b)

(i)

(ii)

(iii)

Basis for Nul Nul A.

Basis for Col Col A.

IMPORTANT POINT.

Theorem 13.7. The Invertible Matrix Theorem.

Subsection Examples

Example 13.8.

(a)

(i)

Solution.

(ii)

Solution.

(b)

(i)

Solution.

(ii)

Solution.

Example 13.9.

(a)

Solution.

(b)

Solution.

(c)

Solution.

(d)

Solution.

Subsection Summary

Exercises Exercises

1.

2.

3.

4.

5.

6.

7.

Subsection Bases for $Nul A$ and $Col A$

Basis for $Nul A$ .

Basis for $Col A$ .