# The minimum rank of a matrix with a given pattern of zeros

For real matrices $$A=(a_{ij})$$ and $$B=(b_{ij})$$ of the same size, I write $$A\prec B$$ if $$a_{ij}=0$$ whenever $$b_{ij}=0$$.

If $$B = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}^{\otimes10},$$ then the matrix $$A = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ -1 & 0 & 1 \end{pmatrix}^{\otimes10}$$ satisfies $$\mathrm{rk}(A)<\mathrm{rk}(B)$$ and $$I\prec A\prec B$$ (where $$I$$ is the identity matrix of order $$3^{10}$$) . Does there exist a square matrix $$C$$ of order $$3^{10}$$ such that $$\mathrm{rk}(C)<\mathrm{rk}(A)$$ and $$I\prec C\prec A$$?

As Misha Muzychuck has observed, the answer is "no": since $$\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ -1 & 0 & 1 \end{pmatrix}$$ contains a non-degenerate upper-triangular submatrix of size $$2$$, the matrix $$A$$ contains a non-degenerate upper-triangular submatrix of size $$2^{10}$$, whence $$\mathrm{rk}(C)\ge 2^{10}=\mathrm{rk}(A)$$ for any matrix $$C$$ with $$I\prec C\prec A$$.
• just curious: since ${\rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)? – Fedor Petrov Dec 22 '18 at 12:21
• @FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)\cap\{0,1\}^n\ne\{0\}$ for any set $A\subset\mathbb F_3^n$ with $|A|>2^n$ (can you?) – Seva Dec 23 '18 at 19:35
• @FedorPetrov: Interestingly, there is a huge set $A\subset\mathbb F_3^n$ (of size $|A|\ge 3^{n-1}$) and a very large subset $D_0\subset\{0,1\}$ (of size $|D_0|\gtrsim \frac13\cdot 2^n$) such that $A-A$ is disjoint from $D_0$. – Seva Dec 25 '18 at 18:06
• probably even $\frac 23 \cdot 2^n$? If $A$ lies in some hyperplane. – Fedor Petrov Dec 26 '18 at 7:27