TAOCP 2.3.4.2 Exercise 18
For (a), first suppose that $G$ is a free tree and $m=n$.
Section 2.3.4.2: Oriented Trees
Exercise 18. [**] $$M30$$ Let $G$ be a graph with $n+1$ vertices $V_0,V_1,\ldots,V_n$ and $m$ edges $e_1,\ldots,e_m$. Make $G$ into a directed graph by assigning an arbitrary orientation to each edge; then construct the $m\times(n+1)$ matrix $A$ with
$$ a_{ij}= \begin{cases} +1, & \text{if } \operatorname{init}(e_i)=V_j;\ -1, & \text{if } \operatorname{fin}(e_i)=V_j;\ 0, & \text{otherwise.} \end{cases} $$
Let $A_0$ be the $m\times n$ matrix $A$ with column 0 deleted.
a) If $m=n$, show that the determinant of $A_0$ is equal to 0 if $G$ is not a free tree, and equal to $\pm1$ if $G$ is a free tree.
b) Show that for general $m$ the determinant of $A_0^T A_0$ is the number of free subtrees of $G$ (namely the number of ways to choose $n$ of the $m$ edges so that the resulting graph is a free tree). [Hint: Use (a) and the result of exercise 1.2.3-46.]
Verified: yes
Solve time: 1m26s
For (a), first suppose that $G$ is a free tree and $m=n$. Choose $V_0$ as root and orient every edge toward $V_0$ as described in the text. Then each vertex $V_j$ $(1\le j\le n)$ is the initial vertex of exactly one edge. Renumber the edges so that $e_j$ is the edge leaving $V_j$. Since $e_j$ joins $V_j$ to a vertex closer to the root, the matrix $A_0$ is triangular with diagonal entries all $+1$ or all $-1$, according to the chosen orientation. Hence $\det A_0=\pm1$. Reversing the orientation of any edge multiplies one row of $A_0$ by $-1$, changing the determinant only in sign; therefore $\det A_0=\pm1$ for every orientation of a free tree.
Now suppose $m=n$ and $G$ is not a free tree. If $G$ is disconnected, let $C_1,\ldots,C_r$ be its connected components. The sum of the columns of $A$ belonging to any component is $0$, so the columns of $A_0$ are linearly dependent and $\det A_0=0$. If $G$ is connected, then it contains a cycle. Since $m=n$, removing one edge of the cycle leaves a connected graph with $n-1$ edges, hence a free tree. By the first part, the corresponding $n-1$ rows of $A_0$ are linearly independent. The remaining row comes from the unique cycle and is a linear combination of those rows, because the signed incidence vectors around a cycle sum to $0$. Therefore the $n$ rows of $A_0$ are linearly dependent, and again $\det A_0=0$.
For (b), apply the Cauchy-Binet formula of exercise 1.2.3-46:
$$ \det(A_0^TA_0) =\sum_S \det(B_S)^2, $$
where $S$ ranges over all choices of $n$ rows of $A_0$, and $B_S$ is the resulting $n\times n$ submatrix. Each choice $S$ corresponds to a set of $n$ edges of $G$. By part (a), $\det(B_S)^2=1$ exactly when those $n$ edges form a free tree, and $\det(B_S)^2=0$ otherwise. Hence every free subtree contributes $1$ to the sum and every other edge set contributes $0$. Therefore $\det(A_0^TA_0)$ is exactly the number of free subtrees of $G$.
$$ \boxed{\det(A_0^TA_0)=\text{number of free subtrees of }G.} $$