Determinant formula for a certain parametrized M-matrix

Question

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).

Answer 1

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}$.