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}