How to prove that for the real stable characteristic polynomial $P=\Phi_T$ of a tree $T$, $P_iP_j-PP_{ij}=(\Phi_{T-[v_i,v_j]})^2$?

Question

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$ deleted ?

In case $G$ is not a tree, how to prove $\Phi_G$ is still a perfect square ? How to read off the square root from the graph?

(Added) The fact that $\Delta_{ij}(P)$ is a perfect square holds more generally if we take $A$ to be any Hermitian matrix. In that case $\Phi_A$ is still real stable but $D_{ij}$ may be non real and the matrix identity implies $\Delta_{ij}(\Phi_A)=|D_{ij}|^2$ so that it is either a square or a sum of two squares of real polynomials. The interpretation of $D_{ij}$ as polynomial of deleted path in the case of tree is less obvious and actually holds in any graph for which there is a unique path from $v_i$ to $v_j$. How can one read off $D_{ij}$ from the graph when there is more than one path ?

Answer 1

Let $B$ denote the $n\times n$ matrix $I_x-A$. Let $[n]=\{1,2,\ldots,n\}$. For $I,J\subset [n]$ with the same number of elements, let $D_{I,J}$ denote the determinant of the matrix resulting from $B$ when deleting the rows indexed by the elements of $I$ and the columns indexed by the elements of $J$.

Assuming $i\neq j$, we clearly have $P=D_{\varnothing,\varnothing}$, $P_i=D_{\{i\},\{i\}}$, $P_j=D_{\{j\},\{j\}}$, and $P_{ij}=D_{\{i,j\},\{i,j\}}$. By the Dodgson condensation identity, $$ D_{\{i\},\{i\}}D_{\{j\},\{j\}}-D_{\{i\},\{j\}}D_{\{j\},\{i\}}= D_{\{i,j\},\{i,j\}}D_{\varnothing,\varnothing}\ . $$ Since $B$ is symmetric $D_{\{i\},\{j\}}=D_{\{j\},\{i\}}$. As a result $$ \Delta_{ij}=(D_{\{i\},\{j\}})^2\ . $$

In the tree case, the relation between $\Phi_{T-[v_i,v_j]}$ and $D_{\{i\},\{j\}}$ can be worked out using Theorem 1 of my article "The Grassmann–Berezin calculus and theorems of the matrix-tree type" in Adv. Appl. Math. 2004. For those without access to the journal, the preprint version is here.