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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

1
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

## 1 Answer

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8776810169219971, "perplexity_flag": "middle"}