An Inquiry-Based Introduction to Linear Algebra and Applications

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\) or \(\R^n\) is a subspace of \(\R^n\) if

1. whenever \(\vu\) and \(\vv\) are in \(W\) it is also true that \(\vu + \vv\) is in \(W\) (that is, \(W\) is closed under addition),

2. whenever \(\vu\) is in \(W\) and \(a\) is a scalar it is also true that \(a\vu\) is in \(W\) (that is, \(W\) is closed under scalar multiplication),

3. \(\vzero\) is in \(W\text{.}\)

Given a matrix \(A\text{,}\) there are several subspaces that are connected to \(A\text{.}\) Two specific such subspaces are the null space of \(A\) and the column space of \(A\text{.}\) 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\text{?}\)” “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.

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 \vx = \vzero\text{.}\) Note that the null space of an \(m \times n\) matrix is a subset of \(\R^n\text{.}\) We saw that the null space of \(A\) is closed under addition and scalar multiplication — that is, if \(\vu\) and \(\vv\) are in \(\Nul A\) and \(a\) and \(b\) are any scalars, then \(\vu + \vv\) and \(a \vu\) are also in \(\Nul A\text{.}\) Since the zero vector is always in \(\Nul A\text{,}\) we can conclude that the null space of \(A\) is a subspace of \(\R^n\text{.}\)

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\) to \(\R^m\) by \(T(\vx) = A \vx\text{.}\) The null space of \(A\) is then the collection of vectors \(\vx\) in \(\R^n\) so that \(T(\vx) = \vzero\text{.}\) So if \(T\) is a matrix transformation from \(\R^n\) to \(\R^m\text{,}\) then the set

is a subspace of \(\R^n\) equal to the null space of \(A\text{.}\) This set is is given a special name.

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(\vx) = A \vx\) 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 \(\{\vzero\}\text{.}\) Activity 13.2 demonstrates that if the matrix \(A\) that defines the transformation \(T\) has a pivot in every column, then \(T(\vx) = \vb\) will have exactly one solution for each \(\vb\) in the range of \(T\text{.}\) So a trivial null space is enough to characterize a one-to-one matrix transformation.

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

Given an \(m \times n\) matrix \(A\text{,}\) we have seen that the matrix-vector product \(A \vx\) is a linear combination of the columns of \(A\) with weights from \(\vx\text{.}\) It follows that the equation \(A \vx = \vb\) has a solution if and only if \(\vb\) is a linear combination of the columns of \(A\text{.}\) So the span of the columns of \(A\) tells us for which vectors the equation \(A \vx = \vb\) is consistent. We give the span of the columns of a matrix \(A\) a special name.

We denote the column space of \(A\) as \(\Col A\text{.}\) Given that \(A \vx\) is a linear combination of the columns of \(A\text{,}\) we can also write the column space of an \(m \times n\) matrix \(A\) as

For the matrix transformation \(T\) defined by \(T(\vx) = A\vx\text{,}\) the set of all vectors of the form \(A \vx\) is also the range of the transformation \(T\text{.}\) So for a matrix transformation \(T\) with matrix \(A\) we have \(\Range(T) = \Col A\text{.}\)

As you saw in Activity 13.3, a matrix transformation \(T\) defined by \(T(\vx)=A\vx\) is onto if the column space of \(A\text{,}\) which consists of the image vectors under the transformation \(T\text{,}\) is equal to \(\R^m\text{.}\) In other words, we want the \(\Range(T)\) to equal \(\R^m\text{.}\)

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.

There is really nothing new here, though. Since the rows of \(A\) are the columns of \(A^{\tr}\text{,}\) it follows that \(\Row A = \Col A^{\tr}\text{.}\) So if we want to learn anything about the row space of \(A\text{,}\) we can just translate all of our questions to the column space of \(A^{\tr}\text{.}\)

Subsection Bases for \(\Nul A\) and \(\Col A\)

When confronted with a subspace of \(\R^n\text{,}\) 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.

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\text{.}\) 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\vx = \vzero\) 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\text{.}\) As we will argue next, these process always give us bases for \(\Col A\) and \(\Nul A\text{.}\)

Let \(A\) be an \(m \times n\) matrix, and let \(R\) be the reduced row echelon form of \(A\text{.}\) 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).

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

Subsection Examples

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

Subsection Summary

• The null space of an \(m \times n\) matrix \(A\) is the set of vectors \(\vx\) in \(\R^n\) so that \(A \vx = \vzero\text{.}\) In set notation

  \begin{equation*} \Nul A = \{\vx : A \vx = \vzero\}\text{.} \end{equation*}

• The column space of a matrix \(A\) is the span of the columns of \(A\text{.}\)

• A subset \(W\) of \(\R^n\) is a subspace of \(\R^n\) if

  1. \(\vu + \vv\) is in \(W\) whenever \(\vu\) and \(\vv\) are in \(W\) (when this property is satisfied we say that \(W\) is closed under addition),

  2. \(a \vu\) is in \(W\) whenever \(a\) is a scalar and \(\vu\) is in \(W\) (when this property is satisfied we say that \(W\) is closed under multiplication by scalars),

  3. \(\vzero\) is in \(W\text{.}\)

• 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\text{.}\)

• The span of any set of vectors in \(\R^n\) is a subspace of \(\R^n\text{.}\)

• The kernel of a matrix transformation \(T : \R^n \to \R^m\) is the set

  \begin{equation*} \Ker(T) = \{\vx \in \R^n : T(\vx) = \vzero\}\text{.} \end{equation*}

• The kernel of a matrix transformation \(T\) defined by \(T(\vx) = A\vx\) is the same set as \(\Nul A\text{.}\)

• The range of a matrix transformation \(T : \R^n \to \R^m\) is the set

  \begin{equation*} \Range(T) = \{T(\vx) : \vx \in \R^n\}\text{.} \end{equation*}

• The range of a matrix transformation \(T\) defined by \(T(\vx) = A\vx\) is the same set as \(\Col A\text{.}\)

• A basis for the null space of a matrix \(A\) can be found by writing the general solution to the homogeneous equation \(A \vx = \vzero\) as a linear combination of vectors whose weights are the variables corresponding to the non-pivot columns of \(A\text{.}\) The number of vectors in a basis for \(\Nul A\) is the number of non-pivot columns of \(A\text{.}\)

• The pivot columns of a matrix \(A\) form a basis for the column space of \(A\text{.}\)

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\text{.}\)

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\text{.}\)

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\text{.}\) The space of all of these Lights Out configurations is denoted as \(\Z_2^{25}\) (similar to \(\R^{25}\text{,}\) 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

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

The goal of the Lights Out game is to begin with an initial configuration \(\vc\) (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 \(\vzero\text{.}\) Some basic algebra of vector addition in \(\Z_2\) (or mod 2) will help us understand the strategy.

Start with a configuration \(\vc\text{.}\) If we press the \(i\)th square, then we obtain the new configuration \(\vc_1 = \vm_i + \vc\) (where each move \(\vm_i\) is also in \(\Z_2^{25}\)).

What we have seen is that to play the game we are really looking for scalars \(x_1\text{,}\) \(x_2\text{,}\) \(\ldots\text{,}\) \(x_{25}\) in \(\Z_2\) (in other words, either 0 or 1) so that

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

The reduced row echelon form of the matrix \(M\) (using algebra in \(\Z_2\)):

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^{\tr}\) with any column of \(A\) is \(\vzero\text{.}\) Let \(A = [a_{ij}]\) be an \(n \times n\) matrix with columns \(\va_1\text{,}\) \(\va_2\text{,}\) \(\ldots\text{,}\) \(\va_n\text{.}\) Represent the entries in the \(i\)th column as \(\va_i = [a_{1i} \ a_{2i} \ \ldots \ a_{ni}]^{\tr}\) for each \(i\) between 1 and \(n\text{.}\) Note that \(\va_i\) is also the \(i\)th row of \(A^{\tr}\text{.}\) Also, let \(\vx = [x_1 \ x_2 \ \ldots \ x_n]^{\tr}\) be a vector in \(\Nul A^{\tr}\text{.}\) Then \(A^{\tr} \vx = \vzero\text{.}\) Using the row-column method of multiplying a matrix by a vector, when we multiply the \(i\)th row of \(A^{\tr}\) with \(\vx\) we obtain

This equation is valid for each \(i\) between 1 and \(n\text{.}\) Recall that the sum in (13.3) is the scalar product of \(\va_i\) and \(\vx\) and is denoted \(\va_i \cdot \vx\text{.}\) That is,

The fact that \(\vx\) is in \(\Nul A^{\tr}\) means \(\va_i \cdot \vx = \vzero\) for every \(i\) between 1 and \(n\text{.}\) In other words, the scalar product of any vector in \(\Nul A^{\tr}\) with any column of \(A\) is \(\vzero\text{.}\) (When the scalar product of two vectors is \(\vzero\text{,}\) we call the vectors orthogonal — a fancy word for “perpendicular”.) Since scalar products are linear, we can extend this result to the following.

With Theorem 13.11 in mind we can return to our analysis of the Lights Out game, applying this result to the matrix \(M\text{.}\)

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.