Let $r(n)$ be the smallest integer such that

All symmetric $n\times n$ matrices with non-zero real entries can be written as the sum of a diagonal matrix and a matrix of rank $r(n)$

What is $r(n)$? I can show that $$r \left( \binom{k}{2} \right) \geq \binom{k-1}{2}$$ Furthermore, I can show that $r(n)\leq n-2$ and in particular $r(3) = 1$.

  • 1
    $\begingroup$ This question reminds me of one of Fazel's talks. $\endgroup$ Oct 6 '19 at 19:01
  • $\begingroup$ $r(4) \geq 2$: For the matrix $$\begin{pmatrix} x & 1 & 1 & 1 \\ 1 & y & 1 & 2 \\ 1 & 1 & z & 1 \\ 1 & 2 & 1 & w \end{pmatrix},$$ there is no choice of diagonal entries that makes the rank $1$. $\endgroup$ Oct 7 '19 at 1:10

I am afraid that it is quite possible that the rank of any diagonal perturbation of a real symmetric $n\times n$-matrix $A$ with non-zero entries is always at least $n-2$. That is, $r(n)\geqslant n-2$, you say that also $r(n)\leqslant n-2$, thus $r(n)=n-2$.

Moreover, it may happen that the submatrix formed by the columns $3,4,\ldots,n$ and rows $1,2,\ldots,n-2$ is always non-degenerated. Namely, take $$ A_{ij}=\begin{cases}2,&\text{if}\quad |j-i|\geqslant 2 \,\,\text{and}\,\, \min(i,j)\geqslant 2\\ 1,& \text{otherwise}\end{cases} $$

Say, it is how it looks for $n=6$: $$\pmatrix{1&1&1&1&1&1\\ 1&1&1&2&2&2\\ 1&1&1&1&2&2\\ 1&2&1&1&1&2\\ 1&2&2&1&1&1\\ 1&2&2&2&1&1}.$$ The above claim follows by subtracting the $(n-1)$-st column from the $n$-th, then $(n-2)$-nd column from the $(n-1)$-st etc.


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.