The largest 0-1 determinant · Problem 235

s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.

Idea. Expanding along a row bounds the determinant by 3. A short case check rules out 3, and a simple matrix reaches 2.

Step 1: a bound. Expanding along the first row, $det A = a_{11} M_{11} - a_{12} M_{12} + a_{13} M_{13}$ , where each $M_{1 j}$ is a $2 \times 2$ determinant with 0-1 entries, so it is $- 1$ , $0$ or $1$ . Hence $det A \leq 3$ .

Step 2: 3 is impossible. It would need $a_{11} = a_{12} = a_{13} = 1$ and $M_{11} = 1$ , $M_{12} = - 1$ , $M_{13} = 1$ . Call the other two rows $(p, q, r)$ and $(s, t, u)$ .

$M_{11} = q u - r t = 1$ forces $q = u = 1$ and $r t = 0$ .
$M_{13} = pt - q s = 1$ with $q = 1$ forces $p = t = 1$ and $s = 0$ .
Then $r t = 0$ gives $r = 0$ , and $M_{12} = p u - r s = 1$ , not $- 1$ .

Step 3: 2 is reached. The matrix with 0 on the diagonal and 1 elsewhere has eigenvalues $2, - 1, - 1$ , so its determinant is $2$ .

So the largest determinant is 2. With entries $\pm 1$ instead, the largest $3 \times 3$ determinant is 4.