Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
sounds like a very nice question. –  Suvrit Nov 11 '10 at 10:27
3  
See the discussion at mathoverflow.net/questions/2193/variation-on-a-matrix-game . –  Qiaochu Yuan Nov 11 '10 at 10:52
    
This is just the opposite goal than in mathoverflow.net/questions/2193 –  Denis Serre Nov 11 '10 at 12:12
1  
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. –  Ben Nov 11 '10 at 15:50
1  
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. –  Gabriel Benamy Nov 11 '10 at 23:00
show 2 more comments

1 Answer 1

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.

share|improve this answer
    
Is $r+s=n-p$ right? All your examples have $r+s\gt n$. –  Gerry Myerson Nov 11 '10 at 22:30
    
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. –  Gerry Myerson Nov 11 '10 at 22:39
    
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. –  Gabriel Benamy Nov 11 '10 at 22:59
1  
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. –  Gerry Myerson Nov 11 '10 at 23:16
    
Thank you for these usefull insights. I was wrong for $n=3$. –  Anonymous Nov 12 '10 at 16:40
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.