Let $P_{ij}$ be variables, and let $A \in \mathbb{R}^{n\times n}$ be the matrix defined by $$ A_{ij} = \begin{cases} -P_{ij} & i \neq j,\\ P_{i1} + P_{i2} + \dots + P_{in} & i=j. \end{cases} $$ For instance for $n=3$ $$ A = \begin{bmatrix} P_{1,1}+P_{1,2}+P_{1,3} & -P_{1,2} & -P_{1,3}\\ -P_{2,1} & P_{2,1}+P_{2,2}+P_{2,3} & -P_{2,3}\\ -P_{3,1} & -P_{3,2} & P_{3,1}+P_{3,2}+P_{3,3} \end{bmatrix}. $$ Then, computationally I observe that $\det(A)$ is the sum of $(n+1)^{n-1}$ distinct terms, each of which is the product of $n$ variables $P_{ij}$. For instance for $n=3$ we get the 16 terms \begin{align*} \det(A) &= P_{1,1}\,P_{2,1}\,P_{3,1}+P_{1,1}\,P_{2,1}\,P_{3,2}+P_{1,1}\,P_{2,2}\,P_{3,1}+P_{1,1}\,P_{2,1}\,P_{3,3} \\ &+ P_{1,1}\,P_{2,2}\,P_{3,2}+P_{1,1}\,P_{2,3}\,P_{3,1}+P_{1,2}\,P_{2,2}\,P_{3,1}+P_{1,1}\,P_{2,2}\,P_{3,3} \\ &+P_{1,2}\,P_{2,2}\,P_{3,2}+P_{1,1}\,P_{2,3}\,P_{3,3}+P_{1,2}\,P_{2,2}\,P_{3,3}+P_{1,3}\,P_{2,1}\,P_{3,3} \\& +P_{1,3}\,P_{2,2}\,P_{3,2}+P_{1,2}\,P_{2,3}\,P_{3,3}+P_{1,3}\,P_{2,2}\,P_{3,3}+P_{1,3}\,P_{2,3}\,P_{3,3}. \end{align*} Interestingly, there are no minus signs in the formula. Is this a known result? It looks like it might have a nice combinatorial interpretation, since the number of terms matches Cayley's formula for the number of trees on $n+1$ labeled nodes (https://oeis.org/A000272).
-
1$\begingroup$ I haven't worked through the details, but I expect this would follow fairly immediately from the first (un-numbered) theorem on Page 379 of this paper: the sum described in that theorem also has $(n+1)^{n-1}$ terms, and there is a similar distinction between terms like $-P_{ij}$ and $P_{i1}+\cdots+P_{in}$ there. $\endgroup$– Nathaniel JohnstonCommented Nov 8 at 16:42
-
$\begingroup$ @NathanielJohnston Thanks, the suggestion was spot-on. I have filled in the blanks in a CW answer, but if you wish to write your own answer I will be happy to accept it. $\endgroup$– Federico PoloniCommented Nov 9 at 12:51
-
$\begingroup$ Nope, I’m happy to not work through the details myself. Glad it worked out! $\endgroup$– Nathaniel JohnstonCommented Nov 9 at 13:48
1 Answer
Nathaniel Johnston's comment is correct; this is indeed a variant of the matrix tree theorem. To see this, one needs to rename the variable $P_{i,i}$ to $P_{i,0}$, for each $i$.
Then, $A$ becomes the matrix obtained by removing the $0$th row and column from the $(n+1)\times (n+1)$ matrix $$ L = \begin{bmatrix} * & -P_{0,1} & -P_{02} & -P_{0,3}\\ -P_{1,0} & * & -P_{1,2} & -P_{1,3}\\ -P_{2,0} & -P_{2,1} & * & -P_{2,3}\\ -P_{3,0} & -P_{3,1} & -P_{3,2} & * \end{bmatrix}, $$ where the diagonal entries denoted by $*$ are chosen so that each row sums to $0$. This matrix is the Laplacian of a weighted directed graph, and we can apply the generalized matrix tree theorem suggested in the comment (the first unnumbered theorem on page 379 of https://doi.org/10.1016/0097-3165(78)90067-5). This theorem states that $\det A$ is the sum of the weights of all arborescences (directed trees) rooted in the vertex $v_0$, each of which is a product of $n$ variables of the form $P_{ij}$.