§A1.1 Introduction
In this lab, let us take a break
from serious work and do something we enjoyplaying 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 preencoded 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 alreadyencoded 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 square5 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 roomsthe 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. 
§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
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:
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
R_{3} = (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 R_{5} and R_{9 }corresponding to flipping the switch in rooms R5, and R9. 

(b) Add vectors ( R_{3} + R_{5} + R_{9 }) + s_{init} 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 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
ε_{1}R_{1 }+ ε_{2}R_{2 }+_{ }ε_{3}R_{3 }+ ... + ε_{25}R_{25 }+ 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 ε_{i}R_{i} means "flip the switch in room Ri, ε_{i} times."
Since s_{init} is just the zero vector, we can rewrite our equation as:
ε_{1}R_{1 }+ ε_{2}R_{2 }+_{ }ε_{3}R_{3 }+ ... + ε_{25}R_{25 }= s_{final}
Or in matrix notation, this is just:
Rε = s_{final}
Here R is a 25 x 25 matrix given by:
R = [R_{1} R_{2} ... R_{25}]
and
ε = (ε_{1}, ε_{2}, ... , ε_{25})^{T}.
We see that solving the puzzle reduces to solving a somewhat exotic system of equationsexotic 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ε = 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:
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] 

(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 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.
x_{1} + x_{2} = 0 Remember, x_{i} are either 0 or 1, and the addition is defined as in section A1.4. 

(b) Do
the same exercise for the following system:
x_{1} + x_{3} = 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 mfile rrefmod2.m
,
you'll need to rightclick on the link below to download the
file. When you rightclick the link, the popup 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
.

Exercise
A1.8 We will perform row reduction on the augmented
matrix [R s_{final}] as follows: First enter the vector s_{final }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:
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!
Last Modified:
06/10/2009