# Appendix 1: Linear Algebra and Fun and Games

§A1.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.  But enough talk, let's get down to business.

§A1.2 Application to Encryption

In conclusion, we will present a simple method of encrypting a piece of text using matrices and its inverses.

Any text message, such as, for example, "I LOVE MY TA," can be translated into a string of numbers by agreeing that each letter will correspond to its position in the alphabet, and a blank space will correspond to the number 27.  Thus A corresponds to 1, B corresponds to 2, and M corresponds to 13.  Then the message above can be written as "9 27 12 15 22 5 27 13 25 27 20 1."  If we did this alone, our message would be quite easy to break.  Let us use our sophistication in linear algebra to try to come up with a better encoding procedure.

Let us pick some invertible 4x4 matrix C with integer coefficients. For example let

Let us enter this matrix into MATLAB

>> C = [1 1 1 1; 1 2 1 2; 1 1 1 0; 1 4 2 3]

Now to encode our numerical message we simply take the first four numbers in our string and multiply C by it.

>> C*[9;27;12;15]

This gives us the first four numbers of the encoded string:

63 105 48 186

Thus to encode the rest of the message we keep multiplying C by the next four numbers in the original array.

 Exercise A1.1  Using the matrix above, encode the word "NOON".  Note that even though in the pre-encoded numerical string the numbers representing the letter "O" are the same, once we encode the word, the numbers in the encoded message are all distinct.  Thus the naive approach of decoding the message under the assumption that each letter is represented by a unique number will fail.  Include your input and output in the final Word document.

Now we know how to encode a text message, but it is of little use to us if the party to whom we are sending it cannot decode it.  Thus we must devise a way of decoding an already-encoded message.  That is, given an encoded message we must work in reverse to find the original message.  This is done by applying the inverse of the encoding matrix to the encoded string.

Example A1.1

Let us decode the encrypted message "42 51 34 81," knowing that it was encrypted using the matrix C.

We must first find the decoding matrix.  This involves finding the inverse of C.  Type in:

>> D = inv(C)

Then simply multiply D by the column vector representing the encoded message.

>> D*[42;51;34;81]

ans =

13
1
20
8

This obviously says "MATH"

 Exercise A1.2 (a)  Explain why you think we must have an invertible matrix to do the encoding? (b)  The string "56 83 37 127 42 56 40 83 82 118 55 182 77 119 50 191 48 70 41 121" was obtained by encoding a message with the matrix C.  What does the original message say?  Include all relevant MATLAB commands with the output in your write up.

§A1.3 A 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 A1.3 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 A1.3 (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).  Note the light configuration before pressing Clear.  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.

 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R15 R16 R17 R18 R19 R20 R21 R22 R23 R24 R25

§A1.4 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 A1.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.

 Exercise A1.4  In terms of the model above, write down an equation that describes flipping the switch twice on a light that is initially in the ON state.  What is the resulting state of the light?  Is this consistent with our common sense?

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.

§A1.5 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

sinit = (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:

sfinal = (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:

 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R15 R16 R17 R18 R19 R20 R21 R22 R23 R24 R25 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

which we denote

R3 = (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

 Exercise A1.5 (a)  Write down the vectors R5 and R9 corresponding to flipping the switch in rooms R5, and R9. (b)  Add vectors ( R3 + R5 + R9 ) + sinit to see what will be the state of the lights after performing operation (R3, R5, R9) starting with all of the lights turned off.  Remember, you are using the arithmetic rules from previous section!  Do the same operations on the puzzle board and compare your results.  How do they compare?

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 sinit to sfinal.  Each move is simply the addition of one of the vectors Ri to the state vector s.  Thus we are looking for numbers εi such that

ε1R1 + ε2R2 +  ε3R3 + ... + ε25R25 + sinit = sfinal

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 εiRi means "flip the switch in room Ri,  εi times."

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

ε1R1 + ε2R2 +  ε3R3 + ... + ε25R25 = sfinal

Or in matrix notation, this is just:

Rε = sfinal

Here R is a 25 x 25 matrix given by:

R = [R1  R2  ...  R25]

and

ε = (ε1, ε2, ... , ε25)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.

§A1.6 Solving the Puzzle and Marrying the Princess

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

 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1

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 =

 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

where

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 is the 5 x 5 identity matrix, and O is just a 5 x 5 zero matrix.

 Exercise A1.6 (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 sfinal] 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 A1.2:

Perform row reduction on the matrix

 1 0 1 1 0 0 1 1 0

using arithmetic operations defined earlier:

 1 0 1 Multiply Row 1 by 1 1 0 1 Multiply Row 1 by 1 1 0 1 Swap Row 2 and Row 3 1 0 1 1 0 0 → 0 0 1 → 0 0 1 → 0 1 1 1 1 0 and add to Row 2 1 1 0 and add to Row 3 0 1 1 0 0 1

 Exercise A1.7 (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 = 0 x1 + x3 = 1 x1 + x2 + x3 = 1 Remember, xi are either 0 or 1, and the addition is defined as in section A1.4. (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.)

 Exercise A1.8  We will perform row reduction on the augmented matrix [R sfinal] as follows: First enter the vector sfinal into MATLAB: >> s = [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]   Now perform row reduction by typing in: >> X = rrefmod2([R s])

Note there are two free variables corresponding to ε25 and ε24.  Since we are free to choose their values, we can set ε24 = ε25 = 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 (ε24, ε25):

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

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

 X X X X X X X X X X X X X X X

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

Exercise A1.9  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?

§A1.7 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!