Diagonal plus low-rank decomposition of symmetric matrices

Question

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$.

Answer 1

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.