<p>Your question is too imprecise.  What does it mean to "transform a matrix"?  Are you asking whether there is an algorithm that takes as input a symmetric matrix and finds the minimal total weight that can be added to diagonal entries so as to make the new matrix positive semi-definite?  </p>

<p>If this is your question, the answer is yes, since it is an SDP.  If you restrict to adding integer values to diagonal elements ("self loops"), then I do not know the complexity of finding the minimum number of self loops needed.  </p>

<p>You might want to look into <a href="http://en.wikipedia.org/wiki/Gershgorin_circle_theorem" rel="noreferrer">Gershgorin's circle theorem</a> if you are trying to do this by hand.  </p>

CC BY-SA 3.0
2011-05-09T06:06:45.083Z
I think this theorem is very close to what I needed. thanks
N27
CC BY-SA 3.0
2014-01-08T11:00:44.970Z
One should observe that modifying the diagonal entries of the adjacency matrix by adding the terms that arise from Gershgorin's theorem amounts exactly to switching from the adjacency matrix to the so-called graph Laplacian.
Delio M.
CC BY-SA 3.0
2011-05-09T05:47:31.560Z
2011-05-09T05:47:31.560Z
Anonymous
<p>This is simple. Assume the adjacency matrix is $A$. As it is symmetric, it guarantees that $A$ can be diagonalized as $A=U\Sigma U^T$ by SVD decomposition, where $\Sigma=diag(\lambda_1,...,\lambda_n)$ is the diagonal matrix of eigenvalues. For node $i$, just add this mount of loop to it: $\text{ceiling}(|min(\lambda_i,0)|)$.</p>

CC BY-SA 3.0
2016-03-21T18:47:21.990Z
2016-03-21T18:47:21.990Z
yliueagle
<p>I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can find on which nodes to set self-loops and how many of those.</p>

CC BY-SA 3.0
2011-05-09T05:51:31.460Z
What do your mean by "transform"? One can obtain a positive semidefinite matrix by setting the diagonal entries as the nodes' degree, since it is equivalent to $N^T N$ where $N$ is the incidence matrix.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-05-09T15:14:39.303Z
If all you care about is a PSD matrix, you could always just compute the Laplacian.  It's always PSD.
Josephine Moeller
<graph-theory><matrices><spectral-graph-theory>
Making an adjacency matrix positive semidefinite
N27
# Making an adjacency matrix positive semidefinite

(Asked by: username_0 on 2011-05-09)

I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can find on which nodes to set self-loops and how many of those.

**Tags:** graph-theory, matrices, spectral-graph-theory
> **Comments:**
> **username_1**: What do your mean by "transform"? One can obtain a positive semidefinite matrix by setting the diagonal entries as the nodes' degree, since it is equivalent to $N^T N$ where $N$ is the incidence matrix.  
> **username_2**: If all you care about is a PSD matrix, you could always just compute the Laplacian.  It's always PSD.  

---

## 2 answers

### Answer by username_3 on 2011-05-09. Score: 6 | Accepted answer

Your question is too imprecise. What does it mean to "transform a matrix"? Are you asking whether there is an algorithm that takes as input a symmetric matrix and finds the minimal total weight that can be added to diagonal entries so as to make the new matrix positive semi-definite?

If this is your question, the answer is yes, since it is an SDP. If you restrict to adding integer values to diagonal elements ("self loops"), then I do not know the complexity of finding the minimum number of self loops needed.

You might want to look into [Gershgorin's circle theorem](http://en.wikipedia.org/wiki/Gershgorin_circle_theorem) if you are trying to do this by hand.

> **Comments:**
> **username_0**: I think this theorem is very close to what I needed. thanks  
> **username_4**: One should observe that modifying the diagonal entries of the adjacency matrix by adding the terms that arise from Gershgorin's theorem amounts exactly to switching from the adjacency matrix to the so-called graph Laplacian.  

---

### Answer by username_5 on 2016-03-21. Score: 1

This is simple. Assume the adjacency matrix is $A$. As it is symmetric, it guarantees that $A$ can be diagonalized as $A=U\Sigma U^T$ by SVD decomposition, where $\Sigma=diag(\lambda\_1,...,\lambda\_n)$ is the diagonal matrix of eigenvalues. For node $i$, just add this mount of loop to it: $\text{ceiling}(|min(\lambda\_i,0)|)$.


---

