Playing an (invertible) matrix game with two players

2010-11-11T10:04:59Z

Players A en B play a game. They take an empty n-by-n matrix (n > 0) and place one by one an element (say a rational number) in an unoccupied place of this matrix. Player A starts. The game ends if there is no move left. Player A wins if the matrix is invertible, player B wins if it is not. Is there, for a given n, a winning strategy for one of the two players?

It is not hard to show that for n = 3, player A can win. Also if n is even player B has a winning strategy. But what if n is odd and n > 3?

Answer by Gabriel Benamy for Playing an (invertible) matrix game with two players

2010-11-11T21:31:23Z

Player A wins the trivial n=1 case by playing any non-zero number in (1,1). For all even n, player B wins by using symmetry a la a horizontal mirror. As Ben points out in the comments, if n = 3, player B can force a win. I had a long demonstration written out, but I decided against it (if you want, I can put it in later). Anyway, as for the general case, after a little searching, I found a paper called "A determinantal version of the Frobenius - König Theorem" by D. J. Hartfiel and Raphael Loewy, which can be purchased here.

The abstract, at least, says that given an n by n matrix A of, say, rational numbers, if the determinant is zero, then A must contain an r by s submatrix B such that r + s = n + p, and rank(B) ≤ p - 1 (no more than p - 1 linearly independent rows), for some positive integer p. This means that if we have, say, a 5x5 matrix whose determinant is zero, then there exists a submatrix B in A such that B is:

a 1x5, 2x4, 3x3, 4x2, or 5x1 matrix of 0s
a 2x5, 3x4, 4x3, or 5x2 matrix whose rows are all scalar multiples of each other
a 3x5, 4x4, or 5x3 matrix with no more than two linearly independent rows
a 4x5 or 5x4 matrix with no more than three linearly independent rows
a 5x5 matrix with no more than four linearly independent rows (duh)

While it doesn't say so explicitly, I think that it's a biconditional, so if player B manages to get one of these in the matrix, then she will win. However, even if it isn't biconditional, if player A can prevent any of those forming, he will win.

Of these two, I believe it would be easier for player A to prevent any of these forming than it would be for player B to force one of these, but I haven't given that in particular a great deal of thought. I hope this is helpful.

Playing an (invertible) matrix game with two players - MathOverflow

Playing an (invertible) matrix game with two players

Answer by Gabriel Benamy for Playing an (invertible) matrix game with two players