Lower bound for rank of a matrix

Question

This was asked earlier at MSE and incorporates replies from Omnomnomnom and Chappers.

Let A = (a$_{i,j}$) be an $\,$ n x n $\,$ real symmetric matrix. What can be said about lower bounds for rank(A) if the off diagonal elements are small compared to the diagonal entries?

In particular, suppose that $\,$ a$_{i,i}$ = 1 $\,$ for all 1 $\leq$ i $\leq$ n $\,$ while $\,$ a$_{i,j}$ = a$_{j,i}$ $\in$ (-1,1) for i $\neq$ j. $\,$ As a function of n, how small can the rank of A be under these conditions?

We have the following observations:

a) In the very atypical case n = 2, $\,$ A must be nonsingular (full rank).

b) For all n $\geq$ 3, however, A can be singular. For n=3 consider

A$_3$ = $\begin{pmatrix} 1&-1/2&-1/2\\ -1/2&1&-1/2\\ -1/2&-1/2&1\end{pmatrix}$ $\,$ which has rank(A$_3)$ = 2.

And if n$\geq$4, one can form the direct sum A$_3$ $\oplus$ I$_{n-3}$ .

c) The class of matrices under consideration is closed under taking tensor products. $\quad$ Since $\quad$ $\;$ rank(A$\otimes$B) = rank(A)$\cdot$rank(B), we find rank(A$_3$$^{\otimes}$$^n$) = 2$^n$ which is small when compared with its size of 3$^n$ .

d) In individual cases, it may be possible to do better than (b) and (c) above. For example, if n = 4, we have

A$_4$ = $\begin{pmatrix} 1&0&c&s\\0&1&-s &c\\c&-s&1&0\\s&c&0&1\end{pmatrix}$

which has rank(A$_4$) = 2. $\,$ Here c = cosx and s = sinx with x any angle such that (sinx)(cosx) $\neq$ 0 .

Questions:

1) With A as above, is it necessarily true that $\,$ rank(A) $\rightarrow$ $\infty$ $\,$ as n $\rightarrow$ $\infty$ ?

2) If so, is there a good lower bound for rank(A) as a function of n ?

Thanks

Answer 1

The smallest rank is $2$, for all $n$. Indeed, let $\{p_i\}\subset \mathbb{R}^2$ be any set of $n$ points on the unit circle that does not contain two antipodal points. Let $A$ be $2$-by-$n$ the matrix whose columns are $p_1,p_2,\dotsc,p_n$, and set $M=A^TA$. Then $M$ is a rank-$2$ matrix whose $ij$'th entry is $\langle p_i,p_j\rangle$. So, the diagonal is $1$ and off-diagonal entries are less than $1$ in absolute value.

It is also easy to see that no such rank-$1$ matrix exists.

Answer 2

The following lemma might be useful if you have more information about the off diagonal entries:

Let $A$ be a $n \times n$ matrix. Then the following inequality holds:

$$ \text{rank}(A)\left( \sum_{i,j} |a_{ij}|^2 \right) \ge \left( \sum_{i} a_i \right)^2. $$

So for instance, if you knew that all the off diagonal entries were bounded by $\epsilon$, then it follows that $\text{rank}(A) \ge n/(1+\epsilon(n-1))$. While it does not seem very powerful, this lemma has many applications (see here and the references within: https://konradswanepoel.wordpress.com/2014/03/04/the-rank-lemma/). There is also a way to `boost' in the example above for a range of $\epsilon$ to say that $\text{rank}(A) = \Omega(\log n)$. See Theorem 2.1 here: https://www.tau.ac.il/~nogaa/PDFS/identity1.pdf.