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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ 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. $\endgroup$– Hsien-Chih Chang 張顯之Commented May 9, 2011 at 5:51
-
1$\begingroup$ If all you care about is a PSD matrix, you could always just compute the Laplacian. It's always PSD. $\endgroup$– Josephine MoellerCommented May 9, 2011 at 15:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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 if you are trying to do this by hand.
-
$\begingroup$ I think this theorem is very close to what I needed. thanks $\endgroup$– N27Commented May 9, 2011 at 6:06
-
1$\begingroup$ 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. $\endgroup$– Delio M.Commented Jan 8, 2014 at 11:00
$\begingroup$
$\endgroup$
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)|)$.
