Exercise 4, § 2

Soit G a finite graph and let $Q = (S,F, o, t)$ be its underlying quiver. We endow the space $\mathbf{C}^S$ with the unique hermitian space structure for which its canonical basis is orthonormal. Let $L:\mathbf{C}^S\rightarrow \mathbf{C}^S$ be the mapping given by $L(u)(x) =\sum_{o(f)=x}(u(t(f))-u(x))$ for $x\in S$ and $u\in \mathbf{C}^S$.

(a) Prove that the endomorphism L of $\mathbf{C}^S$ is positive (EVT, V, p. 45, def. 6).

(b) Prove that the kernel of L consists of the functions $u\in \mathbf{C}^S$ which are constant on each connected component of G.

(c) Let $F_1$ be an orientation of G. Let E $= (e_{s,f})$ be the matrix of type $(S,F_1)$ given by

1 if $o(f) =s$ and $t(f)=\not s$;

$e_{s,f}=-1$ if $o(f)=\not s$ and $t(f) =s$;

0 otherwise.

Prove that the matrix Λ of L in the canonical basis of $\mathbf{C}^S$ is given by Λ = $E\cdot^tE$.

(d) Suppose that G is connected and that the set of its vertices is not empty; let $x$ be a vertex of G and let $S'= S-\{x\}$. Let T be a subset of F of cardinal Card(S$'$). Prove that T is the set of arrows of a maximal oriented subtree of G (endowed with the orientation $F_1$) if and only if the rank of the matrix $E'_T$ of type $(S',T)$ deduced from E is equal to Card(S$'$). Deduce then that the determinant of the matrix $\Lambda_{S',S'}$ is equal to the number of maximal oriented subtrees of G. (Use Exercise 6 of A, III, §8, p. 192.)

(e) Let W be the orthogonal of Ker(L). Prove that W is a subspace of $\mathbf{C}^S$ which is stable by W and that det(L$|_W$) is equal to the number of maximal forests of the graph G (Kirchhoff's theorem).