-1
$\begingroup$

As known, the graph Laplacian $L = D - A$ is semi-positive definite.

What if there is a matrix $A'$ where

$$ A'_{ij} = \begin{cases} A_{ij}, \quad if A_{ij} >0 \\ -\varepsilon, \quad if A_{ij} = 0 \end{cases} $$

where $\varepsilon$ is a parameter.

Is $L' = D - A'$ still semi-positive definite? Thanks.

Be more specific, Let's say the affinity matrix $A$ is : \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{array}

and lest $\epsilon$ = 0.1

Then $A'$ will be: \begin{array}{ccc} 1 & -0.1 & -0.1 \\ -0.1 & 1 & 1 \\ -0.1 & 1 & 1 \end{array}

$\endgroup$
0

1 Answer 1

1
$\begingroup$

If you adjust the diagonal accordingly then yes, because it would correspond to the Laplacian matrix of a slightly different edge-weighted graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.