About reducing the rank of a matrix by substract a diagonal matrix Given a positive definite matrix $Q\in\mathbb{R}^{n \times n}$, I want to find a diagnonal matrix $D$ such that $rank(Q-D) \leq k < n$.
I think this can be regarded as a generalization of eigenvalue problem, which is basically problem of finding a diagonal matrix $\lambda I$ such that $rank(Q-\lambda I) < n$.
Is there any theory about this problem?
 A: Your problem can be restated as follows: To a given symmetric matxix, can
you add a diagonal matrix so that the result has eigenvalue $0$ with high
multiplicity?
This belongs to the theory which is called Additive Inverse Eigenvalue Problems. See, for example this paper, which seems to treat a very similar problem:
D.Paul Phillips, Some partial inverse eigenvalue problems: recovering diagonal entries of symmetric matrices, Linear Algebra and its Applications
Volume 380, 263-270,
however the exact statement you ask does not follow from this result,
and I suppose that your problem is unsolved.
Here is a survey of such problems:
Moody T. Chu, Inverse eigenvalue problems, SIAM Rev. 
Vol. 40, No. 1, pp. 1–39.
A: You can limit the question to real symmetric matrices $A$ (with diagonal $0$ if desired). For large enough $k,$ the matrix $A+kI$ will be positive definite and you are then allowed to change all the diagonal entries.
As noted in a comment (and overlooked in my earlier answer) this $5 \times 5$ matrix (where the diagonal entries are free to be assigned) will have rank at least $4.$
$$ \left[ \begin {array}{ccccc} a&1&0&0&0\\ 1&b&1&0&0\\ 0&1&c&1&0\\ 0&0
&1&d&1\\ 0&0&0&1&e\end {array} \right] 
 $$ 
The same construction works for any $n.$
It is curious that having the freedom to chose any diagonal matrix may be no more effective than being restricted to choosing a multiple of the identity matrix. Perhaps the thing to generalize is not $\lambda I$ to $D$ but $\lambda I$ to $\lambda D$ for a given $D$. Hence:

Given  $n \times n$ matrices $Q,D$ with $D$ diagonal, consider scalars $\lambda$ such that $rank(Q-\lambda D) < n.$ Discuss the theory.

We might call $\lambda$ an  eigenvalue for $Q$ with respect to $D.$ Likewise a vector $X$ with $Qx=\lambda Dx$ (which there will then be) might be termed a $\lambda$-eigenvector for $Q$ with respect to $D.$ 
When $D$ is has all entries non-zero, $D^{-1}$ exists and we are simply looking at the eigenvalues and eigenvectors of $D^{-1}Q.$ When $D$ itself has rank $k \lt n$ one can still consider the degree $k$ polynomial $|Q-xD|$, it's roots etc. I'm not sure how it would all work out. 
