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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
6
  • 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
    Commented Dec 22, 2018 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
    Commented Dec 23, 2018 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
    Commented Dec 23, 2018 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
    Commented Dec 25, 2018 at 18:06
  • $\begingroup$ probably even $\frac 23 \cdot 2^n$? If $A$ lies in some hyperplane. $\endgroup$
    – Fedor Petrov
    Commented Dec 26, 2018 at 7:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .