4
$\begingroup$

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$?

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ 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)? $\endgroup$ – Fedor Petrov Dec 22 '18 at 12:21
  • $\begingroup$ @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?) $\endgroup$ – Seva Dec 23 '18 at 19:35
  • 1
    $\begingroup$ I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra) $\endgroup$ – Fedor Petrov Dec 23 '18 at 20:37
  • $\begingroup$ @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$. $\endgroup$ – Seva Dec 25 '18 at 18:06
  • $\begingroup$ probably even $\frac 23 \cdot 2^n$? If $A$ lies in some hyperplane. $\endgroup$ – Fedor Petrov Dec 26 '18 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.