0
$\begingroup$

Let $L$ be a graph Laplacian. What is the meaning of the entries of its (pseudo)inverse $L^{-1}$? In other words, are there any interpretations which might help with understanding the entries of $L^{-1}$?

$\endgroup$
2
  • 2
    $\begingroup$ There is no graph - your link is missing. $\endgroup$
    – joseph h
    Feb 6 at 2:14
  • $\begingroup$ I fixed it, thank you. $\endgroup$
    – Zuza
    Feb 6 at 9:50

1 Answer 1

1
$\begingroup$

I originally wanted to pose the question, but then I started investigating and found a few very helpful interpretation that haven't been collected anywhere (to my knowledge). Hence, I will write my results here for future reference:

Interpretation of the entries of $L^{-1}$:

  • The i'th row (or column, it's symmetric) of $L^{-1}$ represents the voltage at vertices required such that the unique electrical flow sends a total of 1 unit of flow from the i'th vertex in a way that each vertex receives $1/|V|$ units of flow.

  • Let the energy of a flow $f \in \mathbb{R}^E$ be $\sum_{e \in E} f_i^2$. Let the effective resistance between two vertices $u, v$ be the minimum energy requred to send a unit of flow from $u$ to $v$. The effective resistance between $u, v \in V$ is $(1_u - 1_v)^T L^{-1} (1_u - 1_v)$ where $1_i$ is the i'th canonical basis vector.

  • (Assume the graph is connected, degree regular, and not bipartite.) Let $s, t \in V$. Start with +1 units of "supply" in $s$ and -1 of "supply" in $t$. Do a random walk (each vertex chooses a random incident edge and pushes all of its supply to the other node). The expected amount of supply at node j (summed up over all steps) is exactly $M_{sj} - M_{tj}$ where $M := L^{-1}$ (I had to introduce M due to some MathJax+SE formatting issue).

$\endgroup$

Your Answer

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

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