Determinant of the distance matrix of a tree

Séminaire Lotharingien de Combinatoire XX (2024) Proceedings of the 36th Conference on Formal Power Article #YY, 12 pp. Series and Algebraic Combinatorics (Bochum) Determinant of the distance matrix of a tree Emmanuel Briand1, Luis Esquivias23, Álvaro Gutiérrez24, Adrián Lillo2, Mercedes Rosas2 1Departamento Matemática Aplicada 1, University of Seville, Seville, 2Departamento de Álgebra, University of Seville, Seville, 3Departamento de Álgebra, Geometría y Topología, Universidad Complutense, Madrid, 4Department of Mathematics, University of Bonn, Bonn. Abstract. We present a combinatorial proof of the Graham–Pollak formula for the determinant of the distance matrix of a tree, via sign-reversing involutions and the Lindström–Gessel–Viennot lemma. Résumé. Nous présentons une preuve combinatoire de la formule de Graham et Pollak pour le déterminant de la matrice des distances d’un arbre, en utilisant des involutions et le lemme de Lindström–Gessel–Viennot. Keywords: Distance matrix of a tree. Lindström–Gessel–Viennot’s Lemma. Signreversing involutions. Bijective Combinatorics. 1 Introduction Consider a tree Twith vertices labeled from one to n, and edge set E. Define the distance between vertices iand j, denoted by d(i,j), as number of edges in the unique path of T connecting iand j. Define the distance matrix of Tas M(T) = (d(i,j))1≤i,j≤n. In their influential 1971 paper [7], Graham and Pollak established that the determinant of the distance matrix of Tobeys the Graham–Pollak formula: det M(T) = (−1)n−1(n−1)2n−2(1.1) Observe that this implies that the determinant of the distance matrix of Tis solely dependent on its number of vertices, and not on its tree structure. Multiple techniques drawn from linear algebra, ranging from Gauss elimination to Charles Dodgson’s condensation formula, have been used to prove the Graham–Pollak formula [4,7,6,9,10,11]. However, the expression (−1)n−1(n−1)2n−2suggests the existence of a signed enumeration problem solved by det M(T). Pursuing this trail has led us to a novel combinatorial proof of the Graham–Pollak formula that relies on the existence of sign-reversing involutions, and on the celebrated Lindström–Gessel–Viennot lemma. Our journey concludes by establishing that our combinatorial proof provides a solid framework for many of the existing generalizations and q-analogues of the Graham–Pollak formula, and facilitates the derivation of new ones. 2E. Briand, L. Esquivias, Á. Gutiérrez, A. Lillo, M. Rosas 2 Catalysts Where we introduce the idea of a catalyst for a tree, and demonstrate how det(T)does a signed enumeration of all catalysts of a fixed tree T = ([n],E). Fix a tree T= ([n],E). Let E±={(i,j):{i,j} ∈ E}denote the set of arcs supported on T. Given a permutation σin Snand a map f:[n]→E±, the ordered pair (σ,f)is a catalyst for T if for each vertex i,f(i) = (vi,vi+1)is a pair of successive vertices in the path P(i,σ(i)) (i.e., an arrow). The sign of a catalyst is the sign of its underlying permutation. (a) (b) (c) 1 2 3 4 5 6 7 8 9 κ= (σ,f)κ0= (σ0,f0)κ00 = (σ00,f00) Figure 1: A tree Tand the diagrams of three of its catalysts. We can recover a catalyst from its diagram. E.g., from the first diagram we see that σ(1) = 6 and f(1) = (1,2), that σ(2) = 5 and f(2) = (2, 5), that σ(3) = 8 and f(3) = (3,1), and so on. The determinant det M(T)does a signed enumeration of all catalysts for T. This is so because d(i,σ(i)) counts the number of edges in the unique path P(i,σ(i)) in T. Indeed, det M(T) = ∑ σ∈Sn sgn(σ)d(1, σ(1))d(2, σ(2)) . . . d(n,σ(n)) = ∑ κ∈K sgnκ, (2.1) where we are summing over K, the set of all catalysts for T. It is worth noting that the definition of catalyst implies that its underlying permutation must be a derangement, that is, a permutation without fixed points. Partitioning catalysts by their underlying permutations proves ineffective in our search of a combinatorial proof of the Graham–Pollak formula, as in general, there are no cancellations between resulting summands. 3 Arrowflows and the Graham–Pollak formula Where we present the definition of the arrowflow induced on T by a catalyst, and show how the Graham–Pollak formula becomes transparent when catalysts are partitioned according to them. Determinant of the distance matrix of a tree 3 An arrowflow on T is a directed multigraph with vertex set [n], with exactly narcs when counted with multiplicity, and whose underlying simple graph is a subgraph of T. By definition, given any catalyst κ= (σ,f), the image of f, considered as a multiset, is always an arrowflow on T. We refer to it as arrowflow induced by κ. We say that an arrowflow Ais connected when its underlying simple graph is. If Ais a connected arrowflow, there exist precisely two vertices that belong to more than one arrow of A. It turns out that these two vertices always belong to precisely two arrows, that we call the repeated arrows. We say that the repeated arrows of a connected arrowflow are parallel when they point in the same direction, and anti-parallel when they point in opposite directions. An arrowflow is said to be unital when it is connected and its repeated arrows are anti-parallel, as illustrated in Figure 2(a). Otherwise, it is said to be zero-sum. There are two possible causes for an arrowflow to be zero-sum. Either the arrowflow is disconnected, as illustrated in Figure 2(b), or the arrowflow is connected, but the repeated arrows are parallel, as in Figure 2(c). Example 3.1. Figure 2shows the three arrowflows induced by the three catalysts of Figure 1. The first arrowflow (a) is unital. The second arrowflow (b) is zero-sum because it is disconnected. The last one (c) is zero-sum because arc (1, 2)appears twice. (a) (b) (c) 12 3 45 6 7 8 9 12 3 45 6 7 8 9 12 3 45 6 7 8 9 Figure 2: (a) Unital, (b) disconnected zero-sum, (c) connected zero-sum arrowflows. It is crucial to observe that different catalysts on Tcan result on the same arrowflow. On the other hand, it is worth pointing out that there exist arrowflows on Tthat are not induced by any catalyst for T. We leave it to the reader to come up with such examples. We define the arrowflow class of A, denoted by C(A), as the set of catalysts inducing Aon T. An arrowflow class C(A)is unital or zero-sum according to whether Ais unital or zero-sum. Nonempty arrowflow classes define a partition K=FAC(A)of the set Kof all catalysts for T, that we call the arrowflow partition of K. It allows us to rewrite Equation (2.1) as det M(T) = ∑ A arrowflow ∑ κ∈C(A) sgn(κ), (3.1) where the first sum is taken over all arrowflows on T, and the second one over all catalysts κin the arrowflow class C(A). 4E. Briand, L. Esquivias, Á. Gutiérrez, A. Lillo, M. Rosas Theorem 3.2. The arrowflow partition defines an optimal way of partitioning the set of catalysts for T. More precisely, if C(A)is an arrowflow class, then ∑ κ∈C(A) sgn(κ) = ((−1)n−1if A is a unital arrowflow, 0if A is a zero-sum arrowflow. (3.2) The proof of this result will unfold in the following two sections. We close this section by showing how a combinatorial proof of the Graham–Pollak formula can be obtained by gathering all the elements of our reasoning. First observe that Theorem 3.2 implies that there can be no cancellations between the different summands in Equation (3.1). Therefore, it suffices to show that ∑ Aunital arrowflow (−1)n−1= (−1)n−1(n−1)2n−2. Or equivalently, that there exists (n−1)2n−2unital arrowflows on T. This is immediate as the factor (n−1)counts the number of ways of selecting the edge of Tthat gives rise to the anti-parallel repeated arrows, whereas factor 2n−2counts the number of ways in which the remaining n−2 edges can be oriented. Finally, to show that the sign of a unital arrowflow class is (−1)n−1, we show that the underlying permutation of the unique catalyst that survives the involution process is always an n-cycle. 4 Zero-sum arrowflows Where we present a sign-reversing involution without fixed points on each zero-sum arrowflow class, and conclude that the signed sum of catalyst in such a class is always zero. This is achieved in Lemma 4.1, which implies that the signed sum of catalysts in a zero-sum arrowflow class C(A)is zero. This constitutes one half of Lemma 3.2. Lemma 4.1. Let A be a zero-sum arrowflow on T. If A is connected, let i and j be the two preimages of the repeated arrow (a,b)of A. On the other hand, if A is disconnected, we let {i,j} be an edge of T such that neither (i,j)nor (j,i)is in A. Then, the map ϕ:C(A)→C(A)that sends the catalyst (σ,f)to the catalyst (σ◦(i j),f◦(i j)) is a sign-reversing involution without fixed points. Sketch of proof. It is enough to show that f(i)is an arc in both P(j,σ(i)) and P(i,σ(i)). Observe that if Ais connected, then i,jand alie in one connected component of the graph obtained by deleting from Tedge {a,b}, while σ(i),σ(j)and blie in the other one. See Figure 3. Determinant of the distance matrix of a tree 5 •i σ(i)•i(σ◦(i j)) (j) •a b • • a b • j σ(j)•j(σ◦(i j)) (i)• f(i) f(j) (f◦(i j))(j) (f◦(i j))(i) Figure 3: Involution ϕacting on a zero-sum connected arrowflow A. On the other hand, when Ais disconnected, then P(j,σ(i)) and P(i,σ(i)) differ in exactly one arc, either (i,j)or (j,i). Therefore, since f(i)is neither of them, we conclude that f(i)belongs to both paths. See Figure 4. σ(j)• • (σ◦(i j))(i)• • •i j • • i j • •σ(i)• • (σ◦(i j))(j)• f(j) (f◦(i j))(i) f(i)(f◦(i j))(j) Figure 4: Involution ϕacting on zero-sum disconnected arrowflow A. 5 Unital arrowflows Where we rely on the Lindström–Gessel–Viennot Lemma to compute the signed sum of all catalysts in a unital arrowflow class. We rely on the following version of the Lindström–Gessel–Viennot lemma here. Lemma 5.1 (Lindström [8], Gessel–Viennot [5]).Let Rbe an acyclic directed graph. Distinguish two sequences of nodes (v(1), . . . , v(n)) and (v0(1), . . . , v0(n)) with no repeated nodes in either of them. Let Pbe the set of all sequences of paths (P1,..., Pn)for which there exists a permutation σP∈Snsuch that, for each i in [n], the path Pistars at v(i)and finishes at v0(σ(i)). Then, ∑ (P1,...,Pn)∈P sgn(σP) = ∑ (P1,...,Pn)∈P non-intersecting sgn(σP). We break down our argument into three parts. First, we prepare for the application of the Lindström–Gessel–Viennot Lemma and create an acyclic directed graph, the route map RA, from any unital arrowflow Aon T. Subsequently, we establish a sign-preserving bijection that sends each catalyst in C(A)to a family of npaths on RA, which we refer to as n-paths. The application of the Lindström–Gessel–Viennot Lemma reduces our original quest to the problem of finding a description of the non-intersecting n-paths. Finally, 6E. Briand, L. Esquivias, Á. Gutiérrez, A. Lillo, M. Rosas we establish that in each unital arrowflow class, there exists exactly one catalyst κthat generates a non-intersecting n-path, and that its underlying permutation of κis always an n-cycle. Therefore, the sole surviving catalyst, has sign (−1)n−1. 5.1 The route map RA. To construct RA, the route map of T, we proceed in several steps. First, we use arrowflow Ato define a plane rooted directed tree T0. Then, we define the Southern hemisphere, an acyclic directed graph; and its anti-isomorphic counterpart, the Northern hemisphere. Finally, we add bridges connecting both hemispheres and pointing from South to North. Step 1. Construct a rooted directed tree A0from A. Let e={a,b}be the edge of Tconnecting the two vertices appearing in the repeated edge of A. We construct a rooted directed tree A0from Aby adding a new vertex ras a root and substituting the arcs (a,b)and (b,a)by (r,b)and (r,a)respectively. This construction induces a bijection between arcs of Aand A0. An arc of A0will be said to be ascending if it points to the root, and descending if it points away from the root. A child node uof a parent node vis termed ascending when the associated arc for the edge {u,v}is ascending, and descending when it is descending. See Figures 5(a) and (b). We denote the underlying undirected rooted tree of A0by T0. Step 2. Give a compatible plane structure to the rooted directed tree A0. A plane structure for A0is said to be compatible if for each node vwith children u1, . . . , uk, every ascending child of vlies to the left of every descending child. In general there exist multiple compatible plane structures on A0. We just choose one of them. See Figure 5(c). (a) (b) (c) 1 2 3 4 5 6 7 8 9 r 1 3 2 64 7 9 8 5 r 1 3 2 54 8 9 7 6 Figure 5: (a) A unital arrowflow Awith repeated edge {1,2}.(b) The rooted directed tree A0with root r.(c) A compatible plane structure for A0. The underlying rooted tree T0inherits a plane rooted tree structure. The neighbors of a vertex iof T0are ordered starting with the children of iin increasing order (as in the plane structure of T0), and ending with the parent. Determinant of the distance matrix of a tree 7 Step 3. Construct the Southern hemisphere of T0. The Southern hemisphere S(T0)of an undirected plane rooted tree T0is a directed multigraph whose vertex set is composed of three types of nodes (v-node, e-node, and s-node). Each node iof T0, including the root, contributes with a node v(i). Each edge {i,j}of T0, contributes two nodes e(i,j)and e(j,i). Finally, we add two nodes si(jk−1,jk)and si(jk,jk−1)for each vertex iof T0and each pair of consecutive neighbors jk−1,jkof i. See Figure 6. The arcs of the route map connect these nodes in a natural way, as to allow one to understand the paths of T0as paths in the route map. The explicit construction of the set of arcs can be daunting, but these arcs do not need to be included in the graphical representations of S(T0)as they can be inferred from the set of nodes. To construct the set of arcs of S(T0)we add, for each i, two arcs between s-nodes for each three consecutive neighbors jk−1,jk,jk+1, an arc (v(i),si(j1,j2))for each node i that is not a leaf, and an arc (v(i),e(i,j1))for each node i. Additionally, from each e-node e(j,i)there is an arc to (at most) two s-nodes around i, and conversely from each s-node si(jk,jk+1)to its corresponding e(i,jk+1)node. (a) (b) (c) rr 1 3 2 54 8 9 7 6 r 1 3 2 54 8 9 7 6 r 1 3 2 54 8 9 7 6 Figure 6: Highlighted, the sets of (a) v-nodes, (b) e-nodes, and (c) s-nodes of S(T0). Step 4. Construct the Northern hemisphere, an anti-isomorphic copy of the Southern hemisphere. Let T0be an undirected plane rooted tree, let T0 0be its mirror image; a copy of T0in which local orders are inverted. The Northern hemisphere N(T0)of T0is constructed from S(T0 0)by replacing each arc (v(i),e(i,j1))by the arc (e(j1,i),v(i)), and, whenever iis not a leaf, replacing arc (v(i),si(j1,j2))by the arc (si(j2,j1),v(i)). We denote nodes of N(T0)using primed letters. Step 5. Construct the route map RA. The route map RAof the unital arrowflow Ais the directed multigraph obtained by adding to S(T0)∪ N (T0)an arc (e(u,v),e0(u,v))for each arc (u,v)of A0. These arcs are referred to as the bridges between hemispheres of RA. The key property of the route map RAis that it is always acyclic. The Southern hemisphere S(T0)is acyclic because any cycle in S(T0)would induce a cycle in the rooted 8E. Briand, L. Esquivias, Á. Gutiérrez, A. Lillo, M. Rosas plane tree T0. The Northern hemisphere N(T0)is acyclic because it is an anti-isomorphic copy of S(T0). Finally, the route map is acyclic because all the bridges point from South to North. 5.2 Catalyst and n-paths. Let Abe a unital arrowflow, and (σ,f)be a catalyst in C(A). Let Λibe the unique path of RAgoing from v(i)to v0(σ(i)) and passing through the bridge (e(ui,vi),e0(ui,vi)), where (ui,vi)is the arc of A0defined by f(i). See Figure 7. (a) (b) r 1 3 2 54 89 7 6 r′ 1′ 3′ 2′ 5′ 4′ 8′9′ 7′ 6′ Figure 7: (a) A path P(9, σ(9) = 1)marked at f(9) = (4,1).(b) The path Λ9of RA. We define the n-path induced by catalyst κ= (σ,f)on the route map RAas Λ(κ) = {Λ1, . . . , Λn}, and say that κhas been lifted to the n-path Λ(κ). One can recover the permutation σfrom Λ(κ). Thus we define sgn(Λ(κ)) as sgn(σ). Example 5.2. Let κbe the catalyst of Figure 1(a). Figure 8(b) illustrates the n-path induced by κ, where we mark path Λiwith subscript i. Moreover, since each node in the route map belongs to at most one path, it is an example of a non-intersecting n-path. (a) (b) r 1 3 2 54 8 9 7 6 1 5 1 5 3 9 6 2 5 8 47 7 9 5 1 1 1 4 7 9 2 5 r′ 1′ 9 3′ 5 2′ 6 5′ 2 4′ 8 8′ 39′ 7 7′ 4 6′ 1 3 5 8 8 3 6 1 5 1 3 5 3 9 8 3 4 7 6 1 2 Figure 8: (a) A catalyst and (b) its induced n-path Λ(κ) = {Λ1, . . . , Λn}. We say that an n-path is full when every bridge (e(u,v),e0(u,v)) belongs to exactly one of its paths. Since any n-path that is not full must contain an intersection at some bridge, non-intersecting n-paths are always full. Moreover, the lifting of any catalyst belonging to a unital arrowclass is always full. Lemma 5.3. The operation of lifting defines a permutation-preserving bijection between the set of catalysts with unital arrowflow A and the set of full n-paths of RA. Determinant of the distance matrix of a tree 9 Sketch of proof. To prove that the lifting map is a bijection, we define its inverse. Any n-path Pdefines a permutation σ, where Piis a path from v(i)to v0(σ(i)). On the other hand, we use the bridges of Pto define a map f:[n]→E±. If the arc edefining the bridge of Pidoes not include the root, we define f(i) = e. Otherwise, we let f(i)be the repeated edge with the appropiate orientation. It can be shown that (σ,f)∈C(A) and, that the map we just defined is the inverse of the lifting map. Since the underlying permutation of a catalyst is the permutation induced by its lifting, we conclude that the lifting map is a permutation-preserving bijection. Lemma 5.3 allows us to rewrite Equation (3.2) as ∑κ∈C(A)sgn(κ) = ∑sgn(Λ), where the second sum is taken over the set of full n-paths on RA. 5.3 There is an unique catalyst inducing a non-intersecting n-path. Moreover, its underlying permutation is always an n-cycle. Proposition 5.4. Let A be a unital arrowflow on T. Consider all n-paths in the route map RA induced by catalysts in C(A). There exists precisely one catalyst inducing a non-intersecting n-path in RA. Its underlying permutation is an n-cycle. Therefore, its sign is (−1)n−1. Sketch of proof. Fix a plane rooted tree A0and let Λbe an n-path. Assume Λis the lift of catalyst (σ,f). Consider the set Econsisting of the e-nodes appearing in the paths of Λ. We can show that Euniquely determines the catalyst (σ,f). On the other hand, for each arc (i,j)of A0, the set Econtains both e(i,j)and e0(i,j). Furthermore, if Λis nonintersecting, a counting argument allows us to show that (i,j)is ascending if and only if Econtains e0(j,i), and descending if and only if it contains e(j,i). This gives uniqueness. The argument concludes by noting that the underlying permutation of the sole catalyst inducing a non-intersecting n-path is always an n-cycle, and that the depth-first search algorithm allows us to explicitly describe this cycle, as illustrated in Figure 9. r 1 3 2 54 8 9 7 6 1 2 3 4 5 67 8 9 10 11 12 13 14 15 16 17 18 Figure 9: Applying the depth-first search algorithm to this rooted tree results in the word r13148474941r26252r, which we identify with the cycle (384791625).