2

Let $A$ be an $n \times n$ real symmetric matrix. What can be said about lower bounds for the rank of $A$ when the off diagonal elements are small relative to those on the diagonal?

Question: In particular, suppose the diagonal elements of $A$ are all equal to 1 while all the off diagonal elements lie in the open interval $(-1,1)$. As a function of $n$, how small can the rank of $A$ be under these conditions? [Note that in the atypical case $n = 2$, $A$ must be nonsingular but that for all $n \ge 3$, $\text{rank}(A) \lt n$ is achievable.]

Chappers
  • 67,606
user2052
  • 2,427
  • 1
    Since $\operatorname{tr}{A}=n$, it's clear that the rank is at least $1$. Since $A$ is symmetric, $\operatorname{tr}{(A^2)}-(\operatorname{tr}{A})^2 = 2\sum_{j>i} a_{ij}^2+n-n^2 = 2\sum_{j>i} (a_{ij}^2-1)$, which is negative, so has rank at least $2$. I wonder if this pattern continues. – Chappers Jul 22 '17 at 21:28
  • Notably, we can always achieve rank at most $(2/3)n + 1$ with $$ \pmatrix{1&-.5&-.5\ -.5&1&-.5\ -.5&1&1\ &&&\ddots\ &&&&1&-.5&-.5\ &&&&-.5&1&-.5\ &&&&-.5&1&1} $$ (blank entries are zero) – Ben Grossmann Jul 22 '17 at 21:36
  • Also notable: if $A$ and $B$ are matrices of this form with possibly different sizes, then $A \otimes B$ (where $\otimes$ denotes the Kronecker product) is another matrix of this form with $$ \operatorname{rank}(A\otimes B) = \operatorname{rank}(A)\operatorname{rank}(B) $$ consequently, $\operatorname{rank}(A)/n$ can be made arbitrarily small for sufficiently large $n$. – Ben Grossmann Jul 22 '17 at 21:43
  • That matrix above should be $$ M = \pmatrix{1&-.5&-.5\ -.5&1&-.5\ -.5&-.5&1} $$ and the big matrix is just $I \otimes M$ – Ben Grossmann Jul 22 '17 at 21:45
  • We can get the rank down to $\lfloor n/2 \rfloor$ with matrices of the form $$ \begin{pmatrix} I_k & O^T \ O & I_m \end{pmatrix}, $$ where $O$ is part of an orthogonal matrix, which have characteristic polynomials of the form $(1-t)^{|k-m|} [(t-2)t]^{\min{m,k}} $. In particular, this gives you a $4\times4$ example of rank $2$. – Chappers Jul 26 '17 at 19:13
  • An example with rank $2$ for $n=5$ is $$ \begin{pmatrix} 1 & a & b & b & a \ a & 1 & a & b & b \ b & a & 1 & a & b \ b & b & a & 1 & a \ a & b & b & a & 1 \end{pmatrix}, $$ with $a$ and $b$ the roots of $4x^2+2x+1=0$ (roughly $-0.8$ and $0.3$). – Chappers Jul 26 '17 at 21:35
  • Nice results. The possibility of a uniform bound is intriguing. Thanks to both of you for working on it. – user2052 Aug 06 '17 at 22:01

0 Answers0