Winning strategy in $(2n+1) \times (2n+1)$ matrix game.

Edit: A few minutes after posting this question (that I had been thinking about for about a day) I figured out the answer in the $3 \times 3$ case; see my answer below. However, the question might still be interesting in the more general $(2n+1) \times (2n+1)$ case, so I am still interested in the question more generally. Below is the original question.


Fix some field $\mathbb K$. Two players, Eloise and Abelard, play a game. They start with an empty $3 \times 3$ matrix. $$ \begin{pmatrix} * & * & * \\ * & * & * \\ * & * & * \end{pmatrix} $$ Their turns alternate: first Eloise, then Abelard, and so on. A turn consists of filling in one of the blanks in the matrix with an element of $\mathbb K$. After Eloise's first move, the matrix might look like $$ \begin{pmatrix} * & 3 & * \\ * & * & * \\ * & * & * \end{pmatrix}; $$ after Abelard's first move, it could look like $$ \begin{pmatrix} * & 3 & * \\ * & * & * \\ -5 & * & * \end{pmatrix}. $$ The game ends when the matrix is filled, so a game always lasts 9 turns. Eloise wins the game if the matrix is invertible -- that is, if its determinant is non-zero. Abelard wins if the matrix is singular -- that is, its determinant vanishes.

Clearly, since the number of turns in the game is bounded, one of the players must have a winning strategy.

My question is:

Does Eloise or Abelard have a winning strategy? Does this depend on the field $\mathbb K$, and if so, in what way?

The question is motivated by this question and answer where it is shown that if we work in a $2n \times 2n$ matrix instead, Abelard has a winning strategy: whenever Eloise plays a move in an odd row, Abelard plays the same move in the row below; and when Eloise plays a move in an even row, Abelard plays the same move in the row above. This ensures that for any $i$, rows $2i-1$ and $2i$ agree, so that the matrix is singular. Note that this strategy also works if Abelard just copies Eloise's moves on rows 1 and 2, and plays random moves (outside row 1 and 2) otherwise.

The same strategy does not work in the odd case: if Abelard tries to make rows 1 and 2 of the $3 \times 3$ matrix, Eloise can fill up row 3 first, forcing Abelard to make a move in row 1 and 2 before Eloise has. Since all even numbers are easy, and a $1 \times 1$ matrix is a trivial case, this makes the $3 \times 3$ matrix the first non-trivial case; but of course we can ask the question for a $(2n +1) \times (2n+1)$ matrix for any $n$.

I wrote a short, inefficient Python script to brute force the solution for $\mathbb K = \mathbb F_2$, and $\mathbb K = \mathbb F_3$. (It is so inefficient that $\mathbb K = \mathbb F_5$ is already a problem.) It turns out that in both these cases, Abelard has a winning strategy (assuming my script is correct), although I haven't been able to see a pattern to the results of the computation that suggest a human-understandable strategy.

For one final observation: it appears that Eloise has an advantage, getting both the first and the last turn, but it turns out that her first turn is (essentially) determined. Namely, if she plays a zero, then Abelard can beat her. Without loss of generality, suppose she played the zero in the top left. Then Abelard can add a zero next to it, and Eloise is forced to save the row from becoming all zeros: $$ \begin{pmatrix} 0 & 0 & e_1 \\ * & * & * \\ * & * & * \end{pmatrix}. $$ Then, Abelard can play a zero in the middle left, forcing Eloise to similarly save the left column from becoming all zeros: $$ \begin{pmatrix} 0 & 0 & e_1 \\ 0 & * & * \\ e_2 & * & * \end{pmatrix}. $$ But then Abelard wins by playing a 0 in the center field: $$ \det\begin{pmatrix} 0 & 0 & e_1 \\ 0 & 0 & * \\ e_2 & * & * \end{pmatrix} = 0. $$ Hence, Eloise must play a non-zero move, and by scaling the entire matrix we might as well assume she plays a 1. Thus, we can start the game as $$ \begin{pmatrix} 1 & * & * \\ * & * & * \\ * & * & * \end{pmatrix} $$ instead, letting Abelard take the first move.


Solution 1:

I actually figured out the answer myself, only a few minutes after posting, but I figured I would not delete the question as it already had a few upvotes and a favourite. The answer is,

Abelard has a winning strategy, regardless of $\mathbb K$.

To simplify, the strategy is to pull of the same "square of zeros" trick that wins him the game if Eloise starts with a 0 move. We take the version of the game where Eloise starts with a 1 in the top left corner. Then Abelard plays a 0 in the center. $$ \begin{pmatrix} 1 & * & * \\ * & 0 & * \\ * & * & * \end{pmatrix} $$ Without loss of generality (by symmetry) we can assume that Eloise's next move is either in the left column or in the bottom row. Now we distinguish a few cases.

  1. Eloise plays in a corner, so the field is $$ \begin{pmatrix} 1 & * & * \\ * & 0 & * \\ x & * & y \end{pmatrix}, $$ where $x,y$ can be an empty field or one of her values. Then Abelard can pull off his trick the same way: $$ \begin{pmatrix} 1 & 0 & * \\ * & 0 & * \\ x & * & y \end{pmatrix} \to \begin{pmatrix} 1 & 0 & * \\ * & 0 & * \\ x & e_1 & y \end{pmatrix} \to \begin{pmatrix} 1 & 0 & * \\ * & 0 & 0 \\ x & e_1 & y \end{pmatrix} \to \begin{pmatrix} 1 & 0 & * \\ e_2 & 0 & 0 \\ x & e_1 & y \end{pmatrix} \to \begin{pmatrix} 1 & 0 & 0 \\ e_2 & 0 & 0 \\ x & e_1 & y \end{pmatrix} $$
  2. Eloise plays below the 1, so the field is $$ \begin{pmatrix} 1 & * & * \\ e_1 & 0 & * \\ * & * & * \end{pmatrix}. $$ Then Abelard forces $$ \begin{pmatrix} 1 & * & * \\ e_1 & 0 & * \\ * & 0 & * \end{pmatrix}\to \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & * \\ * & 0 & * \end{pmatrix}\to \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & * \\ * & 0 & 0 \end{pmatrix}\to \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & * \\ e_3 & 0 & 0 \end{pmatrix}\to \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & 0 \\ e_3 & 0 & 0 \end{pmatrix}. $$
  3. Eloise plays below the 0. Then Abelard can do the same as in case 2 by playing zeroes in (2,3), (1,3), (1,2) respectively.

It is not obvious to me if or how this generalizes to odd numbers greater than 3.