Solution to the puzzle "Lights".
Below you can find the solution to the puzzle. More explanation will be provided in class.

We can find a strategy for this game using systems of linear equations. To keep our system of equations managable let's first find a solution for a 3x3 board.
Sorry, your browser does not support Java
 1 2 3 4 5 6 7 8 9

How can linear equations  be applied to this game? The answer is surprisingly simple. To solve this puzzle we have to find out how many times to click at each square to get the desirable effect: all squares red. These are our unknowns .If we assign numbers for each square like in the picture below ,we can denote xi  the number of times we have to click at the square i in order to get a solution. But what equations can we write for these variables?

Let's write down the system of equations for a starting position on the board. We must get all squares red after we do all the  clicking. So the first square that was white should become red, therefore this square should change its color the odd number of times. But exactly how many times will it change the color? Well, the first square changes color if and only if we click at squares 1,2,3,4 and 7. So the first equation is:

x1+x2+x3+x4+x7=odd
From now on we write 1 instead of odd and 0 instead of even.

The second square will change its color   x1+x2+x3+x5+x8 number of times. It was red when we started and should stay red in the end. So the second equation is:
x1+x2+x3+x5+x8=0 (even)

We obtain other equations in the same way:
x1+x2+x3+x6+x9=0
x1+x4+x5+x6+x7=0
x2+x4+x5+x6+x8=0
x3+x4+x5+x6+x9=1
x1+x4+x7+x8+x9=0
x2+x5+x7+x8+x9=1
x3+x6+x7+x8+x9=0

If we solve this system of linear equations we will find the solution to the above position on the board. We can find the general solution in the same way. We denote  b1,b2... b9 the right sides of our equations. If when we started a square i was white then bi=1 , if it was red then bi=0 . We obtain the following system of equations:
x1+x2+x3+x4+x7=b1
x1+x2+x3+x5+x8=b2
x1+x2+x3+x6+x9=b3
x1+x4+x5+x6+x7=b4
x2+x4+x5+x6+x8=b5
x3+x4+x5+x6+x9=b6
x1+x4+x7+x8+x9=b7
x2+x5+x7+x8+x9=b8
x3+x6+x7+x8+x9=b9
The augmented matrix for this system is:
 1   1   1   1   0   0   1   0   0     b1   1   1   1   0   1   0   0   1   0     b2   1   1   1   0   0   1   0   0   1     b3   1   0   0   1   1   1   1   0   0     b4   0   1   0   1   1   1   0   1   0     b5  0   0   1   1   1   1   0   0   1     b6  1   0   0   1   0   0   1   1   1     b7  0   1   0   0   1   0   1   1   1     b8  0   0   1   0   0   1   1   1   1     b9 (1)
To solve the  system we can apply the Gauss-Jordan method. We should keep in mind that 1 stands for an odd and 0 for an even number . If we add two odd numbers we get an even one,  so 1+1=0 . Similarly,  bi + b = 0, since  2b is even.
 Sorry, your browser does not support Java But we can make few conclusions immediately without solving this complicated system. We know that a system of equations Ax=b has a solution for every right side b if and only if a homogeneous system of equations Ax=0 only has the trivial solution. (Theorem 1.6.4 H.Anton, Elementary Linear Algebra) .  The question about non-trivial solutions of the homogeneous system is equivalent to the following question about our game: is it possible starting from the board below to click at some squares(odd number of times) and get again all squares red. You can check that if you click at all squares in the first row and then at all squares in the second  you will obtain the original position .  Thus we found a non-trivial solutions for the homogeneous system . (You can check , if you want, that    x1=x2=x3=x4=x5=x6=1 and x7=x8=x9=0 is a solution for the homogeneous system.). It means that for some right sides the system doesn't have any solutions and therefore it is  sometimes  impossible to solve the puzzle
Now let's try to make first step in the Gauss-Jordan elimination. We ADD(!) the first row of the system (1) to the second  one. We obtain the following row:
0   0   0   1   1   0   1   1   0     b1+b2

We use the fact that 1+1=even=0. We can continue the elimination procedure ,but it will take some time .If you want to look at the whole procedure and the general solution use the following links:
Gauss -Jordan elimination for 3x3 board.
Gauss -Jordan elimination for 5x5 board.

We can also say a lot about our game if we work a little bit with our equations. Let's add the first 3 rows to obtain the following row:

1   1   1   1   1   1   1   1   1     b1+ b2+ b3

Now let's add equations 4,5 and 6, then 7,8 and 9. The result is:

1   1   1   1   1   1   1   1   1     b4+ b5+ b6
1   1   1   1   1   1   1   1   1     b7+ b8+ b9

It means that the numbers b1+ b2+ b3, b4+ b5+ b6 and b7+ b8+ b9 are all equal ( in our case this means that either they are all odd or they are all even).

We also can add equations 1,4,7 and 2,5,8 and 3,6,9. The result is :
1   1   1   1   1   1   1   1   1     b1+ b4+ b7
1   1   1   1   1   1   1   1   1     b1+ b4+ b7
1   1   1   1   1   1   1   1   1     b1+ b4+ b7
So we see that if we can find a solution for our system then the number of white squares in each row and column is odd or in each row and column is even If this condition is satisfied then we can check that   xi=bi is a solution . It means that if we click at white squares then we will get one of the solutions. Check it!

Sometimes you can find shorter solutions. Think how you could do it (Hint: use nontrivial solutions for the homogeneous system).