2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.