# Making an adjacency matrix positive semidefinite

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.

• 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 張顯之 May 9 '11 at 5:51
• If all you care about is a PSD matrix, you could always just compute the Laplacian. It's always PSD. – John Moeller May 9 '11 at 15:14

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