13
$\begingroup$

$\DeclareMathOperator{\rk}{rk}$

Suppose that $A$ is a square matrix of order $n$. If, for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 2$, we have $$ P(A)\circ Q(A^t) = P(1)Q(1)\, I_n \tag{$\ast$} $$ (pointwise / Hadamard / Schur product in the left-hand side), then the basic inequality $\rk(B\circ C)\le\rk(B)\rk(C)$ readily gives $\rk(A)\ge\sqrt{n}$.

Notice that the present assumption "($\ast$) holds whenever $\deg P+\deg Q\le 2$" simply means that $A_{ii}=1$ and $A_{ij}A_{ji}=0$ for all $i,j\in[1,n],\ i\ne j$.

Assuming now that ($\ast$) actually holds true for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 3$, does it follow that $\rk(A)\ge n^{2/3}$?

A down-to-earth form of this question is as follows:

Suppose that $A$ is a square matrix of order $n$ with each element on the main diagonal equal to $1$. Given that for any $1\le i,j\le n$ with $i\ne j$ and $A_{ij}\ne 0$ we have $A_{ji}=0$ and also $(A^2)_{ji}=0$, does it follow that $\rk(A)\ge n^{2/3}$?

If $\rk(A)\ge n^{2/3}$ fails to hold, what is the smallest possible rank of $A$ under the stated condition?

For an upper bound, observe that if $A$ is a tensor power of the matrix $$ \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} $$ then $\rk(A)=n^c$ with $c=\log_43\approx 0.792$. (The fact that these tensor powers satisfy the assumptions follows from the identities $(B\otimes C)\circ(D\otimes E)=(B\circ D)\otimes(C\circ E)$ and $(B\otimes C)(D\otimes E)=(BD)\otimes(CE)$.)

In case it matters, the matrices I am interested in have all their elements in the set $\{0,\pm1\}$.

Improve this question
$\endgroup$
4
  • $\begingroup$ In the down-to-earth formulation, should not we add that diagonals of $A^2$ and $A^3$ are also all-1s? $\endgroup$
    – Fedor Petrov
    Commented Mar 24, 2017 at 19:37
  • 1
    $\begingroup$ @FedorPetrov: this follows automatically; say, $(A^3)_{ii}=\sum_j A_{ij}(A^2)_{ji}=A_{ii}(A^2)_{ii}=1$. $\endgroup$
    – Seva
    Commented Mar 24, 2017 at 19:46
  • $\begingroup$ Oh, indeed. By the way, how sharp the first estimate $\sqrt{n}$ is? For $n=2$ rank can not be equal to 2, for instance. $\endgroup$
    – Fedor Petrov
    Commented Mar 24, 2017 at 20:13
  • 2
    $\begingroup$ @FedorPetrov: great question. One cannot do better than $\rk(A)\ge n^{\log_32}$, by considering the tensor powers of an appropriate matrix of order $3$. Thus, the right exponent is somewhere between $1/2$ and $\log_32\approx 0.631$. $\endgroup$
    – Seva
    Commented Mar 24, 2017 at 20:18

0

Reset to default

You must log in to answer this question.