Thursday, October 6, 2011

Game Description: Matrix-Game-That-Needs-A-Name

Games are fun and linear algebra is fun. Let's put them together! It's especially fun to try to determine whether a matrix is invertible. Here's a game that revolves around invertibility (it still needs a name).

The game begins with an invertible matrix of non-negative integers. Each turn ends with a player reducing one of the entries of the matrix, so that it is still a non-negative integer. If the resulting matrix is non-invertible, that is a losing move. Depending on how cutthroat you want to play, it might be up to the other player to notice you created a non-invertible matrix at the beginning of their turn.

I've played with my matrix algorithms class a few time|s this semester, using this as the starting position:

| 1 2 |
| 3 4 |

This position is in Fuzzy. What's the winning move?


  1. For a name, how about Determinater?

    I don't see the winning move (although I didn't draw out the game tree). It looks like it is in P to me.

  2. Determinater! That's beautiful! :)

    Uhoh! You think it's in P! :-\ I certainly have a move **I think** puts the game in P. It's not good news to be on the opposite side of the fence as Neil McKay!

    I'm not ready to give my move away yet, though. Any other thoughts?