16
$\begingroup$

Players $A$ and $B$ take an empty $n \times n$ matrix 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.

For a given $n > 0$, is there 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 > 3$ is odd?

$\endgroup$
7
  • $\begingroup$ sounds like a very nice question. $\endgroup$
    – Suvrit
    Commented Nov 11, 2010 at 10:27
  • 3
    $\begingroup$ See the discussion at mathoverflow.net/questions/2193/variation-on-a-matrix-game . $\endgroup$ Commented Nov 11, 2010 at 10:52
  • $\begingroup$ This is just the opposite goal than in mathoverflow.net/questions/2193 $\endgroup$ Commented Nov 11, 2010 at 12:12
  • 1
    $\begingroup$ Are you sure that there is a winning strategy for A if $n$ is odd? w.l.o.g. A plays a 1 in position (1,1). If B then plays a 0 in (2,2) it looks as of B can either create a row/column of 0s or a 2x2 submatrix of 0s no matter what A plays. $\endgroup$
    – Ben
    Commented Nov 11, 2010 at 15:50
  • 1
    $\begingroup$ True, but in the case of the 3x3, a 2x2 submatrix of zeros guarantees the determinant is zero, and I think that's what he meant. $\endgroup$ Commented Nov 11, 2010 at 23:00

1 Answer 1

3
$\begingroup$

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:

  1. a 1x5, 2x4, 3x3, 4x2, or 5x1 matrix of 0s
  2. a 2x5, 3x4, 4x3, or 5x2 matrix whose rows are all scalar multiples of each other
  3. a 3x5, 4x4, or 5x3 matrix with no more than two linearly independent rows
  4. a 4x5 or 5x4 matrix with no more than three linearly independent rows
  5. 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.

$\endgroup$
6
  • $\begingroup$ Is $r+s=n-p$ right? All your examples have $r+s\gt n$. $\endgroup$ Commented Nov 11, 2010 at 22:30
  • $\begingroup$ I'm looking at the review of the Hartfiel-Loewy paper, MR 86a:15009, written by B N Moyls. The meaty part is that if $\det A=0$ then there's an $r$-by-$s$ submatrix with $r+s=n+p$ of rank at most $p-1$. The review says the converse is also true. But there's also some hoopla about independent indeterminates each appearing exactly once, truly marvelous but too long to fit into this comment box. $\endgroup$ Commented Nov 11, 2010 at 22:39
  • $\begingroup$ Thanks; I didn't catch that mistake in my read-through. The article's abstract mentions that it's n + p, so I mistyped it. $\endgroup$ Commented Nov 11, 2010 at 22:59
  • 1
    $\begingroup$ Those who do not wish to pay for the Hartfiel-Loewy paper may see Brualdi, Huang, and Zhan, Singular, nonsingular, and bounded rank completions of ACI-matrices, freely available at math.ecnu.edu.cn/~zhan/papers/BHZ_Final.pdf wherein the Hartfiel-Loewy result comes as Corollary 8 on page 11. No application to our matrix game is given. $\endgroup$ Commented Nov 11, 2010 at 23:16
  • $\begingroup$ Thank you for these usefull insights. I was wrong for $n=3$. $\endgroup$
    – Anonymous
    Commented Nov 12, 2010 at 16:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .