# Alice and Bob matrix problem.

Alice and Bob play the following game with an $n*n$ matrix, where $n$ is odd. Alice fills in one of the entries of the matrix with a real number. then Bob fills one. Then Alice and so on so forth until the entire matrix is filled. At the end the determinant of the matrix is taken. if it is nonzero Alice wins and if it is zero Bob wins. The question is to determine who wins playing perfect strategy each time.

When n is even it's easy to see why Bob wins every time. and for n equal to 3 i have brute forced it. Bob wins. But for n = 5 and above i can't see who will win on perfect strategy each time.

Any clever appraoches to solving this problem?

-
What are the strategies you found optimal for $n=3$? –  Jean-Sébastien Oct 18 '12 at 20:27
For reference, the case $n = 2008$ is a Putnam problem (guess the year). I think this generalization was discussed on MO but I can't find it. –  Qiaochu Yuan Oct 18 '12 at 20:32
i assumed that the game could be played with just 1s and 0s. by playing zeros in the corners Bob keeps forcing Alice to play specific moves, and i checked every possible permutation. each time two rows wound up the same. I saw it in a putnam training course for n = 100, again even. i've never been able to find a generalisation to odd n. –  pad Oct 18 '12 at 20:32
Note that for odd $n$, Alice has the last move. If it happens to be the lower right corner, Bob will - among others - need to win the "subgame" of the $(n-1)\times(n-1)$ top left matrix. –  Hagen von Eitzen Oct 18 '12 at 21:07
@mjqxxxx: I followed your suggestion. Here's the code. The result, up to coding errors, is that Bob can't force one of those zero patterns in the $5\times5$ game. However, he also can't force a corresponding zero pattern in the $4\times4$ game, which he can win, so this leaves open who wins the $5\times5$. –  joriki Oct 26 '12 at 4:37

We know that the determinant of a matrix A is non-zero if the rank of the matrix is the same size of the matrix. So, in this case, rank(A) is odd. So, on the last column (or first column) all Alice has to do to guarantee a win is make sure the real number cannot be written as a linear combination of the others in that column, thereby making every column independent. This in turn makes the rank(A) = n, which is to say the determinant is non-zero.

May not be the correct answer as to what you are looking for, but it is a generalized result.

-
Every real number can be written as a linear combination of any others except 0. Why does a matrix of odd order have to have odd rank? What about $$\begin {array}{c c c}1&0&0\\0&1&0\\0&0&0 \end {array}$$ –  Ross Millikan Oct 23 '12 at 22:40

Ok so Alice has the winning strategy if the dimensions are odd, and here's why.

For Alice to win, the determinant must be non-zero, which means all rows/columns must be linearly independent.

Alice makes the first move. She can go anywhere. Then Bob makes a move. For Bob to win, in the simplest case, he needs to duplicate any one of Alice's rows or columns (then they won't be linearly independent). So his ideal strategy might be to mirror her moves. All Alice has to do is make sure Bob can't duplicate one of her rows/columns, and of course she must make sure to not duplicate any herself, but assuming she is good enough at arithmetic, this is trivial (since we can use any of the infinite real numbers)

If n were even, then Bob would win, because he could mirror Alice's moves the whole way through, and no matter where she goes, he can mirror her, right to the end, forcing one of the rows/columns to be the same as another, leading to zero determinant.

If n is odd, then this strategy no longer works for Bob, because he no longer has the last move. So even if he mirrors Alice all the way through, she can ensure that none of her rows/columns are ever duplicated by taking advantage of the odd number of rows and columns, and of the fact that she goes first and last. Ultimately, then, Alice will be able to make moves that Bob can't mirror, and so she can ensure non-zero determinant.

For example, suppose Alice is filling in a row, and Bob is mirroring her with the next row. Suppose they fill in the entire row save the final element. If alice fills this element, and Bob mirrors her, she loses. But Alice now has the whole rest of the board, so she can conceivably continue to take Bob through this process of filling in rows up to the last element. If they do this right up to the last row (since n is odd, there will be a single last row), then Alice can start filling in the last row, and Bob can no longer mirror her. Since the length of a row is odd, Alice can fill in the final element of that row. Then Bob must make a move - but the only moves available are filling in the final element of the previous rows (which come in pairs since Bob mirrored Alice all the way). But then whatever Bob picks to end a row with, Alice can choose something else for the mirror row, and thus prevent the mirrored rows from ending up as duplicates, thus maintaining independence. This goes on until the end, with Alice making the last move. Thus, Alice wins.

-
Your argument would suggest that Alice should win the $n=3$ game, too, which she doesn't. One problem with your approach is that the determinant can be zero even if no pair of rows or columns is linearly dependent (for instance, you could have two rows summing to a third). –  mjqxxxx Oct 23 '12 at 23:39
also. bob cannot mirror for odd n. one can't sort the entries into pairs. –  pad Oct 24 '12 at 15:21
hm you are right about the linear independence. However I imagine that some rephrasing of my argument, with particular care taken around the 'assuming she is good enough at arithmetic' part, can still make it work. I'm not convinced Bob wins in the 3x3. He can mirror most of the way, but eventually fails, which was the thrust of my argument. –  Ethan Oct 24 '12 at 21:30
Bob wins the $3\times3$ simply by placing $0$s in a $1\times3$ or $2\times2$ block, forcing Alice's moves in tic-tac-toe style. You can play this through by hand: Place Alice's first move in the top left and Bob's in the centre, then go through the four inequivalent second moves by Alice; you can easily find a strategy for Bob that forces a zero pattern in each case. –  joriki Oct 25 '12 at 17:07

I tried to approach it from leibniz formula for determinants

$\det(A) = \sum_{\sigma \in S_n} sgn(\sigma) \prod_{i=1}^n A_{i,\sigma_i}$

There are $n!$ factorial terms in this sum. Alice will have $\frac{n^2+1}{2}$ moves whereas Bob has $\frac{n^2-1}{2}$ moves. There are $n^2$ variables (matrix entries). Each of them taken alone appear in $(n-1)!$ terms in this summation. Whenever Bob picks a zero in his first move for any entry in the matrix, $(n-1)!$ factorial terms of this go to zero. For instance, consider a $5 \times 5$ matrix. So there are 120 terms. In first move, whenever Bob makes any matrix entry zero, he zeros out 24 of this terms. In his second move, he has to pick that matrix entry which has least number of presence in the first zeroed-out 24 terms. There can be multiple such matrix entries. In face, it can be seen that there is surely another matrix entry appearing in 24 non-zero terms in the above sum. Since $n$ is odd in this case, the last chance will always be that of Alice. Because of that, one doesn't have to bother about this terms summing to zero. What Bob has to do if he has to win is that

• He has to make sure he touches at least once (in effect zeroes) each of this 120 terms. In the $n=5$ case, he has 12 chances. In this 12 chances he has to make sure that he zeros out all this 120 terms. In one sense, It means that he has to average at least 10 terms per chance of his. I looked at the $n=3$ case, bob has 4 chances there and 6 terms, he can zero out all of them in 3 moves.

• He has to make sure that Alice doesn't get hold of all the matrix entries in one single term in 120 terms, because then it will be non-zero, and since the last chance is hers, Bob won't be able to zero it out, so she will win.

As per above explanation, in the $5 \times 5$, he has to just average killing 10 terms in each chance which seems quite easy to do. I feel this method is a bit easy to generalize and many really clever people in here can do it.

EDIT----------------

In response to @Ross Milikan, I tried to look at solving $5 \times 5$ case, this is the approach. Consider $5 \times 5$ matrix with its entries filled in by the english alphabets row-wise, so that the matrix of interest is

\begin{align} \begin{bmatrix} a & b & c & d& e \\ f& g & h &i& j \\k& l& m& n& o \\ p& q& r& s& t\\ u& v& w& x& y \end{bmatrix} \end{align}

Without loss of Generality (WLOG), let Alice pick up $a$ (making any entry zero is advantageous for her). Lets say Bob picks up $b$ (again WLOG, picking up any entry is same). This helps Bob to zero out 24 terms in the total 120. Alice has to pick up one entry in this first row itself otherwise she will be in a disadvantage (since then, Bob gets to pick the 3 terms in total from the first row and gets 72 terms zeroed out). So concerning the first row, Alice picks 3 of them, Bob picks 2 of them (say $b$ and $d$), and hence he zeros out 48 terms of the total 120. Now note that next move is Bob's. Let us swap the second column and first column. This doesn't change the determinant other than its sign. Look at the modified matrix

\begin{align} \begin{bmatrix} 0 & \otimes & \otimes & 0 & \otimes \\ g & f & h &i& j \\l& k& m& n& o \\ q& p& r& s& t\\ v& u& w& x& y \end{bmatrix} \end{align}

where $0$ is put in entries Bob has modified and $\otimes$ has been put in entries modified by Alice. Now in the first column, lets say Bob gets hold of $g$ and $q$, and alice gets hold of $l$ and $v$. Again Alice has to do this and any other move will put her in a disadvantage. Bob had made 4 moves already, the next move is his and now the matrix will look like,

\begin{align} \begin{bmatrix} 0 & \otimes & \otimes & 0 & \otimes \\ 0 & f & h &i& j \\ \otimes & k & m& n& o \\ 0 & p& r& s& t\\ \otimes & u& w& x& y \end{bmatrix} \end{align}

Now we are left with the lower $4 \times 4$ matrix, Bob is left with 8 chances, and the first move is his. Compare this with $4 \times 4$ case, it looks intuitively that Bob should win.

-
Late in the game, many of the terms will already be zero. By your argument, Bob has to average 10 new zeros. It isn't obvious to me that he can do that. –  Ross Millikan Oct 30 '12 at 17:47
Did you read my comment underneath the question? If so, do you think there are any winning patterns of zeros that don't contain one of mjqxxxx's winning patterns as a subpattern? Or are you hoping that my code is buggy? :-) –  joriki Oct 30 '12 at 17:48
@joriki yes i saw your comment later only, it was minimized. Is your code in Java, I don't understand a word of it. But yes, I do think mjqxxxx's winning patterns are not the only ones. –  dineshdileep Oct 30 '12 at 18:54
@dineshdileep Those are all the configurations which force zero at each step in the Laplace expansion. I don't see how there can be others. –  EuYu Oct 30 '12 at 19:15
@dineshdileep: Yes, it's in Java. Why do you think there are further winning patterns? Do you have one in mind? –  joriki Oct 30 '12 at 23:36