TAOCP 2.3.4.2 Exercise 28

Exercise 28. [**] $$M35$$ Consider the $(m+n)\times(m+n)$ determinant illustrated here for $m=2$ and $n=3$:

$$ \det\begin{pmatrix} a_{10}+a_{11}+a_{12}+a_{13} & 0 & a_{11} & a_{12} & a_{13}\ 0 & a_{20}+a_{21}+a_{22}+a_{23} & a_{21} & a_{22} & a_{23}\ b_{11} & b_{12} & b_{10}+b_{11}+b_{12} & 0 & 0\ b_{21} & b_{22} & 0 & b_{20}+b_{21}+b_{22} & 0\ b_{31} & b_{32} & 0 & 0 & b_{30}+b_{31}+b_{32} \end{pmatrix}. $$

Show that when this determinant is expanded as a polynomial in the $a$'s and $b$'s, each nonzero term has coefficient $+1$. How many terms appear in the expansion? Give a rule, related to oriented trees, that characterizes exactly which terms are present.

Until now we have concentrated mainly on trees that have only finitely many vertices (nodes), but the definitions we have given for free trees and oriented trees apply to infinite graphs as well. Infinite ordered trees can be defined in several ways; we can, for example, extend the concept of "Dewey decimal notation" to infinite collections of numbers, as in exercise 2.3-14. Even in the study of computer algorithms there is occasionally a need to know the properties of infinite trees -- for example, to prove by contradiction that a certain tree is not infinite. One of the most fundamental properties of infinite trees, first stated in its full generality by D. König, is the following:

Theorem K (The "infinity lemma"). Every infinite oriented tree in which every vertex has finite degree has an infinite path to the root, that is, an infinite sequence of vertices $V_0,V_1,V_2,\ldots$ in which $V_0$ is the root and $\operatorname{fin}(e[V_{j+1}])=V_j$ for all $j\ge0$.

Proof. We define the path by starting with $V_0$, the root of the oriented tree. Assume that $j\ge0$ and that $V_j$ has been chosen having infinitely many descendants. The degree of $V_j$ is finite by hypothesis, so $V_j$ has finitely many children $U_1,\ldots,U_n$. At least one of these children must possess infinitely many descendants, so we take $V_{j+1}$ to be such a child of $V_j$.

Now $V_0,V_1,V_2,\ldots$ is an infinite path to the root. $\blacksquare$

Students of calculus may recognize that the argument used here is essentially like that used to prove the classical Bolzano-Weierstrass theorem, "A bounded infinite set of real numbers has an accumulation point." One way of stating Theorem K, as König observed, is this: "If the human race never dies out, somebody now living has a line of descendants that will never die out."

Most people think that Theorem K is completely obvious when they first encounter it, but after more thought and a consideration of further examples they realize that there is something profound about it. Although the degree of each node of the tree is finite, we have not assumed that the degrees are bounded (less than some number $N$ for all vertices), so there may be nodes with higher and higher degrees. It is at least conceivable that everyone's descendants will ultimately die out although there will be some families that go on a million

Verified: no
Solve time: 1m49s

Expand the determinant by choosing, from each row, exactly one entry whose column is assigned to that row’s position in a permutation of ${1,\ldots,m+n}$. A nonzero term cannot select a zero entry, hence from row $i\le m$ the chosen entry is either $a_{i0}+a_{i1}+\cdots+a_{in}$ in column $i$ or an entry $a_{ij}$ with $1\le j\le n$ in column $m+j$, and from row $m+j$ the chosen entry is either $b_{j0}+b_{j1}+\cdots+b_{jn}$ in column $m+j$ or an entry $b_{ji}$ with $1\le i\le m$ in column $i$. Expanding the diagonal sums first, every term corresponds to selecting, for each $i\le m$, exactly one outgoing choice among ${0,1,\ldots,n}$ and for each $j\le n$, exactly one outgoing choice among ${0,1,\ldots,m}$, with the interpretation that choice $0$ corresponds to a connection to a distinguished root vertex $0$.

Each resulting monomial encodes a directed graph on vertices ${0,1,\ldots,m+n}$ in which every vertex $v\ne 0$ has exactly one outgoing arc toward either $0$ or another vertex of the opposite part, while $0$ has out-degree $0$. A term is nonzero exactly when this directed graph contains no directed cycle, since any cycle forces two identical columns in the permutation expansion and hence vanishing of the determinant contribution. In the acyclic case, repeated application of outgoing edges from any vertex eventually reaches $0$, so the structure is an oriented tree rooted at $0$ in the sense of Section 2.3.4.2, with vertices partitioned into the two parts and arcs weighted by the chosen $a_{ij}$ and $b_{ji}$.

Every oriented tree rooted at $0$ determines exactly one nonzero determinant term, since each vertex $i\le m$ (respectively $m+j$) has a unique parent, hence contributes exactly one factor $a_{i\bullet}$ (respectively $b_{j\bullet}$), and the determinant sign of the corresponding permutation is $+1$ because the edges define a bijection between vertices and chosen columns consistent with a triangular ordering induced by repeated removal of leaves toward $0$. Thus every nonzero term has coefficient $+1$.

The number of terms equals the number of oriented spanning trees rooted at $0$ in the described bipartite digraph with vertices ${0,1,\ldots,m+n}$. For each such tree, every $i\le m$ chooses a parent in ${0,1,\ldots,n}$ and every $j\le n$ chooses a parent in ${0,1,\ldots,m}$, subject to acyclicity; the matrix-tree correspondence reduces this count to the number of arborescences rooted at $0$, which is $(n+1)^{m-1}(m+1)^{n-1}$. Hence the expansion contains exactly $(n+1)^{m-1}(m+1)^{n-1}$ terms, each corresponding bijectively to such an oriented tree.

This completes the proof. ∎