4. Linear Algebra and Fun and Games

§4.1 Introduction

    In this lab, let us take a break from serious work and do something we enjoy--playing games and solving puzzles.  You will be surprised to learn that linear algebra comes in very handy in solving a puzzle you will see momentarily.  In fact, a seemingly complicated problem comes down to simply solving a system of linear equations.

§4.2 The Game

    In a kingdom far far away, the King decided that the time has come to find a husband for his princess daughter.  The King wanted to find a worthy lad for his princess, so he promised to give his daughter away to the first young (or old) man who would solve the puzzle that has stumped the best of his court mathematicians for years.  The puzzle is very simple: in a palace, there are 25 rooms arranged in a square--5 rows of rooms with 5 rooms in each row.  In every room there is a light switch which not only switches on/off the light in that room, but also switches the lights in the adjacent rooms--the room to the right, to the left, the room above and the room below.  Initially, all of the lights are turned off.  The goal is to turn the lights on in every room of the palace.

     Just below Exercise 4.1 is the picture of the King's palace.  The rooms are numbered from R1 (Room 1) to R25 (Room 25).  Go ahead and try to get a feeling for this puzzle by trying to turn all the lights on.  If you don't succeed, do not worry; we will figure out how to solve this puzzle by the end of the lab.

	Exercise 4.1
	(a)  What happens when you press the same room button twice in a row?  Does the light configuration seem to change at all?
	(b)  Now press Clear and then press R1 and R7 buttons, in that order.  Note the light configuration.  Press Clear and try pressing R7 and then R1.  Note the light configuration again.  Does it seem to matter in which order you perform the operation?  Do the same question with more buttons: clear the board and then try the following: (R12, R13 R14).  Lights in which rooms appear to be on?  Now try, (R13, R14, R12).  Compare the light configuration with the previous one.  Are they the same?  If you are still skeptical, you can try longer sequences of moves, and see if the order in which you perform them is important.
	(c)  If there is a solution to this puzzle, it consists of a certain sequence of winning moves.  Based on the results above, do you think the order in which you perform these moves is important?  In the sequence of winning moves, do you think you'll have to press the same button more than once?  Explain.

§4.3 Some Theory and Notation

    Before we can start to tackle this problem, we need to think of a mathematical model that would model the process of switching a single light on or off.  This is quite easy.  Let us denote a light in the "ON" position by 1, and the light in the "OFF" position by 0.  There are exactly two states that a light can have, either ON or OFF, so the possible states of the light are described by the two element set {0, 1}.  To describe the process of switching the light on or off, we need to introduce an addition operation on the set {0, 1}.  Here is how it works: if we turn the switch, we add 1 to the present state of the light, and if we do nothing to the switch we add 0.  We perform these additions according to the following rules:

1 + 1 = 0

1 + 0 = 1

0 + 1 = 1

0 + 0 = 0

This may seem a little strange at first, but if we think about our model, it makes perfect sense.  For example, if the light is in the "ON" state, and we flip a switch, it will change to the "OFF" state.  This explains why 1 + 1 = 0.  Think of the summand on right as the state of the light, and the summand on the left as the action we perform on the switch.  What we get on the right hand side of the equality is the new state of the light after the operation is performed.

Remark 4.1  Notice that in the above rules of addition, the order in which we add does not matter.  That is 1 + 0 = 0 + 1 = 1.  This reflects the fact that a light that is turned off initially will turn on once we pull the switch, and the light that is on will remain on if we don't do anything to the switch.

    Before we move on to our problem, let us introduce one more useful operation on the set {0, 1}.  This operation describes what happens when we flip the switch several times.  Of course, to change the state of the light we have to flip the switch at most once.  There is no need to flip the switch twice since this is the same thing as not flipping the switch at all.  Similarly flipping the switch 201 times has the same effect as flipping the switch only once.  So there are really two options: flipping the switch once, or not flipping it at all.  This is reflected in the operation of multiplication. Here is how it works:

1·1 = 1 (This means, "flipping the switch once is the same as flipping the switch")

1·0 = 0 (This means, "not flipping the switch once is the same as not flipping the switch")

0·1 = 0 (This means "flipping the switch zero times is the same as not flipping the switch")

0·0 = 0 (This means "not flipping the switch zero times is the same as not flipping the switch")

Here we think of the factor on the right as the operation on the light switch.  The factor on the left is the number of times we perform that operation.  What we get on the right hand side is the operation obtained as the result.  Note that the multiplication rules do not involve the state of the lights, they only concern the operations on the lights.

    From now on in this lab we will only work with the arithmetic of light switches.  You have to put yourself in the mode of thinking exclusively in terms of 0's and 1's, and operations defined above.

§4.4 Modeling the Puzzle

    In the previous section we were able to create a simple model that describes the state of one light and how turning the switch affects that state.  In our game, we have 25 lights to keep track of instead of one.  Surprisingly, this is not that more difficult.  The idea is to store the state of 25 lights in a column vector.  The various operations we perform translate into adding a column vector representing that operation to the vector representing the current state.  Here is how it works.  Initially, all 25 lights are turned off, so the state of the palace lights is just

s_init = (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)^T.

The state we want is when all the lights are turned on.  In our notation, this is simply:

s_final = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)^T

    Now we need to introduce notation corresponding to turning the switch on in various rooms.  There are 25 rooms, so we will have 25 possible operations, one corresponding to each room.

    For example, when we flip the switch in room R3, the lights change in rooms R2, R3, R4 and R8, so we get the following picture:

This corresponds to the following switching vector:

which we denote

R₃ = (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)^T

    We are now ready to state the puzzle in terms of linear algebra.  We are looking for a sequence of moves that will get us from s_init to s_final.  Each move is simply the addition of one of the vectors R_i to the state vector s.  Thus we are looking for numbers ε_i such that

ε₁R₁ + ε₂R₂ +  ε₃R₃ + ... + ε₂₅R₂₅ + s_init = s_final

where ε_i can be either 0 or 1 because, as we saw before, we do not need to flip the switch more than once, and the expression ε_iR_i means "flip the switch in room Ri,  ε_i times."

    Since s_init is just the zero vector, we can rewrite our equation as:

ε₁R₁ + ε₂R₂ +  ε₃R₃ + ... + ε₂₅R₂₅ = s_final

Or in matrix notation, this is just:

Rε = s_final

 Here R is a 25 x 25 matrix given by:

R = [R₁  R₂  ...  R₂₅]

and

ε = (ε₁, ε₂, ... , ε₂₅)^T.

    We see that solving the puzzle reduces to solving a somewhat exotic system of equations--exotic because all the unknowns and scalars can be just 0 or 1.  Do not worry however, because many of the techniques you've learned in your linear algebra class still apply in this situation.

§4.5 Solving the Puzzle and Marrying the Princess

     To solve the system Rε = s_final we need to perform row reduction on the augmented matrix [R s_final] using the arithmetic operations from section 4.3.  Remember that the columns of R are just the vectors R_i, so the matrix R looks like this:

where the unfilled spaces are zeros.

    Entering this matrix into MATLAB is easier than it seems. We first note that we can write this matrix in a block form as follows:

R =

where

A =

I is the 5 x 5 identity matrix, and O is just a 5 x 5 zero matrix.

	Exercise 4.4
	(a) Enter the matrices A, I and O into MATLAB as follows. >> A = [1 1 0 0 0; 1 1 1 0 0; 0 1 1 1 0; 0 0 1 1 1; 0 0 0 1 1] >> I = eye(5) >> O = zeros(5)
	(b) Now enter the matrix R as follows: >> R = [A I O O O; I A I O O; O I A I O; O O I A I; O O O I A]

    Now comes the most important part of the lab.  This is where we perform row reduction on the matrix [R s_final] and read off the solution.  However, you must keep in mind that in performing row reduction we can only use arithmetic operations defined earlier.  Consider the following:

Example 4.1:

Perform row reduction on the matrix

using arithmetic operations defined earlier:

	Exercise 4.5
	(a)  Using the example above as your guide, find the solution to the following system by performing row reduction on the coefficient matrix. x1 + x2 = 1 x2 + x3 = 0 x1 + x2 + x3 = 1 Remember, xi are either 0 or 1, and the addition is defined as in section 4.3.
	(b)  Do the same exercise for the following system: x1 + x3 = 0 x1 + x2 = 0 x2 + x3 = 0 How many solutions are there?  List them.  (If there is a free variable, remember that it can be only 0 or 1, so for every free variable there are 2 solutions!)

    The time has come to solve our puzzle.  We will be using a modified version of the "rref()" command to row reduce our matrix R.  This command is called "rrefmod2()".  Beware that this is not a standard MATLAB command, but it was created in MATLAB just for you to be able to do this assignment.  It takes in a matrix consisting of zeros and ones and it performs the function of "rref ()" using our new arithmetic.

    To get the m-file rrefmod2.m, you'll need to right-click on the link below to download the file.  When you right-click the link, the pop-up menu will give you the choice to save the link.  It will say something like "Save Target As..." or "Save Link As..."  After selecting this option, another screen will come up that asks you to specify where to save the file.  If you are on campus working on ACS computers, you must save the file to MATLAB's working directory. The path to it is shown in the "Current Directory" drop down box at the top of your MATLAB window. (Most likely it will be something like "C:\Program Files\MATLAB\R2006a\work", but double check to make sure. If you save the file to other places, MATLAB might not know that it's there.)  If you are working from home, save the file to whatever you are using as your working directory.  (Keep in mind that you work from home at your own risk.  TAs are not technical support staff and they cannot help you outside the designated times in the computer labs.)

    Right click on this link to download the file rrefmod2.m.

Note there are two free variables corresponding to ε₂₅ and ε₂₄.  Since we are free to choose their values, we can set ε₂₄ = ε₂₅ = 0. This means we won't touch the light switches in rooms R24 and R25.  Since the free variables are set to 0, the solution vector corresponding to this choice of free variables, is just the last column of the matrix X, which is:

ε = (0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0).

This means that to solve the puzzle we turn the switch in those rooms that correspond to 1 in the vector ε.  That is, starting from the initial state, we flip the switch in rooms R2, R3, R5, R7, R8, R9, R13, R14, R15, R16, R17, R19, R20, R21, R22.  Go ahead and do that on the puzzle board.

    Note that since there are 2 free variables that come out of solving our system, we must have 4 solutions corresponding to the following choices of the pair (ε₂₄, ε₂₅):

(0, 0), (1, 0), (0, 1), and (1, 1).

We can draw the solution we got (corresponding to (0, 0)) as follows:

Here 'X' marks the room where the switch needs to be flipped. 

 

Exercise 4.7  Now consider the following picture: X X       X X   X X     X X X   X X X     X X   X By clearing the puzzle board and switching the lights as shown on the picture above, verify that this picture also gives a solution to the puzzle.  Draw two more pictures, different from the two above, that correspond to solutions of the puzzle.  Are there any more solutions to this puzzle other than the 4 that you've found?

§4.6 Conclusion

    The princess may be very unhappy about marrying some fellow off the street, but despite that, we certainly see the great benefits of the machinery of linear algebra in the most unexpected of situations.  You may be surprised to find out that not every initial state of the puzzle has a sequence of moves that changes it into the desired final state (where all lights are ON).  This has to do with the fact that we have free variables and so the matrix of coefficients cannot be invertible.  If this lab has grabbed your attention, you may try to find an initial configuration of the puzzle which cannot be solved.  That would certainly make the princess happy!

Last Modified:

9/16/2008