Matrix-Tree Theorem: proof with graph characteristic polynomial

171 Views Asked by At

This is a follow-up question regarding my previous one.
I went through the sections: 1.1 and 1.2 of the following script.
I am in the middle of the section 1.3 but I do not understand what is happening after the line:

"It is true that"

Why is that equality true? What is represented by the coefficient of t in the characteristic polynomial?
ALso, later in the equations: what happens to that coefficient and where does the additional (-1)^n-1 come from?

1

There are 1 best solutions below

8
On BEST ANSWER

Recall that

$$\chi(t)=\det(tI-L)=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{k=1}^n\left(t[k=\sigma(k)]-L_{k,\sigma(k)}\right)\;,\tag{1}$$

where $[k=\sigma(k)]$ is an Iverson bracket, equal to $1$ if $k=\sigma(k)$ and to $0$ otherwise. The terms in the summation on the righthand side of $(1)$ that contribute to the $t$ term in the polynomial $\chi(t)$ are those for which $\sigma$ has exactly one fixed point. Suppose that $r\in[n]$ is a fixed point of $\sigma$; then

$$\begin{align*} \operatorname{sgn}(\sigma)\prod_{k=1}^n\left(t[k=\sigma(k)]-L_{k,\sigma(k)}\right)&=\left(\operatorname{sgn}(\sigma)\prod_{\substack{k\in[n]\\k\ne r}}(-L_{k,\sigma(k)})\right)(t-d_r)\\ &=\left((-1)^{n-1}\operatorname{sgn}(\sigma)\prod_{\substack{k\in[n]\\k\ne r}}L_{k,\sigma(k)}\right)(t-d_r)\;, \end{align*}$$

which contributes

$$(-1)^{n-1}\operatorname{sgn}(\sigma)\prod_{\substack{k\in[n]\\k\ne r}}L_{k,\sigma(k)}$$

to the coefficient of $t$ in $\chi(t)$.

Now let $\hat\sigma\in S_{n-1}$ be defined from $\sigma$ as follows:

$$\hat\sigma(k)=\begin{cases} \sigma(k),&\text{if }k,\sigma(k)<r\\ \sigma(k)-1,&\text{if }k<r\text{ and }\sigma(k)>r\\ \sigma(k-1),&\text{if }k>r\text{ and }\sigma(k)<r\\ \sigma(k-1)-1,&\text{if }k,\sigma(k)>r \end{cases}$$

Since $\sigma(r)=r$, $\sigma$ induces a permutation of $[n]\setminus\{r\}$; $\hat\sigma$ is the ‘same’ permutation of $[n-1]$ after each member of $[n]$ greater than $r$ has been reduced by $1$. Thus, $\operatorname{sgn}(\hat\sigma)=\operatorname{sgn}(\sigma)$, and in fact

$$(-1)^{n-1}\operatorname{sgn}(\sigma)\prod_{\substack{k\in[n]\\k\ne r}}L_{k,\sigma(k)}=(-1)^{n-1}\operatorname{sgn}(\hat\sigma)\prod_{k=1}^{n-1}L_{k,\hat\sigma(k)}^{(r)}\;,$$

where $L_{i,j}^{(r)}$ is the $\langle i,j\rangle$ entry in the Laplacian matrix $L_r$.

It follows that the permutations in $S_n$ that fix $r$ contribute a total of

$$\begin{align*} \sum_{\substack{\sigma\in S_n\\\sigma(r)=r}}(-1)^{n-1}\operatorname{sgn}(\sigma)\prod_{\substack{k\in[n]\\k\ne r}}L_{k,\sigma(k)}&=(-1)^{n-1}\sum_{\sigma\in S_{n-1}}\operatorname{sgn}(\sigma)\prod_{k=1}^{n-1}L_{k,\sigma(k)}^{(r)}\\ &=(-1)^{n-1}\det L_r\;. \end{align*}$$

to the coefficient of $t$ in $\chi(t)$. The entire coefficient of $t$ is then obtained by summing over $r$: it’s

$$[t]\chi(t)=\sum_{r=1}^n(-1)^{n-1}L_r=(-1)^{n-1}\sum_{r=1}^n\det L_r\;,$$

and on multiplying by $(-1)^{n-1}$ we have

$$(-1)^{n-1}[t]\chi(t)=\sum_{r=1}^n\det L_r\;.$$


In the final calculation the expression

$$[t]\prod_{i=1}^n(t-\lambda_i)$$

is the coefficient of $t$ in the polynomial $\prod_{i=1}^n(t-\lambda_i)$. Before like terms in the product are collected, there are $n$ first degree terms: for each $r\in[n]$ we have the term

$$t\prod_{\substack{k\in[n]\\k\ne r}}(-\lambda_k)\;.$$

However, $\lambda_n=0$, so all of these are $0$ except the $r=n$ term,

$$t\prod_{k=1}^{n-1}(-\lambda_k)=\left((-1)^{n-1}\prod_{k=1}^{n-1}\lambda_k\right)t\;,$$

so the coefficient of $t$ in $\prod_{k=1}^n\lambda_k$ is

$$(-1)^{n-1}\prod_{k=1}^{n-1}\lambda_k\;;$$

that’s where the second $(-1)^{n-1}$ comes from.