Minors of a particular matrix?

Question

Take an $\frac{n(n-1)}2\times n$ matrix $M$ with $0/1$ entries

1. each row distinct

2. each row having two $1$s.

Take an $\frac{n(n-1)}2\times \frac{n(n-1)}2$ matrix $N$ with $0/1$ entries

1. each row distinct

2. each row having a single $1$

3. if $M$ has a row with columns $i,j$ marked as $1$ then $N$ has in the same row $(i-1)\times (n-i) + (j-i)$ column marked as $1$.

Then does only powers of $2$ occur as minors (absolute values of cofactors) of matrix $\begin{bmatrix}M&N\end{bmatrix}$ ?

$M=\begin{bmatrix} 1&1&0&0\\ 1&0&1&0\\ 1&0&0&1\\ 0&1&1&0\\ 0&1&0&1\\ 0&0&1&1 \end{bmatrix}$, $N=\begin{bmatrix} 1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&1 \end{bmatrix}$ and $\begin{bmatrix}M&N\end{bmatrix}=\begin{bmatrix} 1&1&0&0&1&0&0&0&0&0\\ 1&0&1&0&0&1&0&0&0&0\\ 1&0&0&1&0&0&1&0&0&0\\ 0&1&1&0&0&0&0&1&0&0\\ 0&1&0&1&0&0&0&0&1&0\\ 0&0&1&1&0&0&0&0&0&1 \end{bmatrix}$ is matrix example at $n=4$.

I think minor structure of $M$ is same as minor structure of $\begin{bmatrix}M&N\end{bmatrix}$ and $N$ might be disregarded.

Answer 1

As no one has attempted a solution let me at least identify what a minimal counterexample would look like. If any minor fails then one of the form $Z+Z^{-1}$ fails, where $Z$ is the permutation matrix of the cycle $(1 2 \dots n)$.

Setup Perhaps it helps to view $M$ as the vertex-edge incidence matrix of the $n$-simplex. That is the columns are indexed by the elements of $\{1,2,\dots,n\}$ and the rows by the elements of the $2$-sets $\{1,2,\dots,n\}^{(2)}$; with $m_{\{a,b\},c}=1$ if $c\in\{a,b\}$ and $0$ otherwise.

With a suitable re-ordering if the columns of $n$ we have $N=I$.

Preliminary Let us see that the minors of $(M\ I)$ are found among the minors of $M$. Consider some minor $K$. If the corresponding column choice chooses only columns of $M$ the result is trivial, so suppose that $s$ columns of $I$ are involved. By suitably renaming everything we can suppose that the first $s$ columns of $I$ are chosen. Now if the first $s$ rows of $(M\ I)$ are not all chosen we have in $K$ a column of $0$s and are done. Otherwise $K$ is of the form $\det\begin{pmatrix} A & I\\B & O\end{pmatrix}=\det B$ and we are done.

Minimal Counterexample $\mathbf{K}$ We consider only $M$ and what we intend to prove is that every $k\times k$ minor, for $k=1,\dots n$, is up to sign either $0$ or a natural power of $2$. We argue by induction, noting that all is clear for small values. If the result is false we consider the least $n$ for which there is a counterexample, and then with this $n$, the least $k$ for which there is a counterexample, the minor $K$ say.

Rows and columns of $\mathbf{K}$ If $K$ has any row (or column) of $0$s then its value is $0$ and so is no counterexample. If $K$ has any row (or column) with a single $1$ then we can expand $K$ along that row (or column) and get that $K$ is equal to a $(k-1)\times (k-1)$ minor and so is no counterexample. To summarise: each row and column of $K$ has exactly two $1$s.

The meaning of $\mathbf{K}$ By the above we can view $K$ as the incidence matrix of a graph $\Gamma$ with $k$ vertices and $k$ edges: every vertex is on two edges and every edge joins two vertices.

The structure of $\mathbf{\Gamma}$ Then $\Gamma$ must be a disjoint union of cycles. Suitable reordering the rows and columns of $K$ we see that if there is more than one cycle then the underlying matrix of $K$ must be of the form $\begin{pmatrix}A & O\\O & B\end{pmatrix}$, and then $K$ is the product of two minors of smaller dimension and so no counterexample. That is $\Gamma$ is a single cycle.

$\mathbf{k=n}$ Clearly if $k<n$ then this same structure occurs in the $(n-1)$ simplex, and so by the minimality of $n$ this is not a counterexample.

The structure of $\mathbf{K}$ We can suppose now without loss that the columns involved in $K$ are the first $k$. After a suitable permutation of the columns and labelling of the edges we can suppose that the cycle is $1- 2-3-\dots-k-1$. Let $Z$ denote the permutation matrix of $(123\dots k)$; it is the usual circulant matrix. Then our incidence matrix $K$ is just $Z+Z^{-1}$.

The determinant of $\mathbf{Z+Z^{-1}}$ The eigenvalues of $Z$ are of course $\{\zeta^j| j=0,\dots, k-1\}$ where $\zeta$ is the primitive $k$-th root of unity $e^{2\pi/k}$. $Z$ and $Z^{-1}$ simultaneously diagonalise. Hence the determinant of $K$ is $\prod_{j=0}^{k-1}(\zeta^{j}+\zeta^{-j})=2^{k}\prod_{j=0}^{k-1}\cos\frac{2\pi}{k}$.

The value of $\mathbf{\prod_{j=0}^{k-1}\cos\frac{2\pi}{k}}$ This has something to do with Chebychev polynomials, but I cannot at the moment sort it out.