Maximal determinant conjecture for 2-consecutive-ones matrices

A Counterexample to MathDB 337797

1. Counterexample

MathDB 337797 states the following conjecture. If $A\in\{0,1\}^{n\times n}$ has the 2-consecutive-ones property, meaning that there is a common ordering of the columns in which the ones in every row form at most two contiguous blocks, then

$$|\det A|\le 4^{n/3}.$$

Consider the following $9\times 9$ matrix:

$$A= \begin{pmatrix} 0&1&1&1&0&1&1&0&0\\ 0&0&0&1&1&1&0&1&0\\ 0&1&1&1&1&0&0&0&1\\ 1&1&1&1&0&0&0&1&0\\ 0&0&1&0&0&1&1&1&1\\ 0&0&0&1&0&0&1&1&1\\ 0&0&1&1&1&0&1&1&0\\ 1&1&0&0&1&1&1&1&0\\ 1&0&1&1&1&1&1&0&0 \end{pmatrix}.$$

This matrix has the 2-consecutive-ones property, but

$$|\det A|=68>64=4^{9/3}.$$

Therefore, $A$ is a counterexample to the conjecture stated in MathDB 337797.

2. Proof

We first verify the 2-consecutive-ones property. Keep the columns in the displayed common order, and use the closed interval $[a,b]$ to denote a contiguous block of ones from column $a$ through column $b$. The complete list of blocks in each row is as follows:

Row	Contiguous blocks of ones
1	$[2,4]$, $[6,7]$
2	$[4,6]$, $[8,8]$
3	$[2,5]$, $[9,9]$
4	$[1,4]$, $[8,8]$
5	$[3,3]$, $[6,9]$
6	$[4,4]$, $[7,9]$
7	$[3,5]$, $[7,8]$
8	$[1,2]$, $[5,8]$
9	$[1,1]$, $[3,7]$

Thus every row has exactly two contiguous blocks of ones in the same column order. Hence $A$ has the 2-consecutive-ones property.

It remains to compute the determinant exactly. Perform ordinary Gaussian elimination over $\mathbb{Q}$: in each column, choose the uppermost available nonzero entry as the pivot; interchange rows when necessary; and eliminate entries below the pivot using only operations of the form

$$R_i\longleftarrow R_i-qR_j\qquad(q\in\mathbb{Q}).$$

The five row interchanges, recorded as row positions at the time they occur, are

$$(1,4),\ (2,3),\ (3,5),\ (4,5),\ (7,8).$$

The elimination produces the upper-triangular matrix

$$U= \begin{pmatrix} 1&1&1&1&0&0&0&1&0\\ 0&1&1&1&1&0&0&0&1\\ 0&0&1&0&0&1&1&1&1\\ 0&0&0&1&1&1&0&1&0\\ 0&0&0&0&-1&1&1&0&-1\\ 0&0&0&0&0&-2&0&0&2\\ 0&0&0&0&0&0&4&2&4\\ 0&0&0&0&0&0&0&-1&-3\\ 0&0&0&0&0&0&0&0&\frac{17}{2} \end{pmatrix}.$$

Adding a multiple of one row to another does not change the determinant, whereas every row interchange reverses its sign. Since the determinant of an upper-triangular matrix is the product of its diagonal entries,

$$\det U =1\cdot1\cdot1\cdot1\cdot(-1)\cdot(-2)\cdot4\cdot(-1)\cdot\frac{17}{2} =-68.$$

There were five row interchanges, so

$$\det A=(-1)^5\det U=68.$$

For $n=9$, the conjectured upper bound is

$$4^{n/3}=4^{9/3}=4^3=64.$$

Consequently,

$$|\det A|=68>64=4^{9/3},$$

which proves that $A$ is a counterexample.