Playing an (invertible) matrix game with two players - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:25:46Z http://mathoverflow.net/feeds/question/45672 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45672/playing-an-invertible-matrix-game-with-two-players Playing an (invertible) matrix game with two players Anonymous 2010-11-11T10:04:59Z 2010-11-11T22:58:26Z <p>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? </p> <p>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? </p> http://mathoverflow.net/questions/45672/playing-an-invertible-matrix-game-with-two-players/45746#45746 Answer by Gabriel Benamy for Playing an (invertible) matrix game with two players Gabriel Benamy 2010-11-11T21:31:23Z 2010-11-11T22:58:26Z <p>Player A wins the trivial <em>n</em>=1 case by playing any non-zero number in (1,1). For all even <em>n</em>, player B wins by using symmetry a la a horizontal mirror. As Ben points out in the comments, if <em>n</em> = 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 <a href="http://www.informaworld.com/smpp/content~db=all~content=a779099931~frm=abslink" rel="nofollow">here</a>.<p></p> <p>The abstract, at least, says that given an <em>n</em> by <em>n</em> matrix <em>A</em> of, say, rational numbers, if the determinant is zero, then <em>A</em> must contain an <em>r</em> by <em>s</em> submatrix <em>B</em> such that <em>r</em> + <em>s</em> = <em>n</em> + <em>p</em>, and rank(<em>B</em>) ≤ p - 1 (no more than <em>p</em> - 1 linearly independent rows), for some positive integer <em>p</em>. This means that if we have, say, a 5x5 matrix whose determinant is zero, then there exists a submatrix <em>B</em> in <em>A</em> such that <em>B</em> is:</p> <ol> <li>a 1x5, 2x4, 3x3, 4x2, or 5x1 matrix of 0s</li> <li>a 2x5, 3x4, 4x3, or 5x2 matrix whose rows are all scalar multiples of each other</li> <li>a 3x5, 4x4, or 5x3 matrix with no more than two linearly independent rows</li> <li>a 4x5 or 5x4 matrix with no more than three linearly independent rows</li> <li>a 5x5 matrix with no more than four linearly independent rows (duh)<br></li> </ol> <p>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.<p></p> <p>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.</p>