Game theory involving matrix determinants

317 Views Asked by At

Let $n \in \Bbb N, n \gt 1$ and $X \in M_n(\Bbb R)$ a matrix whose elements are chosen by two players ($A$ and $B$) one after another, starting with $A$. The game is won by $A$ if $\det X \ne 0$ and by $B$ in the other case. 1. Show that if $n$ is even, $B$ has a winning strategy.
2. Study whether $A$ or $B$ has a winning strategy in the case that $n$ is odd.

1

There are 1 best solutions below

0
On BEST ANSWER

I'll do problem $1$ (the easier of the two).

Suppose $n$ is even.

Then $B$ can force rows $1$ and $2$ to be equal, using the following strategy . . .

Whenever $A$ places a value in row $1$, column $j$, $B$ responds by placing the same value in row $2$, column $j$.

Similarly, whenever $A$ places a value in row $2$, column $j$, $B$ responds by placing the same value in row $1$, column $j$.

If $A$ places a value somewhere other than rows $1$ or $2$, $B$ can also avoid rows $1$ and $2$. In this case, $B$ can use any value and place it in any free cell, as long as it's not in row $1$ or row $2$.

Since $n$ is even, the number of cells not in rows $1$ or $2$ is even, so $B$'s strategy is never blocked.

Thus at the end, the first two rows will be equal, so the determinant will be $0$, hence $B$ wins.

The case where $n$ is odd seems harder, and at this point, I don't have an answer, although my gut feeling is that $A$ has the advantage.