4
$\begingroup$

I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that

$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $

where $N_k(T)$ is the number of matchings of size $k$ of $T$.

However, I couldn't find a proof. Does anyone know how to do it? Thanks!

1 Answers 1

2

This is just a direct application of the definition of the determinant as the signed sum of all permuted products. Every term in that sum corresponds to a permutation of the vertices, which you can write as a product of cycles, and because the tree contains no cycles, for the term to be non-zero the permutation can only contain $1$- and $2$-cycles, with the $2$-cycles corresponding to edges. Each $2$-cycle yields a factor $-1$, and each $1$-cycle yields a factor $\lambda$, and the result follows.

  • 0
    @Joanne: You're welcome!2012-08-04