Application to Games

So you think Linear Algebra is boring with all these definitions and theorems? Maybe you'll change your mind after you look at these two applications.

Game 1:

The game is a grid of 5 by 5 buttons that can light up. Pressing a button will switch its light around, but it will also switch the lights of the adjacent buttons around. Each problem presents you with a certain pattern of lit buttons and to solve the puzzle you have to turn all the lights out (which is not easy because if you're not careful you will turn more lights on than off). This is the primary goal, the secondary goal is to accomplish this with as few moves (pressing a button is one move) as possible.
Try it yourself on this grid. If a box has a check mark, this means its light is off.



Click here to see an algebraic solution using vector space theory and matrix multiplication by blocks.

Game 2: The magic squares

A magic square of size n is an n by n square matrix whose entries consist of all integers between 1 and n2, with the property that the sum of the entries of each column, row, or diagonal is the same. The sum of the entries of any row, column, or diagonal, of a magic square of size n is n(n2+1)/2 (to see this, use the identity: 1+2+...+k=k(k+1)/2).
Let us start with the easy case of a two by two magic square

ab
cd


In order to have a magic square, one would have a linear system of six equations and four unknowns:

a+b=5
c+d=5
a+c=5
b+d=5
a+d=5
b+c=5


One can use the Gaussian elimination to solve that system. A simpler way is to notice that the first and the third equation give that b=c; so the last equation becomes 2b=5 which, of course, has no integer solution. So the system has no integer solutions. In other words, there are no magic squares of size 2.


Fine, let us try now a magic square of size 3:

abc
def
ghi


In this case, the sum of each row, column or diagonal must be 15. This gives the following system of equations:

a+b+c=15
d+e+f=15
g+h+i=15
a+d+g=15
b+e+h=15
c+f+i=15
a+e+i=15
c+e+g=15


Using Gaussian elimination technique would give us the following reduced form of the above system:

10000000110
01000001010
0010000-1-1-5
0001000-1-2-10
0000100005
00000101220
00100011115
0010000000


So we have two free variables h and i. Taking h=9 and i=2 would give the following solution:

816
357
492


If you think that the above 3 by 3 square is kind of hard to guess, take a look at this very, very magic square created by H. Derksen:



1 443 235 547 339 283 100 387 179 616 565 352 44 456 148 217 509 321 113 405 499 161 578 270 57
157 599 261 53 495 439 226 543 335 22 91 383 200 612 279 373 40 452 144 556 505 317 109 421 213
313 105 417 209 521 595 257 74 486 153 247 539 326 18 435 379 191 608 300 87 31 473 140 552 369
469 131 573 365 27 121 413 205 517 309 253 70 482 174 586 535 347 14 426 243 187 604 291 83 400
625 287 79 391 183 127 569 356 48 465 409 221 513 305 117 61 478 170 582 274 343 10 447 239 526
587 254 66 483 175 244 531 348 15 427 396 188 605 292 84 28 470 132 574 361 310 122 414 201 518
118 410 222 514 301 275 62 479 166 583 527 344 6 448 240 184 621 288 80 392 461 128 570 357 49
149 561 353 45 457 401 218 510 322 114 58 500 162 579 266 340 2 444 231 548 617 284 96 388 180
280 92 384 196 613 557 374 36 453 145 214 501 318 110 422 491 158 600 262 54 23 440 227 544 331
431 248 540 327 19 88 380 192 609 296 370 32 474 136 553 522 314 101 418 210 154 591 258 75 487
423 215 502 319 106 55 492 159 596 263 332 24 436 228 545 614 276 93 385 197 141 558 375 37 454
554 366 33 475 137 206 523 315 102 419 488 155 592 259 71 20 432 249 536 328 297 89 376 193 610
85 397 189 601 293 362 29 466 133 575 519 306 123 415 202 171 588 255 67 484 428 245 532 349 11
236 528 345 7 449 393 185 622 289 76 50 462 129 566 358 302 119 406 223 515 584 271 63 480 167
267 59 496 163 580 549 336 3 445 232 176 618 285 97 389 458 150 562 354 41 115 402 219 506 323
359 46 463 130 567 511 303 120 407 224 168 585 272 64 476 450 237 529 341 8 77 394 181 623 290
390 177 619 281 98 42 459 146 563 355 324 111 403 220 507 576 268 60 497 164 233 550 337 4 441
541 333 25 437 229 198 615 277 94 381 455 142 559 371 38 107 424 211 503 320 264 51 493 160 597
72 489 151 593 260 329 16 433 250 537 606 298 90 377 194 138 555 367 34 471 420 207 524 311 103
203 520 307 124 411 485 172 589 251 68 12 429 241 533 350 294 81 398 190 602 571 363 30 467 134
195 607 299 86 378 472 139 551 368 35 104 416 208 525 312 256 73 490 152 594 538 330 17 434 246
346 13 430 242 534 603 295 82 399 186 135 572 364 26 468 412 204 516 308 125 69 481 173 590 252
477 169 581 273 65 9 446 238 530 342 286 78 395 182 624 568 360 47 464 126 225 512 304 116 408
508 325 112 404 216 165 577 269 56 498 442 234 546 338 5 99 386 178 620 282 351 43 460 147 564
39 451 143 560 372 316 108 425 212 504 598 265 52 494 156 230 542 334 21 438 382 199 611 278 95


This square has the following properties: