$\DeclareMathOperator\perm{perm}\DeclareMathOperator\len{len}$Let $A$ be the adjacency matrix of a tree $T$ for some ordering $v_1,...,v_n$ of the vertices, and let $D=xI-A$ its characteristic matrix, and $D_{ij}$ the sub-matrix obtained from $D$ by deleting the $i$th row and $j$th column. Clearly $\det( D_{ii})=\phi_{T-v_i}(x)$ is the characteristic polynomial of $T$ with $v_i$ deleted. This has an interesting extension to the case $i<j$ but only up to a square factor namely
$$(\det D_{ij})^2=\det(D_{ij}D_{ji})=\phi_{T-[v_i,v_j]}(x)^2$$
where $T-[v_i,v_j]$ is the forest obtained from $T$ by deleting all vertices on the unique path from $v_i$ to $v_j$. It follows that
$$\det (D_{ij})= \pm \phi_{T-[v_i,v_j]}(x),$$
which begs the question of how are the signs determined? Both signs can occur for different $i,j$ but there does not seem to be a simple rule. For instance if $T=[12,23,24,15,56]$ then the sign is a plus if $i=j$ or $ij=13,24,15,35,26,46$. I am curious to know the rule even if a proof is not available.
Interestingly there is a similar formula if we replace $\phi_A(x)$ by the permanent characteristic polynomial,$\psi_A(x):=\perm(xI-A)$ and now there is a simple rule for the sign.
$$\perm(D_{ij})=(-1)^{\len([v_i,v_j])} \psi_{T-[v_i,v_j]}(x),$$
where $\len([v_i,v_j])$ is the length of the path $[v_i,v_j]$.
(Added) There is a very simple extension if $A$ is the adjacency matrix of a graph $G$ not necessarily a tree. We then have
$\det(D_{ij})=(-1)^{i+j}\sum_{[v_i,v_j]} \phi_{G-[v_i,v_j]}(x),$ and
$perm(D_{ij})=\sum_{[v_i,v_j]} (-1)^{(len[v_i,v_j])} \psi_{G-[v_i,v_j]}(x),$
where the sum is over all simple paths (ie. all verices on the path distinct) from $v_i$ to $v_j$.
(Added 2) The formula for sum over all paths was found by guessing. It is not at all obvious because of cancelations. If we label the edges with new variables, there will be no cancelation and a term coding the path appears, and it becomes impossible not to see the sum over all paths.
We define the labelled adjacency of a graph by $A_y[i,j]=A_y[j,i]=y_{ij}$ if $(i,j)$ is an edge and zero otherwise. Let $I_x=diag\{x_1,...,x_n\}$. The multi-variable homogeneous characteristic polynomial of $G$ is $\Phi_G(x,y)=\det (I_x-A_y)$ and similarly $\Psi_G(x,y)= perm (I_x-A_y)$. They are homogeneous polynomial in $x_i,y_{jk}$ of degree $n$. For $D=I_x-A_y$, we now have
$$(-1)^{i+j} \det D_{ij}=\sum_{p_{ij} \in [v_i.v_j]} \Phi_{G-p_{ij}}(x,y) \prod_{y \in p_{ij}} y_{st},$$ $$perm D_{ij}=\sum_{p_{ij} \in [v_i.v_j]} (-1)^{len(p_{ij})} \Psi_{G-p_{ij}}(x,y) \prod_{y \in p_{ij}} y_{st},$$ where $p_{ij}$ range over all non self-intersecting path from $v_i$ to $v_j$ and the product term $\prod y_{st}$ is over all the edges in the deleted path.
(Added 4) The perm formula above is invariant (independent of vertex ordering) since we can replace $ij$ by $uv$ where $u$,$v$ are given vertices and $len(p_{uv})$ is invariant. However it is impossible to get rid of $(-1)^{i+j}$ so the det formula cannot be made invariant. In a sense, one can say this example lead us to "discover" fermions can have 1/2-intergal spin. I knew the perm formula already and was looking for an invariant sign for det and that's why I missed the very obvious $(-1)^{i+j}$. So it is good to think basis-free even when it fails.
eg. If $G=[12,23,34,24,25,45]$, $[v_1,v_5]=[125,12345,1245]$, and we have $$\det D_{15}=y_{12}y_{25}(x_3x_4-y_{34}^2)+y_{12}y_{23}y_{34}y_{45}+y_{12}y_{24}y_{45}x_3$$ $$ perm D_{15}=y_{12}y_{25}(x_3x_4+y_{34}^2)+y_{12}y_{23}y_{34}y_{45}-y_{12}y_{24}y_{45}x_3$$
So one can find all paths between two vertices in a graph by evaluating an $(n-1) \times (n-1)$ determinant.
There is a way to distinguish between the $y_{st}$ occurring in a path from those in $\Phi_G(x,y)$.
For a tree $T$, $\phi_T(x)=\sum_{k=0}^{[n/2]} (-1)^kc_kx^{n-2k}$, where $c_k$ counts the number of matchings (mutually non adjacent edges) of size $k$). The homogenised form enumerate the $k$-matchings $\prod y_{ij}^2$ with square term times a produce of $x_i$ which does not appear as vertices , in other words, the $y_{ij}$ and the $x_k$ form a spanning forest.
Eg. if $T=[[1,2],[2,3],[2,4],[4,5]]$. $$\Phi_T(x,y)=x_1x_2x_3x_4x_5-(x_3x_4x_5y_{12}^2+x_1x_4x_5y_{23}^2+x_1x_3x_5y_{24}^2+x_1x_2x_3y_{45}^2) $$ $$+x_3(y_{12}y_{45})^2+x_1(y_{23}y_{45})^2,$$ but the $y_{st}$ need not be squared when there is a cycle, eg $G=[12,23,13]$ $\Phi_G(x,y)=x_1x_2x_3-(x_1y_{23}^2+x_2y_{13}^2+x_3y_{12}^2)-2y_{12}y_{23}y_{13}$,
where the last term corresponding to a cycle is square-free but they always occurred doubled which follows from the deletion formula.
So if we let $D=I_n-A_y$ and $P=\det D_{ij}$, $$\left(P(y)-\sum_{1 \le s < t \le n}\frac{y_{st}^2}{2}\frac{\partial^2P}{\partial y_{st}^2}(y) \right) \; \; mod \;\;2=\sum_{p_{ij} \in [v_i.v_j]} \prod_{y \in p_{ij}} y_{st},$$ will be a sum of paths joining $v_i$ to $v_j$, and there is a similar all minor version for multiple paths.
(Added August 2002) The sum over all paths formula follows essentially from the edge deletion formula. If $e=ij$ is an edge, $$\Phi_G(x,y)=\Phi_{G-e}(x,y)-y_{ij}^2\Phi_{G-[e]}(x,y)-2\sum_{C \ni e} \Phi_{G-C}(x,y)\prod_{y \in C} y_{uv},$$ where $C$ range over all cycles containing $e$. If we remove $e$ from all the cycles, we get all paths from $v_i$ to $v_j$.
Interestingly, there is a similar sum over all path formula for the matching polynomial : $$ M_G(x,y)=\sum_{y_{ij}=(x_ix_j) \in M} (-1)^k \frac{x_1...x_n (y_{i_1j_1}...y_{i_kj_k})^2}{(x_{i_1}x_{j_1})...(x_{i_k}x_{j_k})},$$ where the sum is over all sets of mutually non-adjacent edges $\{y_{i_s,j_s}\}$ and $x_{i_s},x_{j_s}$ are their end points. This agrees with the characteristic polynomial $\Phi_G(x,y)$ if $G$ is a tree and specialize to the usual matching polynomial $m_G(x)=\sum (-1)^km_kx^{n-2k}$ in the one variable case, where $m_k$ is the number of $k$ matchings. An important non obvious property of $m_G(x)$ is that it is real rooted. One can also prove this by showing that it lifts to a real stable multi-variable polynomial $M_G(x)$. Since $M_G(x)$ is multi-affine, it suffices to prove that $\Delta_{ij}(M_G(x)) \ge 0$ where $\Delta_{ij}(P):=P_i P_j- P P_{ij}$. We observe that it is always a sum of squares indexed by non self intersecting paths from $v_i$ to $v_j$
$$\Delta_{ij}(M_G(x,y))=\sum_{p_{ij} \in [v_i,v_j]} M_{G-p_{ij}}(x,y)^2 \prod_{y \in p_{ij}} y_{uv}^2.$$ Note in contrast, we have earlier for the characteristic polynomial $\Phi_G(x,y)$ $$\Delta_{ij}(\Phi_G(x,y))=\left( \sum_{p_{ij} \in [v_i,v_j]} \Phi_{G-p_{ij}}(x,y) \prod_{y \in p_{ij}} y_{uv} \right)^2,$$ where the squareroot term on the right Is $(-1)^{i+j}D_{ij}$.
Question 1: How does one prove the first formula for $\Delta_{ij}(M_G(x,y))$ ? The edge deletion formula for matching polynomial does not have a sum over all cycles term.
Non self intersecting paths are exactly self avoiding walks, which seem to be very hard to compute and it seems that we have unintentionally found a formula which may be useful.
We also observe that the connective constant of the Honeycomb lattice $\sqrt{2+\sqrt{2}}$ is the largest eigenvalue of the matching polynomial of a square (coincidence?), $x^4-4x^2+2$ which means its $2r$ moments $2(2+\sqrt{2})^r+2(2-\sqrt{2})^r$ counts all the tree like closed walks in a square. This means if $c_r$ is the number of closed walks rooted at a vertex of the path tree (which is a rooted tree with two tails which are paths of length $3$), then $c_r \sim (\sqrt{2+\sqrt{2}})^r/2$. Note that if we write the square as $G=[12,23,34,14]$, then the path tree at $1$, $T_G(1)=[1,12,123,1234,14,143,1432]$ is just the path graph on $7$ vertices rooted at the center and if we identify the two end points, we get exactly a hexagon.
Question 2: Is there a way to relate closed walks on this path tree to self avoiding walks on the Honeycomb lattice since they grow at the same rate ?
