15
$\begingroup$

This is a version of the question I asked recently, but the assumptions got now strengthened substantially.

Suppose that $A=(a_{ij})_{1\le i,j\le n}$ is a square matrix with all elements in $\{0,\pm1\}$. How small can the rank of $A$ be, given that

(1) $a_{ii}=1$ for all $i\in[1,n]$;

(2) $\ a_{ij}a_{jk}a_{ki}=0$ for all $i,j,k\in[1,n]$ unless $i=j=k$?

Incidentally, (1) and (2) imply

(3) $\ a_{ij}a_{ji}=0$ for all $i,j\in[1,n]$ unless $i=j$.

As explained in the aforementioned question, (1) and (3) alone suffice to get ${\rm rk}(A)\ge\sqrt{n}$. On the other hand, even under the stronger assumption (2) one can have ${\rm rk}(A)=n^c$ with $c=\log_43\approx0.793$.

What I would like to have is an estimate like ${\rm rk}(A)\ge n^{2/3}$.

A restatement of the problem is as follows.

Denote by $\mathsf M_n$ the set of all real square matrices of order $n$ with the elements on the main diagonal all distinct from $0$. Let's say that a matrix $A=(a_{ij})_{1\le i,j\le n}\in\mathsf M_n$ contains a permutation $\pi\in\mathcal S_n$ if $a_{i\pi(i)}\ne 0$ for all $i\in[1,n]$.

Clearly, the rank of $A$ is tightly related to the permutations contained in $A$. If $A\in\mathsf M_n$ does not contain any non-identity permutation, then $A$ has full rank. More generally, if one can destroy all non-identity permutations contained in $A$ by setting to $0$ at most $k$ of its elements, then ${\rm rk}(A)\ge n-k$. If $A$ does not contain cycles of length $2$, then ${\rm rk}(A)\ge \sqrt n$ (which is sharp, as shown by Boris Bukh).

Is it true that if $A\in\mathsf M_n$ does not contain any cycles of lengths $2$ and $3$, then indeed ${\rm rk}(A)\ge n^{2/3}$?

It would be tempting to conjecture that for any three real square matrices $A,B$, and $C$ with the property that the product $a_{ij}b_{jk}c_{ki}$ is non-zero if and only if $i=j=k$, one has $$ {\rm rk}(A)\, {\rm rk}(B)\, {\rm rk}(C) \ge n^2 $$ (where $n$ is the order of the matrices). However, Jon Noel and Peter Pach have constructed an example where the product of the ranks does not exceed $n^{3/2+o(1)}$, which is essentially best possible in view of the easy lower bound $$ {\rm rk}(A)\, {\rm rk}(B)\, {\rm rk}(C) \ge n^{3/2}. $$

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Just out of curiousity, why do you call it "triangle free"? $\endgroup$
    – Amir Sagiv
    Apr 6, 2017 at 11:15
  • 3
    $\begingroup$ @AmirSagiv Because it is the adjacency matrix of a triangle-free directed graph. $\endgroup$
    – Federico Poloni
    Apr 6, 2017 at 12:47
  • 1
    $\begingroup$ @FedericoPoloni If we have two matrices, one with (for a certain pair i,j) $a_{ij}=1,a_{ji}=0$ and one with $a_{ij}=0,a_{ji}=-1$, both describe the same directed graph, don't they? But in terms of ranks, they may have different ranks. I suppose this possibility is intended by the OP, otherwise it would be stated "all elements in $\{0,1\}$". $\endgroup$
    – Wolfgang
    Apr 6, 2017 at 15:21
  • 1
    $\begingroup$ @TonyHuynh The indices in $a_{ij}a_{jk}a_{ki}$ are cyclic. It is rather triangles which are not right ones - at least not with sides parallel to the axis - and only some of those. Try $\{i,j,k\}=\{1,2,3\}$. $\endgroup$
    – Wolfgang
    Apr 6, 2017 at 15:30
  • 2
    $\begingroup$ @Wolfgang What you write is true, but still "triangle-free" seems like the perfect name to describe this concept to me. $\endgroup$
    – Federico Poloni
    Apr 6, 2017 at 18:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.