5
$\begingroup$

I've done my research and found a few similar questions here and on other sites, but none of them have what I'm looking for.

Lights out is a simple game that has interesting math-based solutions (info here). Using the typical rules in a 5x5 board, clicking anywhere in the grid causes the clicked spot and its 4 immediate neighbours to get flipped. But I want to implement a solution where the entire row and column get flipped. For example, in this board

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

Clicking on the point at coordinate (4, 4) will result in

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

Given a 5x5 board, I know how to solve it using Gaussian elimination when using the standard rules. I read this short pdf that explained the linear algebra theory very well and showed how a solution can be obtained by solving Ax = b, where b is the column-vector of the current board and A is the following 25x25 matrix

C I 0 0 0    where    I = identity(5) and C = 1 1 0 0 0
I C I 0 0                                     1 1 1 0 0
0 I C I 0                                     0 1 1 1 0 
0 0 I C I                                     0 0 1 1 1
0 0 0 I C                                     0 0 0 1 1

I figured out how to do Gaussian elimination in modulus 2 in order to solve the matrix equation and was able to solve 5x5 boards. I also found out that by just changing the C matrix slightly, I can easily use the same code to solve 3x3.

I'm pretty sure that in order to solve the variant that I want (entire row+column gets flipped), all I need to do is figure out the C matrix. But I tried sitting down with pencil and paper for a while and do something similar to what the PDF I linked to was doing, but I couldn't figure it out.

Does anyone know how to derive the matrix required for this?

$\endgroup$
3
  • 1
    $\begingroup$ Meta comment: what a nice community! I just joined the math exchange 20 minutes ago, and already receiving 3 upvotes :) I hope this sparks enough interest to get a solution too! $\endgroup$
    – DeanAttali
    Dec 28, 2015 at 2:15
  • $\begingroup$ "this short pdf ", the link is no longer available, could you please provide the name of that document? $\endgroup$
    – KevinKim
    Jun 23, 2016 at 3:14
  • $\begingroup$ I don't remember the name of that document... if you REALLY care, you could try looking at the URL and figuring out who the prof was who hosted it (at SFU university) and emailing him $\endgroup$
    – DeanAttali
    Jun 23, 2016 at 5:25

2 Answers 2

1
$\begingroup$

I think the matrix for your variant is this $25\times 25$ block matrix

$$A=\left(\begin{array}{ccccc}J&I&I&I&I\\ I&J&I&I&I\\I&I&J&I&I\\I&I&I&J&I\\I&I&I&I&J \end{array}\right)$$ Where $I$ is the $5\times 5$ identity matrix and $J$ is the $5\times 5$ matrix of all $1$s.

For instance the $(1,1)$ button produces a 'toggle vector' $$(1 1 1 1 1 \; 1 0 0 0 0 \;1 0 0 0 0 \; 1 0 0 0 0\; 1 0 0 0 0)^T$$ and the $(1,2)$ button produces a toggle vector $$ (1 1111 \; 01000 \;01000 \; 01000\; 01000)^T$$

Continuing, and putting these together, give the above matrix of $I$s and $J$s.

$\endgroup$
1
  • $\begingroup$ Thank you! Also, thanks for not pointing out my inability to format text nicely. I'm used to stackoverflow and I never had to format a matrix... $\endgroup$
    – DeanAttali
    Dec 28, 2015 at 2:58
1
$\begingroup$

Try some rows out, you will see that you have the same format. For example, $$x_{1,1}+x_{1,2}+x_{1,3}+x_{1,4}+x_{1,5}+x_{2,1}+x_{3,1}+x_{4,1}+x_{5,1}=b_{1,1}$$ This gives $1$'s in the first row at the position $1,2,3,4,5,6,11,16,21$. The other rows works the same way.

The only difference in the resulting matrix is that the new $C$ is $$\begin{array}&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\\\end{array}$$

The whole $25\times 25$ matrix is still as before. The same $I$ works.

$\endgroup$
1
  • $\begingroup$ I did figure out that my C is all 1s (but it was weird to me so I didn't believe myself), but couldn't figure out that the rest of the columns are all I instead of submatrices of zeros. Thanks. I wish I could accept two answers, you both answered at the same time $\endgroup$
    – DeanAttali
    Dec 28, 2015 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.