Tag Archives | facts I wish I knew in school

more on matrix-tree formula

Fix a weighted graph \(\Gamma=(V,E), w:E\to \mathbb{R}\).

The Laplacian \(L\) of \(\Gamma\) is the symmetric matrix

$$
L_{u,v}=\left\{
\begin{array}{ll}
-w(uv)&\mbox{ if }u\neq v,\\
\sum_{u’\neq u} w(uu’)& \mbox{ if }u=v\\
\end{array}\right..
$$

(Here we view the weights \(w\) as formal variables.)

As we all know, any principal minor of \(L\) equals the sum of the weights of spanning trees of \(\Gamma\).

Another way to define the principal minor is as the determinant of the restriction the quadratic form given by \(L\) to any of the coordinate hyperplanes.…

Read full story Comments { 0 }