Alice and Bob play the determinant game

Alice and Bob play the following game with an $n \times n$ matrix, where $n$ is odd. Alice fills in one of the entries of the matrix with a real number, then Bob, then Alice and so forth until the entire matrix is filled. At the end, the determinant of the matrix is taken. If it is nonzero, Alice wins; if it is zero, Bob wins. 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 approaches to solving this problem?

I tried to approach it from Leibniz formula for determinants

$$\det(A) = \sum_{\sigma \in S_n} \operatorname{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.

The problem states that $n$ is odd, ie., $n \geq 3$.

With Alice and Bob filling the determinant slots in turns, the objective is for Alice to obtain a non-zero determinant value and for Bob to obtain a zero determinant value.

So, Alice strives to get all rows and columns to be linearly independent of each other whereas Bob strives to get at least two rows or columns linearly dependent. Note that these are equivalent ways of saying: Obtain a non-zero determinant or a zero determinant respectively that correspond with Alice and Bob's game objectives.

Intuitively, it feels like the game is stacked against Alice because her criteria is more restrictive than Bob's. But, lets get a mathematical proof while simultaneously outlining Bob's winning strategy.

Since Alice starts the game, Bob gets the even numbered moves. So, Bob chooses $r = [r_0, r_1, \dots, r_{n-1}]$, a row vector of scalars and $c, c^T = [c_0, c_1, \dots, c_{n-1}]$, a column vector of scalars that he will use to create linear dependency relationship between vectors such that, $u \ne v, w \ne x$ and

$$r_u \times R_u + r_v \times R_v = \mathbf{0}$$ $$c_w \times C_w + c_x \times C_x = \mathbf{0}^T$$

where $\mathbf{0}$ is the row vector with all columns set to zero.

He doesn't fill $r, c$ immediately, but only when Alice makes the first move in a given column or row that is not necessarily the first move of the game (update: see Notes section. Bob decides the value for $r$ or $c$ in the last move in a pair of rows or columns). [We will shortly prove that Alice will be making the first move in any given column or row]. When Alice makes her move, Bob calculates the value of $r_v$ or $c_x$ based on the value that Alice has previously filled. Once the vector cell for $r, c$ is filled, he doesn't change it for the remainder of the game.

With this strategy in place, he strives to always play his moves (the even numbered moves in the game) ensuring that the linear dependence relation for the pair of rows (or columns) is maintained. The example below shows one of Bob's moves for rows $r_k, r_{k+1}$. Note that these could be any pair of rows, not necessarily consecutive ones. Also, this doesn't have to be a pair of rows, it also works with pairs of columns.

Bob never makes a move that fills the first cell in a row or column as part of his strategy. He always follows. Therefore, Alice is forced to make that move.

It would be impossible for Alice to beat this strategy because even if she chooses to fill a different row or column, she would be the first one to initiate the move for that row or column and Bob will follow this strategy there with the even numbered moves. It is easy to see that Alice always makes the odd numbered move in any row or column and Bob follows the even numbered move with his strategy of filling in the cell so that the linear dependence condition is met.

So, even though Alice gets the last move, Bob will make a winning move (in an earlier even numbered move) causing two rows or two columns to be linearly dependent causing the determinant to evaluate to zero regardless of what Alice does.

Game play for specific problem

(posed by @Misha Lavrov in comments)

The moves are numbered sequentially. Odd numbered moves are by Alice and Even numbered moves are by Bob. The 'x' and 'o' are just indicators and can be any real number filled by Alice or Bob respectively. The problem posed is for $n=5$ where Alice and Bob have made the following $4$ moves and it is Alice's turn.

Note that if Alice makes her move in any of the yellow or green cells, Bob continues with the pairing strategy described above.

The game gets interesting if Alice fills any of the blue cells. There are three possibilities:

Alice's move (type 1):

Alice fills one of the first two cells in row 5. Bob can continue the game in columns 1 and 2 and it does not matter what he or Alice fill in any of the cells in the column because Bob will need to have the last move in just one pair of rows or columns in order to win.

What happens if Alice chooses her next move outside of the first two columns? That takes us to Alice's moves - type 2 and 3.

Alice's move (type 2):

Alice can choose to fill any cell in columns $3,4$. This becomes the first cell in a pair of columns filled by Alice and Bob falls back to his following strategy.

Alice's move (type 3):

This is also similar to type 2 in that Bob uses the following strategy.

So, regardless of where Alice fills, Bob can use the following strategy to force the last move in a pair of columns or rows to be his and he can ensure that he fills the last cell in that pair with a value that ensures the pair (of rows or columns) is linearly dependent.

While the above example shows adjacent columns, Bob's strategy works for any pair of rows or columns. He ensures he always has the last move in any pair of rows or columns and hence he is guaranteed a win when he finishes any pair of rows or columns. The rest of the moves are redundant.

This is guaranteed when $n$ is odd since he always makes the second move in the game.

Short proof

In at least one pair of rows or columns Bob always makes the last move since he plays the second move in the game and each player alternates. Alice cannot avoid playing any pair of rows or columns completely because, Bob can fill a row or column in that pair with zeros and will win by default in $2n$ moves in that case.

Notes:

• I originally mentioned that Bob chooses $r_k$ and $c_x$ after the first move by Alice in row $k$ or column $x$. In fact, he doesn't have to make the decision until he fills the last cell in the row or column.