Return to Question

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 may be sharp, though I cannot prove it).

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

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

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

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 may be sharp, though I cannot prove it).

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

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

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