3
$\begingroup$

Let $L$ be the Laplacian of a directed weighted graph on $n$ nodes, e.g., for $n=4$: $$ L = \left(\begin{array}{cccc} w_{1,1}+w_{1,2}+w_{1,3}+w_{1,4} & -w_{1,2} & -w_{1,3} & -w_{1,4}\\ -w_{2,1} & w_{2,1}+w_{2,2}+w_{2,3}+w_{2,4} & -w_{2,3} & -w_{2,4}\\ -w_{3,1} & -w_{3,2} & w_{3,1}+w_{3,2}+w_{3,3}+w_{3,4} & -w_{3,4}\\ -w_{4,1} & -w_{4,2} & -w_{4,3} & w_{4,1}+w_{4,2}+w_{4,3}+w_{4,4} \end{array}\right) $$ I am interested in a closed-form in terms of the $w_{i,j}$ of the inverse of its $(n-1)\times (n-1)$ leading submatrix $M = L_{1:n-1, 1:n-1}$.

Kirchoff's matrix-tree theorem states that $\det M$ can be written as a sum of products of $w_{ij}$ with a certain combinatorial interpretation as trees, and we all know that the inverse matrix can be written as $M^{-1} = \frac{1}{\det M} \operatorname{adj}(M)$. Heree $\operatorname{adj}(M)$ is the adjugate matrix, whose entries can be expressed as $(n-2)\times(n-2)$ determinants times a sign. It seems that also these numerators are sums of products of the $w_{ij}$, for instance for $n=4$:

$$ \operatorname{adj}(M) = \left(\begin{array}{ccc} \left(w_{2,1}+w_{2,2}+w_{2,3}+w_{2,4}\right)\,\left(w_{3,1}+w_{3,2}+w_{3,3}+w_{3,4}\right)-w_{2,3}\,w_{3,2} & w_{1,2}\,w_{3,1}+w_{1,2}\,w_{3,2}+w_{1,2}\,w_{3,3}+w_{1,3}\,w_{3,2}+w_{1,2}\,w_{3,4} & w_{1,3}\,w_{2,1}+w_{1,2}\,w_{2,3}+w_{1,3}\,w_{2,2}+w_{1,3}\,w_{2,3}+w_{1,3}\,w_{2,4}\\ w_{2,1}\,w_{3,1}+w_{2,1}\,w_{3,2}+w_{2,1}\,w_{3,3}+w_{2,3}\,w_{3,1}+w_{2,1}\,w_{3,4} & \left(w_{1,1}+w_{1,2}+w_{1,3}+w_{1,4}\right)\,\left(w_{3,1}+w_{3,2}+w_{3,3}+w_{3,4}\right)-w_{1,3}\,w_{3,1} & w_{1,1}\,w_{2,3}+w_{1,3}\,w_{2,1}+w_{1,2}\,w_{2,3}+w_{1,3}\,w_{2,3}+w_{1,4}\,w_{2,3}\\ w_{2,1}\,w_{3,1}+w_{2,1}\,w_{3,2}+w_{2,2}\,w_{3,1}+w_{2,3}\,w_{3,1}+w_{2,4}\,w_{3,1} & w_{1,1}\,w_{3,2}+w_{1,2}\,w_{3,1}+w_{1,2}\,w_{3,2}+w_{1,3}\,w_{3,2}+w_{1,4}\,w_{3,2} & \left(w_{1,1}+w_{1,2}+w_{1,3}+w_{1,4}\right)\,\left(w_{2,1}+w_{2,2}+w_{2,3}+w_{2,4}\right)-w_{1,2}\,w_{2,1} \end{array}\right) $$ I have written it in this form for simplicity, but if one expands the parentheses each diagonal entry contains a sum of 15 products, all with the plus sign. These diagonal entries can be given a combinatorial interpretation via the matrix tree theorem, since $(\operatorname{adj} M)_{ii}$ is the determinant of the $(n-2)\times(n-2)$ matrix obtained by removing row and columns $i$ and $n$ from $L$.

Is there a combinatorial interpretation also for the off-diagonal entries $\operatorname{adj}(M)_{ij}$, $i\neq j$? I imagine with sufficient work one can recurse one more level, but maybe there is already a known result stating this interpretation, since it is a similar setting to the matrix-tree theorem. My searches for "matrix tree theorem + inverse" have returned no useful result.

$\endgroup$

1 Answer 1

7
$\begingroup$

There is a formula as a sum of forests, i.e., collections of trees, for arbitrary minors of any size and row/column selection, for arbitrary matrices. So it can be applied for the numerator and the denominator of the present matrix. See Theorem 1 in my article "The Grassmann-Berezin calculus and theorems of the matrix-tree type". Adv. in Appl. Math. 33 (2004), no. 1, 51--70. Preprint version . Published version.

$\endgroup$
5
  • $\begingroup$ Thanks! That seems on point, but tricky to process for me. One question for now: in the figure on page 7 (resp. 57), it seems that the edges point not only away from $j$, but also towards $i$. Is that an additional condition that needs to be verified? $\endgroup$ Commented Nov 22, 2024 at 16:07
  • $\begingroup$ For your denominator there is only one $i$ and one $j$ so they are automatically paired and in just one tree. The rule is you look at the backbone, i.e., path connecting $i$ and $j$. There the arrows must flow from $j$ to $i$. The backbone treated as a single entity is the "root" from which all the other arrows are outflowing. $\endgroup$ Commented Nov 22, 2024 at 18:17
  • $\begingroup$ For the numerator, one first sums over the two possible pairings of an $i$ with a $j$, then the forest is made of two trees (because you impose zero sum rows) and each $i,j$ pair is inside one of these two trees. Within one of theses trees, the orientation is as in the above comment with backbone rooting etc. $\endgroup$ Commented Nov 22, 2024 at 18:19
  • $\begingroup$ Oops, I forgot my formula gives two trees if the column sums are zero. So you need to apply it to the transpose of your matrix. $\endgroup$ Commented Nov 22, 2024 at 18:21
  • $\begingroup$ got it, thanks! $\endgroup$ Commented Nov 22, 2024 at 19:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.