## Subtract diagonal terms from the matrix to make it negative semi-definite

I'm reading one paper and on page 36 (48 in the pdf) it says:

Let d(s, i) be the (positive) diagonal terms that need to be subtracted from the matrix to make it negative semi-definite...

Could someone explain me why it's possible and how can I get the values of these terms?

-
I think you need to tell us more about the matrix and the context. Is the matrix Hermitian and positive definite to start? – Geoff Robinson Jul 6 2011 at 15:46
The paper is master thesis on Markov Random Fields and matrix elements are potentials of the variables. here is the thesis: stat.berkeley.edu/~pradeepr/paperz/thesis.pdf – sbos Jul 6 2011 at 15:53
My quote was from page 36 (48 in the pdf). – sbos Jul 6 2011 at 15:54
This might just be my lack of expertise in this area talking, but this seems like a question much better suited for direct email with the author. – Cam McLeman Jul 6 2011 at 16:00

If $M$ is a Hermitian matrix, its eigenvalues $\lambda_j$ are all real. If you subtract $d$ from all the diagonal elements, you are changing $M$ to $M - d I$; if $d \ge \max_j \lambda_j$, all eigenvalues of $M - d I$ will be nonpositive so $M - d I$ will be negative semidefinite.
 That's nice, but what would be in more general case? – sbos Jul 6 2011 at 19:02 Ok, let M be symmetrical matrix – sbos Jul 6 2011 at 19:17 More general in what way? Perhaps subtracting $d_i$ from $M_{i,i}$ for each $i$? Then if $\min_i d_i \ge \max_j \lambda_j$, the new matrix will be negative semidefinite. – Robert Israel Jul 7 2011 at 18:11