# Diagonal plus low-rank decomposition of symmetric matrices

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

• This question reminds me of one of Fazel's talks. – Rodrigo de Azevedo Oct 6 '19 at 19:01
• $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$. – Zach Teitler 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.