1999 Doctor of Philosophy Professor Peter Doyle Professor Adriano Garsia
Professor Mark Haiman
Professor Audrey Terras
Professor Mihir Bellare
Professor Ramamohan Paturi 6 B.S. (Yale University) 1993
M.A. (University of California, San Diego), 1995 Mathematics San Diego

# How to encode a tree

Sally Picciotto

###### Abstract

We construct bijections giving three “codes” for trees. These codes follow
naturally from the Matrix Tree Theorem of Tutte and have many advantages over
the one produced by Prüfer in 1918. One algorithm gives explicitly a bijection
that is implicit in Orlin’s manipulatorial proof of Cayley’s formula (the
formula was actually found first by Borchardt). Another is based on a proof of
Knuth. The third is an implementation of Joyal’s pseudo-bijective proof of the
formula, and is equivalent to one previously found by Eğecioğlu and Remmel. In
each case, we have at least two algorithms, one of which involves hands-on
manipulations of the tree while the other involves a combinatorial and linear
algebraic manipulation of a matrix.

To

Ryan Garibaldi

Jean Isaacs

and Dalit Baum

who have witnessed (and greatly assisted in)

my growth over the last few years.

_“I’m afraid you misunderstood… I said I’d like a mango.”–G. Larsen_

###### Contents

  1. 0 Introduction
    1. 1 Definitions
    2. 2 Some History
    3. 3 The Prüfer Code
      1. 1 An example
      2. 2 Finding the tree for a code
    4. 4 The Matrix Tree Theorem
    5. 5 Linear Algebra Setup
  2. 1 The Happy Code
    1. 1 The Sets
    2. 2 The involutions
      1. Defining $\phi_{0}$
      2. Defining $\phi_{i}^{\prime}$ for $0\leq i\leq n-1$
      3. Defining $\phi_{i}$ for $1\leq i\leq n$
      4. Defining $\phi_{n}^{\prime}$ and $\phi_{n+1}$
    3. 3 Garsia and Milne’s Involution Principle
    4. 4 An example
  3. 2 The Blob Code
    1. 1 Orlin’s ideas
    2. 2 The sets
    3. 3 The involutions
      1. Defining $\mu_{0}^{\prime}$
      2. Defining $\rho_{i}$ for $1\leq i\leq n-1$
      3. Defining $\rho_{i}^{\prime}$ for $1\leq i\leq n-1$
      4. Defining $\kappa_{i}$ for $1\leq i\leq n-1$
      5. Defining $\kappa_{i}^{\prime}$ for $1\leq i\leq n-2$
      6. Defining $\kappa_{n-1}^{\prime}$
      7. Defining $\mu_{i}$ and $\mu_{i}^{\prime}$ for $1\leq i\leq n-1$
      8. Defining $\rho_{n}$
    4. 4 How to Find the Blob Code
      1. 1 An example
        1. Step 1
        2. Step 2
        3. Step 3
  4. 3 Tree Surgery for the Blob Code
    1. 1 Tree Surgery Algorithm
      1. Step 1
      2. Step 2
      3. Step 3
    2. 2 Tree Surgery Is A Bijection
    3. 3 The Two Methods Give the Same Blob Code
  5. 4 Tree Surgery for the Happy Code
    1. 1 Tree Surgery Algorithm
    2. 2 An Example
    3. 3 Tree surgery is a bijection
    4. 4 The Two Methods Give the Same Happy Code
      1. 1 A Lemma
      2. 2 The proof
  6. 5 The Dandelion Code
    1. 1 The Sets
    2. 2 The Involutions
    3. 3 How to Find the Dandelion Code
      1. 1 An example
    4. 4 Tree Surgery Method
    5. 5 The Two Methods Give the Dandelion Code
  7. 6 Permutations of the naïve code
    1. 1 The Happy Code: an easier method
    2. 2 The Dandelion Code: an easier method
  8. 7 Relationship between Codes
  9. 8 Conclusion
    1. 1 The codes are distinct
    2. 2 Clever weighting of edges
    3. 3 Applications and more questions

###### Acknowledgements.

It is probably impossible to thank everyone to whom I am grateful, but I’m
going to give it my best shot. First of all, I thank Peter Doyle for his
ability to spark my interest in the questions I explored in my research and
also, just as importantly, for his patience. His enthusiasm is contagious and
his nontraditional teaching methods inspire me. With another advisor, I might
never have completed this degree. I am indebted to the other faculty members
on my committee as well. Professor Garsia pointed me to important papers and
offered valuable insights at several points in my research, and his courses
have helped me to understand the beauty of both bijective and “manipulatoric”
proofs. His Involution Principle was obviously an important foundation for my
research, without which my own results would not have been possible. Professor
Haiman’s “applied algebra” qualifying class initially introduced me to
combinatorics, and he suggested ways that my research might relate to
questions he and other combinatorists investigate. Professor Terras has been
an unflagging source of encouragement, inspiration, and comfort. Professor
Bellare was my supervisor for one of my favorite TAing assignments at UCSD and
also suggested future directions for my career. In addition to my committee,
courses and papers from (and discussions with) Jeff Remmel, as well as
discussions with Glenn Tesler, Jeb Willenbring, and Mike Zabrocki, aided in my
understanding of the subject. Mike Zabrocki actually read my first rough draft
of the thesis and offered dozens of helpful suggestions. Furthermore, the Math
Department staff was of great assistance on numerous occasions, so I thank
Lois Stewart, Joe Keefe, Wilson Cheung, Judy Gregg, Zee Collins, Lee Montaño,
and Mike Stegen, plus Nieves Rankin and Kathy Johns from CSE. Professors
Harold Stark and Ruth Williams have both helped me to develop my teaching
abilities by visiting my classes and making suggestions. Beyond mathematics,
there are many people who have vastly improved my quality of life during
graduate school. I wish to express my deep appreciation.

Born, San Francisco, California

B. S., _cum laude_ , Yale University

Teaching assistant, Department of Mathematics, University of California San
Diego

M. A., University of California San Diego

Lecturer, Department of Mathematics, University of California San Diego

Choreographed “Near The Sand Comets” for “New Works” dance concert, University
of California San Diego

Teaching assistant, Department of Computer Science and Engineering, University
of California San Diego

Ph. D., University of California San Diego

##  Chapter 0 Introduction

This dissertation is a contribution to the history of progressing from
algebraic proofs to bijective proofs. In particular, for theorems involving
graphs, there is a long history of proofs using matrices. We start with linear
algebra, but automatically something is going on beneath the surface that
turns out to be a simple bijection.

###  1 Definitions

###### Definition 1

A directed graph is a quadruple $G=(V,E,\alpha,\omega)$, where the elements of
the set $V$ are called vertices and the elements of the set $E$ are called
edges, and $\alpha$ and $\omega$ are the boundary maps from $E$ to $V$. If
$e\in E$, then $\alpha(e)\in V$ is the initial vertex or tail of $e$ and
$\omega(e)\in V$ is the terminal vertex or head of $e$.

Note that this definition allows for multiple edges with tail $v_{1}$ and head
$v_{2}$. An edge in a directed graph can be represented by an arrow pointing
from the initial vertex to the terminal vertex.

Example:

241356879$\hookleftarrow$e0$\hookleftarrow$

Here the vertices are labelled with integers. The edge labelled e satisfies
$\alpha({\rm e})=9$ and $\omega({\rm e})=6$. An edge is said to point from or
out of its tail and point to or into its head. This dissertation deals with
directed graphs whose vertices are labelled $0,1,\dots,n$. Sometimes the edges
have weights associated to them. Sometimes we refer to a directed graph as
simply a graph.

###### Definition 2

A function $W:E\to S$, where $S$ is any set, defines a weight for each edge.

###### Definition 3

The indegree of a vertex in a directed graph is the number of edges of which
the vertex is the head, and the outdegree is the number of edges of which the
vertex is the tail.

###### Definition 4

A path in a directed graph is an alternating sequence of vertices and edges
$v_{1},e_{1},v_{2},e_{2},\dots,e_{4},v_{r+1}$ where $v_{i}$ is the tail of the
edge $e_{i}$ and $v_{i+1}$ is the head of the edge $e_{i}$.

###### Definition 5

A cycle in a directed graph is a closed path (a path where $v_{1}=v_{r+1}$). A
cycle with only one edge, $v\to v$, is called a loop.

###### Definition 6

The complete digraph (with a given number of vertices) is a directed graph
with exactly one edge $v_{1}\to v_{2}$ for each pair of vertices.

###### Definition 7

A rooted tree is a digraph with a unique path connecting each vertex to the
(unique) vertex with outdegree 0 called the root. Any vertex whose indegree is
$0$ is called a leaf.

Unless otherwise noted, all trees are rooted at 0. Any “free tree” (an
undirected connected graph with no cycles) can be transformed uniquely into a
tree rooted at 0 by directing all edges toward 0.

Example:

04527631

In this tree, the leaves are 1, 3, 5, and 7.

###### Definition 8

The weight of a tree is the product of the weights of its edges.

In the example above, if the weight of the edge $i\to j$ is $a_{ij}$ then the
weight of the tree is $a_{16}a_{24}a_{32}a_{40}a_{54}a_{62}a_{74}$.

###### Definition 9

A spanning tree of a graph $G$ is a tree whose vertices are the same as the
vertices of $G$ and whose edges are a subset of the edges of $G$.

###### Definition 10

A functional digraph is a directed graph where each vertex is the tail of
exactly one edge.

In a functional digraph, there may be many edges pointing into a vertex but
only one pointing out. A functional digraph is a collection of disjoint cycles
whose vertices are roots of trees leading into them.

Example: This is a functional digraph:

2413568790$\hookleftarrow$

A functional digraph represents a function
$f:\\{0,1,2,\dots,n\\}\to\\{0,1,2,\dots,n\\}$, where $f(i)=j$ if and only if
the edge $i\to j$ is in the digraph.

###### Definition 11

Since each vertex $i$ ($\neq 0$ in a rooted tree) in a functional digraph is
the initial vertex for exactly one edge, it makes sense to define
$\verb+succ+(i)=j$ to be the terminal vertex of the edge $i\to j$ in the (tree
or) functional digraph.

In the tree example above, $\verb+succ+(6)=2$; in the functional digraph,
$\verb+succ+(6)=5$.

###### Definition 12

A happy functional digraph is a functional digraph without an edge out of $0$,
and in which $1$ is in the same connected component as $0$.

A happy functional digraph is a collection of trees leading into disjoint
cycles, together with a tree rooted at 0 and also containing 1.

###### Definition 13

An ascent is an edge $i\to j$ where $j>i$.

###### Definition 14

An Escher cycle is a cycle in which each edge except one is an ascent.

Example:

925678

Note that each vertex is smaller than its successor, except for the greatest
vertex in the cycle, 9.

###### Definition 15

The “naïve code” for a tree is defined to be

${\rm na\ddot{\i}ve}=(\verb+succ+(1),\verb+succ+(2),\dots,\verb+succ+(n)).$

The “naïve code” requires no work to find, but not every $n$-tuple corresponds
to a tree. For example, the naïve code (3,2,0,5,4) would correspond to the
following graph:

1302$\hookleftarrow$45

This graph is not a tree because it has a loop and a cycle. It is, however, a
happy functional digraph.

We borrow the notation of discrete geometry for some of the proofs in this
paper:

###### Definition 16

A signed set $S=S^{+}\sqcup S^{-}$, where $\sqcup$ represents the disjoint
union, is an oriented zero-dimensional complex (that is, a collection of
distinguishable points that can be partitioned into two subsets, one
containing the elements considered “positive” and the other containing the
elements considered “negative.”).

###### Definition 17

Let $T=T^{+}\sqcup T^{-}$ and $S=S^{+}\sqcup S^{-}$ be two signed sets. Their
difference is defined to be the disjoint union of the sets, with the following
signs on elements of the union:

$(S-T)^{+}=S^{+}\sqcup T^{-}{\text{ and }}(S-T)^{-}=S^{-}\sqcup T^{+}.$

Example: If $S=\\{a,b,c,-d,-e\\}$ and $T=\\{x,-y,-z\\}$, then

$S-T=\\{a,b,c,y,z,-d,-e,-x\\}.$

###### Definition 18

The Kronecker delta function $\delta_{xy}$ takes value 1 if $x=y$ and 0
otherwise.

###### Definition 19

An involution $\phi:S\to S$ is a map on a signed set $S$ that satisfies
$\phi\circ\phi(x)=x$ for all $x\in S$.

###### Definition 20

An involution is sign-reversing if for any $x\in S^{+}$, $\phi(x)\in S^{-}$
and for any $x\in S^{-}$, $\phi(x)\in S^{+}$.

A sign-reversing involution does not have any fixed points.

###  2 Some History

In 1860, Borchardt [1] discovered through evaluation of a certain determinant
(namely, the principal (0,0)-minor of the matrix Tutte used a hundred years
later, see §4) that the number of labelled trees is $\left(n+1\right)^{n-1}$.
Cayley [2] independently derived this formula in 1889, and his short paper on
the topic alludes to a bijection. However, the invention of a coding algorithm
for trees, by Prüfer in 1918, was the first combinatorial proof that this is
the formula for the number of trees. His idea was that any tree can be encoded
by a vector: an ordered $(n-1)$-tuple of labels chosen from $0$ to $n$. This
is done in such a way that the tree can be recovered from the code and vice
versa. The number of possible codes (which is of course equal to the number of
possible trees) is $(n+1)^{n-1}$.

###  3 The Prüfer Code

In 1918, Prüfer [9] gave the following bijective proof of this formula.

Given a labelled tree, we suppose that the least leaf is labelled $i_{1}$, and
that $\verb+succ+(i_{1})=j_{1}$. Remove $i_{1}$ and its edge from the tree,
and let $i_{2}$ be the least leaf on the new tree, with
$\verb+succ+(i_{2})=j_{2}$. If we repeat this process until there are only two
vertices left, the Prüfer code $(j_{1},\dots,j_{n-1})$ uniquely determines the
tree.

To recover the tree from any $(n-1)$-tuple, we note that for each vertex
except the root, the number of occurrences of that label in the Prüfer code is
equal to the indegree of that vertex. The number of occurrences of $0$ in the
code is one less than the indegree of 0. There must be at least two labels
that don’t appear in the code, since there are $n+1$ vertices and only $n-1$
entries in the code. Any nonzero vertex not occurring in the code is a leaf in
the original tree, so we know that the least one, $i_{1}$, has
$\verb+succ+(i_{1})=j_{1}$, the first vertex in the code. We can also tell
whether any new leaves were formed when $i_{1}$ was removed because we know
the indegree of $j_{1}$. Step by step, from beginning to end, we can
reconstruct each edge of the tree.

Hence, the Prüfer code gives a bijection between trees with $n+1$ vertices and
$(n-1)$-tuples of the vertex-labels. Since the number of $(n-1)$-tuples is
clearly $(n+1)^{n-1}$, this bijection proves the formula that Borchardt
discovered.

However, the algorithm is a bit unnatural. The inverse does not undo the steps
in the backwards order; we have to look at the overall code and decipher what
had to be true in the tree by starting from the beginning of the code and
working our way to the end.

####  1 An example

Consider the tree:

04527631

with leaves $\\{1,5,3,7\\}$. Step by step, we build up the code and remove
leaves from the tree. First, we see that $1$ is the least leaf, so we write
down $\verb+succ+(1)$ and remove $1$ from the tree.

0452763Code so far=(6)

Here, the removal of $1$ created a new leaf. Now the leaves are
$\\{5,6,3,7\\}$, so the new least leaf is $3$.

045276Code so far=(6,2)

The next leaf to fall off of the tree is $5$, leaving us with the following
tree and code:

04276Code so far=(6,2,4)

No new leaves have been created, so the smallest leaf now is $6$ and we remove
it.

0427Code so far=(6,2,4,2)

Now that we’ve removed both $3$ and $6$, the indegree of $2$ is $0$. We remove
$2$ to obtain:

047Code so far=(6,2,4,2,4),

and finally:

04Prüfer Code=(6,2,4,2,4,4).

####  2 Finding the tree for a code

To get the other direction of the bijection, we start by counting occurrences
of each vertex label in the code to find the list of indegrees. (The indegree
of $0$ is one greater than the number of occurrences of $0$ in the code.) For
the code (6,2,4,2,4,4) we have

Vertex | Indegree
---|---
0 | 1
1 | 0
2 | 2
3 | 0
4 | 3
5 | 0
6 | 1
7 | 0

The four vertices with indegree of 0 are the leaves on the original tree. So
far, our knowledge consists of this:

0246$L_{1}=\\{1,3,5,7\\}$$P_{1}=(6,2,4,2,4,4)$

where $P_{i}$ is the code at step $i$ and $L_{i}$ is the Leaf Set at step $i$.
The Leaf Set $L_{i}$ consists of all the vertices whose labels are not listed
in $P_{i}$ and whose outgoing edges have yet to be determined. It is actually
the set of vertices that are leaves after all of the previous “least leaves”
have been removed.

Since the smallest leaf in this example is 1, and we know the code starts with
6, we can see that the edge whose head is 6 must have tail 1. We also see that
removing 1 from the tree created a new leaf, 6, so we add 6 to the Leaf Set.

02461$L_{2}=\\{3,5,6,7\\}$$P_{2}=(2,4,2,4,4)$

The least leaf of $L_{2}$ is 3, so its edge points to 2, the first element in
$P_{2}$. Removing 3 does not create a new leaf because 2 appears twice in
$P_{2}$.

023461$L_{3}=\\{5,6,7\\}$$P_{3}=(4,2,4,4)$

The least leaf of $L_{3}$ is 5. It will point at 4, and removing 5 will not
create a new leaf.

0234561$L_{4}=\\{6,7\\}$$P_{4}=(2,4,4)$

Once we remove 5, the smallest element of $L_{4}$ is 6, so there is an edge
$6\to 2$. Also, removing 6 will turn 2 into a leaf, since this is the only
occurrence of 2 in $P_{4}$.

0261345$L_{5}=\\{2,7\\}$$P_{5}=(4,4)$

The smallest element of $L_{5}$ is 2, so it must point at 4. Since there is
still an unaccounted-for edge into 4, removing 2 does not make 4 into a leaf.
Thus 7 will be the only leaf left after that step.
0261345$L_{6}=\\{7\\}$$P_{6}=(4)$

Now, since 7 is the smallest leaf, its edge has head at 4. From that we can
also conclude that the edge $4\to 0$ is the remaining edge in the tree. In
general, whichever vertex did not yet have an outgoing edge will have to point
to $0$ at the end.

02613457

Given the code, we were able to reconstruct the tree, and this can be done no
matter what $(n-1)$-tuple we are given. It is clear that this algorithm is the
inverse of the algorithm given by Prüfer.

###  4 The Matrix Tree Theorem

In 1948, Tutte [13] associated a matrix $A_{T}$ to the complete loopless
directed graph on vertices $\\{0,\dots,n\\}$, with edge from $i$ to $j$ of
weight $a_{ij}$. The general matrix is $A_{T}=(A_{ij})$, with $i$ and $j$
indexed from $0$ to $n$:

$A_{ij}~{}=~{}\left\\{\begin{array}[]{ll}-a_{ij}&i\neq j\\\\[4.30554pt]
\displaystyle{\sum_{k\neq i,0\leq k\leq n}}a_{ik}&i=j.\end{array}\right.$

The diagonal entry in row $i$ is the sum of the weights of the edges with tail
at $i$. The row sums of such a matrix are zero, so the determinant of the
matrix is zero. However, the following result by Tutte is very useful. Denote
by $A$ the $n\times n$ submatrix of $A_{T}$ obtained by crossing out its
zeroth row and column.

######  Theorem 1 (Matrix Tree Theorem)

The determinant of $A$ is the sum of the weights of all spanning trees (rooted
at vertex $0$) of the graph.

Zeilberger [14] published a nice bijective proof, also discovered
independently by Garsia. A bijective proof of a more general version of the
theorem is due to Chaiken [3]. We will think of the entries in our matrices as
being indeterminates. When the $i,j$-entry of the matrix (not on the diagonal)
consists of a sum of $k$ indeterminates, the matrix corresponds to a graph
with $k$ edges $i\to j$, each having monomial weight. Note that if $a_{ij}$ is
an integer, it can represent the number of edges $i\to j$ in a graph (if
$a_{ij}=0$, then there is no edge $i\to j$). Then $\det(A)$ is the number of
spanning trees of the graph.

Throughout this dissertation we will be defining signed sets that come from
matrices. Each element of a matrix set is an array consisting of exactly one
monomial entry from the matrix in each row and each column. Each array comes
with the sign corresponding to the array position in the determinant. An
element of a matrix set can be thought of as a signed permutation times a
diagonal matrix. The matrix set corresponding to a matrix $M$ consists of all
possible such arrays.

The matrix $\hat{A}=(a_{ij})$ (where $i$ and $j$ are indexed from $0$ to $n$)
has the indeterminate weight corresponding to the edge $i\to j$ in its
$i,j$-entry. If we formally subtract this matrix from the diagonal
$(n+1)\times(n+1)$ matrix $\hat{D}$ whose $i^{\rm th}$ diagonal entry is
$\sum_{j=0}^{n}a_{ij}$, without simplifying, then we obtain a matrix
$\hat{D}-\hat{A}$ whose row sums are zero: this matrix corresponds to the
complete directed graph with loops. It differs from Tutte’s matrix only by the
presence of $a_{ii}-a_{ii}$ in the $i^{\rm th}$ diagonal entry–essentially we
have added zero to each diagonal entry in Tutte’s matrix. Obviously this
doesn’t change the $(0,0)$-minor; loops never appear in trees.

Zeilberger’s bijective proof [14] of the Matrix Tree Theorem hinges on the
idea that every functional digraph with a cycle corresponds to an array some
of whose entries occur both on the diagonal and off the diagonal of Tutte’s
submatrix $A$, with opposite signs. In the determinant, these terms would
cancel. He effectively introduces a surjective map from the matrix set
corresponding to $A$ to the set of digraphs representing functions from
$\\{1,2,\dots,n\\}$ to $\\{0,1,\dots,n\\}$ according to the following rule:
The entry in row $i$ of the array represents the edge from $i$, and if this
entry is $\pm b_{j}$, either on or off the diagonal, then the edge is $i\to
j$.

Example: For $n=2$, the submatrix of $A$ is
$\left[\begin{smallmatrix}a_{10}+a_{12}&-a_{12}\\\
-a_{21}&a_{20}+a_{21}\end{smallmatrix}\right]$. The matrix set is

$\left\\{\left[\begin{smallmatrix}a_{10}&\\\
&a_{20}\end{smallmatrix}\right],\left[\begin{smallmatrix}a_{10}&\\\
&a_{21}\end{smallmatrix}\right],\left[\begin{smallmatrix}a_{12}&\\\
&a_{20}\end{smallmatrix}\right],\left[\begin{smallmatrix}a_{12}&\\\
&a_{21}\end{smallmatrix}\right],\left[\begin{smallmatrix}&-a_{12}\\\
-a_{21}&\end{smallmatrix}\right]\right\\}$

and the surjective map is given in the following diagram:

$\begin{bmatrix}a_{10}&\\\
&a_{20}\end{bmatrix}\longrightarrow$102$\begin{bmatrix}a_{10}&\\\
&a_{21}\end{bmatrix}\longrightarrow$102$\begin{bmatrix}a_{12}&\\\
&a_{20}\end{bmatrix}\longrightarrow$102$\begin{bmatrix}a_{12}&\\\
&a_{21}\end{bmatrix}\longrightarrow$102$\begin{bmatrix}&-a_{12}\\\
-a_{21}&\end{bmatrix}$

Note that the only graph with a cycle gets mapped to twice. Since we are only
interested in counting trees, we can eliminate graphs with cycles and instead
map the two preimages to one another.

Using these ideas, Zeilberger constructs what amounts to a sign-reversing
involution on the matrix set corresponding to $A$ minus the set of trees.

In our case, we think of $A$ as being morally equal to $\hat{D}-\hat{A}$, and
“on the diagonal” as meaning “occurring in $\hat{D}$” and “off the diagonal”
as meaning “occurring in the matrix $-\hat{A}$.” By defining these terms in
this way, we allow for loops. Most of our algorithms for finding codes using a
matrix method will require us to know how to “toggle the diagonality” of a
cycle. Toggling the diagonality of a cycle in an array in a matrix set simply
entails finding the unique array in the same set that satisfies two
conditions: (1) the variable corresponding to any edge not in the cycle is in
the same location as in the original array, and (2) any variable corresponding
to an edge that is in the cycle occurs within the same row but has the
opposite “diagonality” from its location in the original array. Toggling the
diagonality of a cycle is a sign-reversing involution on the matrix set’s
subset corresponding to graphs containing cycles. An off-diagonal cycle will
always come with a negative sign because a cycle of odd length has a
permutation sign of +1, but an odd number of negative terms; a cycle of even
length has an even number of negative terms but a negative sign.

Example:

02413$\longleftrightarrow$$\begin{bmatrix}a_{13}&&&\\\ &a_{24}&&\\\
&&a_{34}&\\\
&&&a_{41}\end{bmatrix}\longleftrightarrow\begin{bmatrix}&&-a_{13}&\\\
&a_{24}&&\\\ &&&-a_{34}\\\ -a_{41}&&&\end{bmatrix}$.

The graph above contains a cycle; the elements of the matrix set corresponding
to the (0,0)-minor of $\hat{D}-\hat{A}$ that correspond to this tree are both
above: the one on the left consists entirely of entries from $\hat{D}$ while
the one on the right has some entries from $-\hat{A}$. $a_{24}$ corresponds to
the edge $2\to 4$ which is not in a cycle, so it appears on the diagonal in
both arrays, but the cycle $(134)$ could appear either on or off the diagonal.
The sign of the first array is +1 because all entries are on the diagonal. The
second array turns out to be negative because the 3-cycle has sign +1 but
there are 3 negative entries.

For loops, it is a little bit less clear:

Example:

02143$\hookleftarrow$$\longleftrightarrow\begin{bmatrix}a_{10}&&&\\\
&a_{20}&&\\\ &&a_{33}&\\\
&&&a_{41}\end{bmatrix}\longleftrightarrow\begin{bmatrix}a_{10}&&&\\\
&a_{20}&&\\\ &&-a_{33}&\\\ &&&a_{41}\end{bmatrix}$.

Here, although the entries are all apparently on the diagonal, we think of the
diagonality of the loop at 3 as having changed from the first matrix to the
second. The first array consists of entries only from $\hat{D}$ while the
$-a_{33}$ in the second one is an entry from $-\hat{A}$.

If a graph has more than one cycle (including loops), we raise the issue of
which cycle’s diagonality gets toggled. Zeilberger arbitrarily chose to move
the cycle with the smallest element in it; we arbitrarily choose to move the
cycle with the largest. All choices are equally valid but result in slightly
different codes. The choice of the largest element in a cycle is consistent
with some tree surgical methods that give the same bijections as our matrix
methods.

###  5 Linear Algebra Setup

If we set $a_{ij}=b_{j}$ for all $i,j$ in Tutte’s matrix $A_{T}$, we get a
matrix with each entry in column $j$ $=-b_{j}$ except on the diagonal. We can
calculate the $(0,0)$-minor using row and column operations.

If we ignore the zeroth row and column, we could find the determinant using
the following operations. We start with the submatrix $A$:

$\det\left[\begin{array}[]{ccc}b_{0}+b_{2}+b_{3}&-b_{2}&-b_{3}\\\
-b_{1}&b_{0}+b_{1}+b_{3}&-b_{3}\\\
-b_{1}&-b_{2}&b_{0}+b_{1}+b_{2}\end{array}\right].$

Subtract row 2 from row 3:

$=\det\left[\begin{array}[]{ccc}b_{0}+b_{2}+b_{3}&-b_{2}&-b_{3}\\\
-b_{1}&b_{0}+b_{1}+b_{3}&-b_{3}\\\
0&-b_{0}-b_{1}-b_{2}-b_{3}&b_{0}+b_{1}+b_{2}+b_{3}\end{array}\right]$

Add column 3 to column 2:

$=\det\left[\begin{array}[]{ccc}b_{0}+b_{2}+b_{3}&-b_{2}-b_{3}&-b_{3}\\\
-b_{1}&b_{0}+b_{1}&-b_{3}\\\ 0&0&b_{0}+b_{1}+b_{2}+b_{3}\end{array}\right]$

Subtract row 1 from row 2:

$=\det\left[\begin{array}[]{ccc}b_{0}+b_{2}+b_{3}&-b_{2}-b_{3}&-b_{3}\\\
-b_{0}-b_{1}-b_{2}-b_{3}&b_{0}+b_{1}+b_{2}+b_{3}&0\\\
0&0&b_{0}+b_{1}+b_{2}+b_{3}\end{array}\right]$

Add column 2 to column 1:

$=\det\left[\begin{array}[]{ccc}b_{0}&-b_{2}-b_{3}&-b_{3}\\\
0&b_{0}+b_{1}+b_{2}+b_{3}&0\\\ 0&0&b_{0}+b_{1}+b_{2}+b_{3}\end{array}\right]$

(Call this last matrix $M$.) Now it is evident (since we have an upper-
triangular matrix) that $\det M=b_{0}\,[b_{0}+b_{1}+b_{2}+b_{3}]^{2}$. In
general, $\det M=b_{0}\,\left[\sum_{j=0}^{n}b_{j}\right]^{n-1}$. The number of
trees is $(n+1)^{(n-1)}$, and it is clear that this is also the number of
terms in $\det M$ (we have an $(n-1)$-fold product of a sum of $n+1$ terms).
Let sequences of the $b_{j}$ as read down the diagonal of the matrix be called
“codes.” One would like to have a bijection relating these codes to trees.
Each array of diagonal entries from $M$ should correspond to a tree.

Note that in a matrix with this much redundancy, there are many different
sequences of row and column operations that can lead to an easily calculated
determinant.

In the course of this research we found that allowing loops was more natural.
Consequently, instead of Tutte’s matrix $A$ we use variations on
$\hat{D}-\hat{A}$ as defined in §4. For our purposes, we will set
$a_{ij}=b_{j}$ in $\hat{A}$ and $a_{ij}=B_{j}$ in $\hat{D}$. At the end of the
long process of row and/or column operations, we set $B_{j}=b_{j}$.

##  Chapter 1 The Happy Code

We can use the Matrix Tree Theorem to find a more “natural” code than the
Prüfer code by expanding on Knuth’s ideas in [7]. As mentioned in §5, we
specialize $a_{ij}$ to be $b_{j}$ in $\hat{A}$ and $B_{j}$ in $\hat{D}$.
Following Knuth, we introduce another indeterminate $\lambda$, which will be a
placeholder, by putting $\lambda-b_{0}$ in the $(0,0)$-entry in the matrix,
calling this new matrix $M_{0}^{\prime}$. We keep in mind that we are
interested in the coefficient of $\lambda$ in the determinant of
$M_{0}^{\prime}$, since it is equal to the $(0,0)$-minor of the original
Matrix Tree Theorem matrix. We will do row operations to form a series of
matrices, all with the same determinant. The coefficient of $\lambda$ in the
final determinant represents the sum of the weights of all the trees, because
that was true of the original matrix; the row operations do not affect that.
The sequence of matrices is formed by subtracting the zeroth row from each of
the other rows, one at a time. (In [7], the row operations are all performed
simultaneously.)

Specifically, we begin with the matrix $M_{0}^{\prime}$ whose $i,j$-entry is
$-b_{j}$ when $i\neq j$ and whose $i^{\rm th}$ diagonal entry is
$-b_{i}+\delta_{i0}\lambda+(1-\delta_{i0})\sum_{j=0}^{n}B_{j}$. (If $B_{j}$ is
set equal to $b_{j}$ then the row sums are zero for rows $1$ through $n$.
Using $B_{j}$ for the diagonal entries enables us to keep track of loops.) Let
$B=\sum_{j=0}^{n}B_{j}$.

$M_{0}^{\prime}=\left[\begin{array}[]{ccccc}\lambda-
b_{0}&-b_{1}&-b_{2}&...&-b_{n}\\\ -b_{0}&B-b_{1}&-b_{2}&...&-b_{n}\\\
.&.&.&...&.\\\ .&.&.&...&.\\\ .&.&.&...&.\\\
-b_{0}&-b_{1}&-b_{2}&...&B-b_{n}\end{array}\right].$

Subtract row $0$ from row $n$, without cancelling anything. Then

$M_{1}=\left[\begin{array}[]{ccccc}\lambda-b_{0}&-b_{1}&-b_{2}&...&-b_{n}\\\
-b_{0}&B-b_{1}&-b_{2}&...&-b_{n}\\\ .&.&.&...&.\\\ .&.&.&...&.\\\
.&.&.&...&.\\\
-\lambda+b_{0}-b_{0}&b_{1}-b_{1}&b_{2}-b_{2}&...&b_{n}+B-b_{n}\end{array}\right].$

The next step consists of arithmetic within entries:

$M_{1}^{\prime}=\left[\begin{array}[]{ccccc}\lambda-
b_{0}&-b_{1}&-b_{2}&...&-b_{n}\\\ -b_{0}&B-b_{1}&-b_{2}&...&-b_{n}\\\
.&.&.&...&.\\\ .&.&.&...&.\\\ .&.&.&...&.\\\
-\lambda&0&0&...&B\end{array}\right].$

Next, subtract row $0$ from row $n-1$, again without cancelling; repeat the
process. The $i^{\rm th}$ step is:

$M_{i}=\left[\begin{smallmatrix}\lambda-
b_{0}&-b_{1}&\dots&-b_{n-i+1}&-b_{n-i+2}&\dots&-b_{n}\\\
-b_{0}&B-b_{1}&\dots&-b_{n-i+1}&-b_{n-i+2}&\dots&-b_{n}\\\
\vdots&\vdots&\ddots&\vdots&\vdots&&\vdots\\\
-b_{0}-\lambda+b_{0}&-b_{1}+b_{1}&\dots&B-b_{n-i+1}+b_{n-i+1}&-b_{n-i+2}+b_{n-i+2}&\dots&-b_{n}+b_{n}\\\
-\lambda&0&\dots&0&B&\dots&0\\\ \vdots&\vdots&&\vdots&\vdots&\ddots&\vdots\\\
-\lambda&0&\dots&0&0&\dots&B\end{smallmatrix}\right],$

where the complicated row is row $n-i+1$. Remember that the matrix is indexed
from 0 to $n$.

$M_{i}^{\prime}=\begin{bmatrix}\lambda-
b_{0}&-b_{1}&\dots&-b_{n-i+1}&-b_{n-i+2}&\dots&-b_{n}\\\
-b_{0}&B-b_{1}&\dots&-b_{n-i+1}&-b_{n-i+2}&\dots&-b_{n}\\\
\vdots&\vdots&\ddots&\vdots&\vdots&&\vdots\\\ -\lambda&0&\dots&B&0&\dots&0\\\
-\lambda&0&\dots&0&B&\dots&0\\\ \vdots&\vdots&&\vdots&\vdots&\ddots&\vdots\\\
-\lambda&0&\dots&0&0&\dots&B\end{bmatrix}$

The last matrix is

$M_{n}^{\prime}=\left[\begin{array}[]{ccccc}\lambda-
b_{0}&-b_{1}&-b_{2}&...&-b_{n}\\\ -\lambda&B&0&...&0\\\ .&.&.&...&.\\\
.&.&.&...&.\\\ .&.&.&...&.\\\ -\lambda&0&0&...&B\end{array}\right].$

The coefficient of $\lambda$ in the determinant of this matrix is

$S=B^{n}-b_{1}B^{n-1}-Bb_{2}B^{n-2}-B^{2}b_{3}B^{n-3}-...-B^{n-1}b_{n},$

where we write each term with its factors in the same order in which their
columns appeared in the final matrix, $M_{n}^{\prime}$.

###  1 The Sets

We define a sequence of signed sets
$A_{0},A_{0}^{\prime},A_{1},A_{1}^{\prime},\dots,A_{n+1},A_{n+1}^{\prime}$.
$A_{0}$ is the set of trees on vertices $0,\dots,n$, where each tree comes
with a positive sign.

The sets $A_{0}^{\prime},A_{1},A_{1}^{\prime},\dots,A_{n}^{\prime}$ are matrix
sets as described in §4: For $1\leq i\leq n$, $A_{i}$ is the matrix set of
arrays corresponding to $M_{i}$ and for $0\leq i\leq n$, $A_{i}^{\prime}$ is
the matrix set of arrays from $M_{i}^{\prime}$. For example, when $n=2$, two
of the elements of $A_{2}$ are: $\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]$ and
$\left[\begin{smallmatrix}&-b_{1}&\\\ -\lambda&&\\\
&&B_{2}\end{smallmatrix}\right]$. (These arrays with one element in each row
and column are understood to come with the sign they would have in the
determinant.)

$A_{n+1}$ is the set of signed monomials (written as ordered $n$-tuples)
occurring in $S$, the coefficient of $\lambda$ in the determinant of
$M_{n}^{\prime}$:

$A_{n+1}=B^{n}-\left(\\{b_{1}\\}\times
B^{n-1}\right)-\left(B\times\\{b_{2}\\}\times
B^{n-2}\right)-\ldots-\left(B^{n-1}\times\\{b_{n}\\}\right).$

Here, we think of $B$ as $B=\\{B_{0},B_{1},\ldots,B_{n}\\}$ and $B^{k}$ as the
$k$-fold direct product of $B$ with itself. We write the factors in the left-
to-right order of the columns in which the entries appeared. The final set,
$A_{n+1}^{\prime}$, is the set of monomials (all positive now) remaining when
$B_{j}$ is set equal to $b_{j}$ and arithmetic is done on $S$:
$A_{n+1}^{\prime}=\\{b_{0}\\}\times B^{n-1}$. Ignoring the initial $b_{0}$,
this is isomorphic to the set of codes (the codes are simply the subscripts of
these monomials taken in order).

###  2 The involutions

We define a sequence of sign-reversing involutions
$\phi_{0},\phi_{0}^{\prime},\phi_{1},\phi_{1}^{\prime},\dots,\phi_{n}^{\prime},\phi_{n+1}$
on differences of two consecutive sets. In this set-up, when we write a
negative sign in front of an array it implies that the matrix comes from the
subtracted set.

##### Defining $\phi_{0}$

$\phi_{0}:A_{0}-A_{0}^{\prime}\to A_{0}-A_{0}^{\prime}$ is defined as follows.
If $t$ is a tree, then $\phi_{0}(t)$ is the negative of the array given by the
bijective proof of the Matrix Tree Theorem: in the $i^{\rm th}$ diagonal, the
$B_{j}$ term is taken if $\verb+succ+(i)=j$. If $t$ is an array in the
negative matrix set, we look at the graph formed by the edges $i\to j$ for all
$i,j$ where an indeterminate with the subscript $j$ is in the $i^{\rm th}$ row
of $t$. If this is a tree, then it is $\phi_{0}(t)$. If not, then
$\phi_{0}(t)$ can be found by toggling the diagonality of the cycle containing
the greatest vertex in a cycle in this graph (see §4). In the case where a
tree matches an array, this is clearly a sign-reversing involution. For the
case of the pairings of two elements of $A_{0}^{\prime}$, since we only moved
one cycle on or off the diagonal, and we know how to find it, it is clear that
repeating the process will get us back where we started. $\phi_{0}$ is sign-
reversing, as noted in §4

##### Defining $\phi_{i}^{\prime}$ for $0\leq i\leq n-1$

Recall that for $0\leq i\leq n-1$, $M_{i+1}$ is obtained from $M_{i}^{\prime}$
by row subtraction without cancellation.
$\phi_{i}^{\prime}:A_{i}^{\prime}-A_{i+1}\to A_{i}^{\prime}-A_{i+1}$ is
defined as follows. If $a\in-A_{i+1}$ and the entry in row $n-i+1$ is
$-\lambda$ or $\pm b_{j}$ for some $j$, then
$\phi_{i}^{\prime}(-a)=-a^{\prime}\in-A_{i+1}$ where $a^{\prime}$ is obtained
from $a$ by interchanging and negating rows 0 and $n-i+1$. (Remember that the
matrices are indexed from 0 to $n$.) Otherwise, $\phi_{i}^{\prime}(a)=-a$ (in
$-A_{i+1}$ if $a\in A_{i}$, and vice versa).

An example may help to clarify the method. In the $n=2$ case, $A_{0}^{\prime}$
and $A_{1}$ are the sets of arrays in which $\lambda$ occurs in
$M_{0}^{\prime}$ and $M_{1}$ respectively:

$M_{0}^{\prime}=\left[\begin{array}[]{ccc}\lambda-b_{0}&-b_{1}&-b_{2}\\\
-b_{0}&B-b_{1}&-b_{2}\\\ -b_{0}&-b_{1}&B-b_{2}\end{array}\right]\text{ and}$
$M_{1}=\left[\begin{array}[]{ccc}\lambda-b_{0}&-b_{1}&-b_{2}\\\
-b_{0}&B-b_{1}&-b_{2}\\\
-\lambda+b_{0}-b_{0}&b_{1}-b_{1}&b_{2}+B-b_{2}\end{array}\right].$

In the easier situation, where the array does not change, we have:

$\phi_{0}^{\prime}\left(\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in-A_{1}.$

Here, we started with an element of $A_{0}^{\prime}$ and ended with an element
of $-A_{1}$; the two arrays look identical other than the negative sign
outside. Meanwhile, in the more confusing case:

$\phi_{0}^{\prime}\left(-\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&b_{2}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\ -\lambda&&\end{smallmatrix}\right].$

Note that in this example, both arrays appear in the set $-A_{1}$ but do not
exist in $A_{0}^{\prime}$, and the actual sign of $\phi_{0}^{\prime}(-a)$ is
different from that of $-a$. We have switched the rows in which two of the
entries appeared, changing their signs but leaving them in their original
columns. This is always the procedure for $\phi_{i}^{\prime}$. Another
possibility is:

$\phi_{0}^{\prime}\left(-\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&-b_{2}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&-b_{2}\end{smallmatrix}\right]\in A_{0}^{\prime}.$

In this example, we started with an element of $-A_{1}$ and
$\phi_{0}^{\prime}$ returned an element of $A_{0}^{\prime}$;
$\phi_{0}^{\prime}$ is an involution because if we apply it twice we get back
the same element we started with. The involution is sign-reversing because
interchanging two rows of a matrix changes the sign of the determinant and
changing the signs of two rows has no effect.

##### Defining $\phi_{i}$ for $1\leq i\leq n$

Since $M_{i}^{\prime}$ is obtained from $M_{i}$ by arithmetic within entries
of the matrix, the rest of the involutions for $1\leq i\leq n$ are of the form
$\phi_{i}:A_{i}-A_{i}^{\prime}\to A_{i}-A_{i}^{\prime}$. If $a\in A_{i}$ and
the entry in the $(n-i+1)^{\rm th}$ row is $\pm b_{j}$, then
$\phi_{i}(a)=a^{\prime}\in A_{i}$ where $a^{\prime}$ is obtained from $a$ by
changing the sign of the entry in the $(n-i+1)^{\rm th}$ row. Otherwise,
$\phi_{i}(a)=-a\in A_{i}^{\prime}$. If $-a\in-A_{i}^{\prime}$, then
$\phi_{i}(-a)=a\in A_{i}$. Returning to the $n=2$ example,

$M_{1}^{\prime}=\left[\begin{array}[]{ccc}\lambda-b_{0}&-b_{1}&-b_{2}\\\
-b_{0}&B-b_{1}&-b_{2}\\\ -\lambda&0&B\end{array}\right].$

So we have

$\phi_{1}\left(\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&-b_{2}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&+b_{2}\end{smallmatrix}\right]\in A_{1},$

and

$\phi_{1}\left(-\left[\begin{smallmatrix}&-b_{1}&\\\ &&-b_{2}\\\
-\lambda&&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&-b_{1}&\\\
&&-b_{2}\\\ -\lambda&&\end{smallmatrix}\right]\in A_{1}.$

Note that in the first of these two examples, $\phi_{1}(a)$ and $a$ had
opposite signs but were both elements of $A_{1}$, whereas in the second
example, $-a\in-A_{1}^{\prime}$ and $\phi_{1}(-a)\in A_{1}$. This is clearly
an involution, since there is only one row of $M_{i}^{\prime}$ in which
entries appear twice with opposite signs.

##### Defining $\phi_{n}^{\prime}$ and $\phi_{n+1}$

The last two involutions are a little bit different.
$\phi_{n}^{\prime}:A_{n}^{\prime}-A_{n+1}\to A_{n}^{\prime}-A_{n+1}$ takes an
array in the matrix set $A_{n}^{\prime}$ and matches it with the product of
its non-$\lambda$ entries in the order of their columns (with the sign the
determinant would assign this term), and it takes signed monomials to the
location of the corresponding array. There is always a $\lambda$ in the zeroth
column.

For example, in

$M_{2}^{\prime}=\begin{bmatrix}\lambda-b_{0}&-b_{1}&-b_{2}\\\ -\lambda&B&0\\\
-\lambda&0&B\end{bmatrix},$

we have

$\phi_{2}^{\prime}\left(\left[\begin{smallmatrix}&-b_{1}&\\\ -\lambda&&\\\
&&B_{0}\end{smallmatrix}\right]\right)=-b_{1}B_{0},$
$\phi_{2}^{\prime}(-B_{0}b_{2})=\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\ -\lambda&&\end{smallmatrix}\right],$

and

$\phi_{2}^{\prime}\left(\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=B_{0}B_{0}.$

Again, this is an involution because it matches elements of $A_{n}^{\prime}$
(the set of arrays) with monomials, in perfect pairs.

The final involution, $\phi_{n+1}:A_{n+1}-A_{n+1}^{\prime}\to
A_{n+1}-A_{n+1}^{\prime}$, takes any positive element of $A_{n+1}$ and matches
it to another monomial, obtained according to the following formula:

$\phi_{n+1}\left(\prod_{k=1}^{n}B_{j_{k}}\right)=\begin{cases}-b_{0}\displaystyle{\prod_{k=2}^{n}B_{j_{k}}}\in-
A_{n+1}^{\prime}&\text{if $j_{1}=0$},\\\
-B_{j_{j_{1}}}\displaystyle{\left(\prod_{k=2}^{j_{1}-1}B_{j_{k}}\right)}b_{j_{1}}\displaystyle{\left(\prod_{k=j_{1}+1}^{n}B_{j_{k}}\right)}\in
A_{n+1}&\text{otherwise.}\end{cases}$

$\phi_{n+1}$ applied to any element of $-A_{n+1}^{\prime}$ gives the same
monomial, only with the initial $-b_{0}$ changed to a positive $B_{0}$, in
$A_{n+1}$. If we start with a negative element of $A_{n+1}$, it must have
exactly one $b_{j}$ in the $j^{th}$ position for some $j$. When we apply
$\phi_{n+1}$, we make this $b_{j}$ upper-case and switch it with the
indeterminate in the first position, and change the sign. This is clearly a
sign-reversing involution.

The ugliness of the formula belies the simplicity of the process. A few
examples with $n=6$ should help.

$\phi_{7}\left(B_{3}B_{4}B_{6}B_{0}B_{2}B_{0}\right)=-B_{6}B_{4}b_{3}B_{0}B_{2}B_{0}\in
A_{7}.$

All we have done is toggle the capitalization of $B_{3}$ (in the first
position of the product) and switch this new lower-case entry with the element
in the third (its subscript) position (which is $B_{6}$). The easiest possible
case is:

$\phi_{7}\left(B_{0}B_{1}B_{6}B_{2}B_{4}B_{2}\right)=-b_{0}B_{1}B_{6}B_{2}B_{4}B_{2}\in-
A_{7}^{\prime}.$

More often some switching is involved, as in the first case and the next one:

$\phi_{7}\left(-B_{4}B_{3}B_{0}B_{3}b_{5}B_{1}\right)=B_{5}B_{3}B_{0}B_{3}B_{4}B_{1}\in
A_{7}.$

(Remember, if there is a lower-case $b_{j}$ in the product, we switch it with
the first element of the product.)

These involutions are a key ingredient in the creation of the Happy Code.

###  3 Garsia and Milne’s Involution Principle

Garsia and Milne [5] found an extremely useful method while investigating
bijective proofs for the Rogers-Ramanujan identities.

###### Definition 21

A pseudo-sign-reversing involution is an involution on a signed set, with the
property that any point that is not fixed is sent to a point with the opposite
sign.

######  Lemma 1 (Scholium: The Involution Principle [5])

Let $A$ be a finite signed set, $A=A^{+}-A^{-}$, with pseudo-sign-reversing
involutions $\phi$ and $\psi$ whose fixed-point sets are $F(\phi)$ and
$F(\psi)$ respectively. Then there is a (fixed-point-free) sign-reversing
involution $\gamma$ on the set $F(\phi)-F(\psi)$. Furthermore, $\gamma$ can be
constructed using the following algorithm:

> begin |
> ---|---
> |  if $\phi(x)$ |  $\,=x$ then
> |  | $y\leftarrow x$
> |  |  repeat |
> |  |  | $z\leftarrow\psi(y)$
> |  |  | $y\leftarrow\phi(z)$
> |  |  until $\phi(z)\,=\,z$ or $\psi(y)\,=\,y$
> |  |  if $\phi(z)\,=\,z$ then
> |  |  | $\gamma(x)\leftarrow z$
> |  | else
> |  |  | $\gamma(x)\leftarrow y$
> |  else if $\psi(x)\,=x$ then
> |  | $y\leftarrow x$
> |  | repeat
> |  |  | $z\leftarrow\phi(y)$
> |  |  | $y\leftarrow\psi(z)$
> |  |  until $\psi(z)\,=\,z$ or $\phi(y)\,=\,y$
> |  |  if $\psi(z)\,=\,z$ then
> |  |  | $\gamma(x)\leftarrow z$
> |  | else
> |  |  | $\gamma(x)\leftarrow y$
> | else
> |  | {$x$ is not a fixed point of $\phi$ or $\psi$}
> end.111Pseudo-code quoted from [11], pages 141-142

This Lemma is extremely important because it not only establishes the
existence of the involution $\gamma$ but actually shows how to construct it.

######  Lemma 2 (The Bread Lemma)

Given two sign-reversing involutions, $\phi:A-B\to A-B$ and $\psi:B-C\to B-C$,
there is a sign-reversing involution on $A-C$.

######  Proof 3.2.

Let $\overline{-I_{B}}$ represent the negative identity map on $B-B$, extended
to be the identity on $A-C$.

$\overline{-I_{B}}\left(x\right)=\begin{cases}-x&\text{if $x\in-B+B$},\\\
x&\text{if $x\in A-C$.}\end{cases}$

Let $\phi+\psi:A-B+B-C\to A-B+B-C$ be defined as follows:

$\left(\phi+\psi\right)\left(x\right)=\begin{cases}\phi\left(x\right)&\text{if
$x\in A-B$}\\\ \psi\left(x\right)&\text{if $x\in B-C$}\end{cases}.$

Then both $\overline{-I_{B}}$ and $(\phi+\psi)$ are pseudo-sign-reversing
involutions, and $F(\overline{-I_{B}})=A-C$ and $F(\phi+\psi)=\emptyset$. The
algorithm of the Involution Principle provides a sign-reversing involution on
$F(\phi+\psi)-F(\overline{-I_{B}})=A-C-\emptyset=A-C$.

We call it the Bread Lemma because it can be visualized as a process to remove
all of the insides from a $B$ sandwich, leaving the diner with only a couple
of slices of bread (the sets $A$ and $C$).

######  Lemma 3.3.

Given any sequence of signed sets $S_{0},S_{1},\dots,S_{k+1}$, where $S_{0}$
and $S_{k+1}$ contain only positive elements, and sign-reversing involutions
$\beta_{0},\dots,\beta_{k}$ where $\beta_{i}$ acts on $S_{i}-S_{i+1}$, there
is a constructible bijection between $S_{0}$ and $S_{k+1}$.

######  Proof 3.4.

By repeated applications of The Bread Lemma (Lemma 2), we can “eliminate” all
of the in-between sets as follows. Let $A=S_{0}$, $B=S_{1}$, $C=S_{2}$,
$\phi=\beta_{0}$, and $\psi=\beta_{1}$. The Bread Lemma constructs a sign-
reversing involution on $S_{0}-S_{2}$, and this involution still satisfies the
hypotheses of the Bread Lemma. Now let $B=S_{2}$, $C=S_{3}$, etc. We keep
sandwiching in until we arrive at $A=S_{0}$, $B=S_{k}$, and $C=S_{k+1}$, where
$\phi$ is the involution achieved by so many applications of the Bread Lemma
and $\psi$ is $\beta_{k+1}$. One more application, and we have a sign-
reversing involution on $S_{0}-S_{k+1}$. However,
$\left(S_{0}-S_{k+1}\right)^{+}=S_{0}$ and
$\left(S_{0}-S_{k+1}\right)^{-}=-S_{k+1}$ since these two sets contained only
positive elements. Hence the only way for the involution to be sign-reversing
is for each element of $S_{0}$ to be mapped to an element of $S_{k+1}$. Thus,
we have found a bijection between $S_{0}$ and $S_{k+1}$. Note that we have not
simply proven the existence of a bijection, but actually provided an algorithm
for constructing it.

######  Theorem 3.5.

Given the sets $A_{0},A_{0}^{\prime},A_{1},\dots,A_{n+1}^{\prime}$ and the
sign-reversing involutions
$\phi_{0},\phi_{0}^{\prime},\dots,\phi_{n},\phi_{n}^{\prime},\phi_{n+1}$
defined above, there is a constructible bijection between $A_{0}$ (the set of
trees) and $A_{n+1}^{\prime}$ (the set of codes).

######  Proof 3.6.

The sets $A_{0},\dots,A_{n+1}^{\prime}$ and the involutions
$\phi_{0},\dots,\phi_{n+1}$ satisfy the hypotheses of Lemma 3.3. Thus we can
construct the bijection between the set of trees and the set of codes.

###  4 An example

Consider the case $n=2$. We will apply the theorem to find the code that
corresponds to the tree $1\to 2\to 0\in A_{0}$.

First we apply $\phi_{0}$ to get an element of $-A_{0}^{\prime}$:

$\phi_{0}\left(1\to 2\to 0\right)=-\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\in-A_{0}^{\prime}$

Next we apply $\overline{-I_{A_{0}^{\prime}}}$:

$\overline{-I_{A_{0}^{\prime}}}\left(-\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\in A_{0}^{\prime}$

We alternate between $\phi$s and $\overline{-I}$s. Each application of a
$\overline{-I}$ merely changes the sign of the element (and of the subset it
lies in):

$\overline{-I_{A_{1}}}\circ\phi_{0}^{\prime}\left(-\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\in A_{1}$
$\overline{-I_{A_{1}^{\prime}}}\circ\phi_{1}\left(\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\in A_{1}^{\prime}$
$\overline{-I_{A_{2}}}\circ\phi_{1}^{\prime}\left(\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\in A_{2}$
$\overline{-I_{A_{2}^{\prime}}}\circ\phi_{2}\left(\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\in A_{2}^{\prime}.$

Since $n=2$, we are in the last matrix set.

$\overline{-I_{A_{3}}}\circ\phi_{2}^{\prime}\left(\left[\begin{smallmatrix}\lambda&&\\\
&B_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\right)=B_{2}B_{0}\in A_{3}$

This is the exciting part!

$\phi_{3}\left(B_{2}B_{0}\right)=-B_{0}b_{2}\in A_{3}$
$\phi_{2}^{\prime}\circ\overline{-I_{A_{3}}}\left(-B_{0}b_{2}\right)=\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\ -\lambda&&\end{smallmatrix}\right]\in A_{2}^{\prime}$

Now there is nothing to stop us from passing through several sets in a row on
our way back up the sequence of sets via the following involutions:

$\phi_{2}\circ\overline{-I_{A_{2}^{\prime}}}\left(\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\
-\lambda&&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\ -\lambda&&\end{smallmatrix}\right]\in A_{2}$

$\phi_{1}^{\prime}\circ\overline{-I_{A_{2}}}\left(\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\
-\lambda&&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\ -\lambda&&\end{smallmatrix}\right]\in A_{1}^{\prime}$

$\phi_{1}\circ\overline{-I_{A_{1}^{\prime}}}\left(\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\
-\lambda&&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\ -\lambda&&\end{smallmatrix}\right]\in A_{1}$

At this point we apply $\phi_{0}^{\prime}\circ\overline{-I_{A_{1}}}$.
$\overline{-I_{A_{1}}}$ takes us to the set $-A_{1}$, and in this case an
application of $\phi_{0}^{\prime}$ maps to another element of $-A_{1}$:

$\phi_{0}^{\prime}\circ\overline{-I_{A_{1}}}\left(\left[\begin{smallmatrix}&&-b_{2}\\\
&B_{0}&\\\
-\lambda&&\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&b_{2}\end{smallmatrix}\right]\in-A_{1}$
$\overline{-I_{A_{1}}}\left(-\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&b_{2}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&b_{2}\end{smallmatrix}\right]\in A_{1}$
$\phi_{1}\left(\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&b_{2}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&-b_{2}\end{smallmatrix}\right]\in A_{1}$
$\overline{-I_{A_{0}^{\prime}}}\circ\phi_{0}^{\prime}\circ\overline{-I_{A_{1}}}\left(\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\
&&-b_{2}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&-b_{2}\end{smallmatrix}\right]\in-A_{0}^{\prime}$

At this point it is the Matrix Tree Theorem that comes to the rescue, in the
form of $\phi_{0}$:

$\phi_{0}\left(-\left[\begin{smallmatrix}\lambda&&\\\ &B_{0}&\\\
&&-b_{2}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&B_{2}\end{smallmatrix}\right]\in-A_{0}^{\prime}$

The involutions now take us directly down the sequence of matrices to the last
one.

$\overline{-I_{A_{1}^{\prime}}}\circ\phi_{1}\circ\overline{-I_{A_{1}}}\circ\phi_{0}^{\prime}\circ\overline{-I_{A_{0}^{\prime}}}\left(-\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\
&&B_{2}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&B_{2}\end{smallmatrix}\right]\in A_{1}^{\prime}$
$\overline{-I_{A_{2}^{\prime}}}\circ\phi_{2}\circ\overline{-I_{A_{2}}}\circ\phi_{1}^{\prime}\left(\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\
&&B_{2}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&B_{2}\end{smallmatrix}\right]\in A_{2}^{\prime}$

Coming down the home stretch:

$\overline{-I_{A_{3}}}\circ\phi_{2}^{\prime}\left(\left[\begin{smallmatrix}\lambda&&\\\
&B_{0}&\\\ &&B_{2}\end{smallmatrix}\right]\right)=B_{0}B_{2}\in A_{3}$

And finally:

$\phi_{3}\left(B_{0}B_{2}\right)=-b_{0}B_{2}\in-A_{3}^{\prime}.$

Thus, the Happy Code for the tree $1\to 2\to 0$ is $B_{2}$.

To find the tree for a code, we can easily follow the involutions through
backwards, undoing the whole process. In this sense, the Happy Code is more
natural (hence “happier”) than the Prüfer Code.

Computationally, finding the Happy Code for a tree is a slow process. However,
later we will see a method for calculating the Happy Code that does not resort
to matrices but works directly with the tree.

##  Chapter 2 The Blob Code

Another code results from a different sequence of sets and involutions, but
still using the Involution Principle and the Bread Lemma. We begin with the
$n\times n$ submatrix from the Matrix Tree Theorem (obtained by crossing out
the zeroth row and column):

$C_{0}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}&\ldots&-b_{n}\\\
-b_{1}&B-b_{2}&\ldots&-b_{n}\\\ .&.&\ldots&.\\\ .&.&\ldots&.\\\
.&.&\ldots&.\\\ -b_{1}&-b_{2}&\ldots&B-b_{n}\end{bmatrix}$

The Blob Code is related to the process of alternately performing row
operations and column operations on adjacent rows and columns as follows. The
first step is to subtract row $n-1$ from row $n$ (without cancellation).

$R_{1}=\begin{bmatrix}B-b_{1}&-b_{2}&\ldots&-b_{n-1}&-b_{n}\\\
-b_{1}&B-b_{2}&\ldots&-b_{n-1}&-b_{n}\\\ .&.&\ldots&.&.\\\ .&.&\ldots&.&.\\\
.&.&\ldots&.&.\\\ -b_{1}&-b_{2}&\ldots&B-b_{n-1}&-b_{n}\\\
-b_{1}+b_{1}&-b_{2}+b_{2}&\ldots&-b_{n-1}-B+b_{n-1}&B-b_{n}+b_{n}\end{bmatrix}$

Now we perform arithmetic within entries, but only in row $n$:

$R_{1}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}&\ldots&-b_{n-1}&-b_{n}\\\
-b_{1}&B-b_{2}&\ldots&-b_{n-1}&-b_{n}\\\ .&.&\ldots&.&.\\\ .&.&\ldots&.&.\\\
.&.&\ldots&.&.\\\ -b_{1}&-b_{2}&\ldots&B-b_{n-1}&-b_{n}\\\
0&0&\ldots&-B&B\end{bmatrix}$

Then we add column $n$ to column $n-1$.

$C_{1}=\begin{bmatrix}B-b_{1}&-b_{2}&\ldots&-b_{n-1}-b_{n}&-b_{n}\\\
-b_{1}&B-b_{2}&\ldots&-b_{n-1}-b_{n}&-b_{n}\\\ .&.&\ldots&.&.\\\
.&.&\ldots&.&.\\\ .&.&\ldots&.&.\\\
-b_{1}&-b_{2}&\ldots&B-b_{n-1}-b_{n}&-b_{n}\\\ 0&0&\ldots&-B+B&B\end{bmatrix}$

And once again, perform arithmetic within entries in row $n$ (not column
$n-1$):

$C_{1}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}&\ldots&-b_{n-1}-b_{n}&-b_{n}\\\
-b_{1}&B-b_{2}&\ldots&-b_{n-1}-b_{n}&-b_{n}\\\ .&.&\ldots&.&.\\\
.&.&\ldots&.&.\\\ .&.&\ldots&.&.\\\
-b_{1}&-b_{2}&\ldots&B-b_{n-1}-b_{n}&-b_{n}\\\ 0&0&\ldots&0&B\end{bmatrix}$

All of that was the first step. We work our way up the matrix this way: at the
$i^{\rm th}$ step we first subtract row $n-i$ from row $n-i+1$, then add
column $n-i+1$ to column $n-i$, cancelling only within row $n-i+1$, until the
matrix consists of $B$ on the diagonals and $0$ elsewhere, except in the first
row. At the end of the $i^{\rm th}$ step the $(n-i)^{\rm th}$ diagonal entry
consists of $B-\sum b_{j}$ where the sum is over $n-i\leq j\leq n$. After the
last column operation, we set $B_{j}=b_{j}$ so that the diagonal entry in row
1 consists only of $b_{0}$. At the end of the whole process, the first row
consists of $b_{0}$ in its first entry and a bunch of garbage in the other
entries, but the rest of the matrix is just $B$ on the diagonal. The last 2
matrices are:

$C_{n-1}=\begin{bmatrix}B-b_{1}-\displaystyle{\sum_{k=2}^{n}}b_{k}&-\displaystyle{\sum_{k=2}^{n}}b_{k}&\displaystyle{\sum_{k=3}^{n}}b_{k}&\ldots&-b_{n-1}-b_{n}&-b_{n}\\\
-B+B&B&0&\ldots&0&0\\\ .&.&.&\ldots&.&.\\\ .&.&.&\ldots&.&.\\\
.&.&.&\ldots&.&.\\\ 0&0&.&\ldots&B&0\\\ 0&0&0&\ldots&0&B\end{bmatrix}$

and

$C_{n-1}^{\prime}=\begin{bmatrix}b_{0}&-b_{2}-b_{3}-\dots-
b_{n}&\ldots&-b_{n-1}-b_{n}&-b_{n}\\\ 0&\sum_{j=0}^{n}b_{j}&\ldots&0&0\\\
.&.&\ldots&.&.\\\ .&.&\ldots&.&.\\\ .&.&\ldots&.&.\\\
0&0&\ldots&\sum_{j=0}^{n}b_{j}&0\\\
0&0&\ldots&0&\sum_{j=0}^{n}b_{j}\end{bmatrix}.$

This matrix clearly has determinant equal to $b_{0}B^{n-1}$.

###  1 Orlin’s ideas

In [8], Orlin introduced the idea of identifying two vertices of a graph. We
explain how this notion is used with the matrices in the construction of the
Blob Code. Assume we have a weighted directed graph on vertices $0$ through
$n$. Loops are allowed. We assume there are no multiple edges, because
multiple edges can be subsumed into the weights. The weight of the edge from
$i$ to $j$ is $a_{ij}$.

######  Definition 1.

In a directed graph $D$, two vertices $i$ and $j$ are identifiable when
$a_{ik}=a_{jk}$ for all $k$.

Note that this definition includes $k=i$ and $k=j$; so if there is an edge
from $i$ to $j$ then there needs to be a loop on $j$.

Identifiability is an equivalence relation, so there is some sense in which we
can think of two identifiable vertices as being redundant (their outgoing
edges have the same heads).

######  Definition 2.

If we “identify” two identifiable vertices $i$ and $j$ to a generalized
vertex, called `blob`, and eliminate one set of the duplicate edges, we end up
with a new digraph in which there are $a_{ik}$($=a_{jk}$) edges
$\verb+blob+\rightarrow k$ for all $k\neq i,j$, and there are $a_{ki}+a_{kj}$
edges $k\rightarrow\verb+blob+$. There are also $a_{ij}+a_{ji}$ loops on the
`blob`.

We take full blame for the naming of the `blob`. We differ from Orlin in our
visualization of this process. He considered this “`blob`” to be a new vertex;
we think of it as containing the original two vertices being identified. Each
incoming edge actually points not at the `blob` as a whole but rather at its
original terminal vertex within the `blob`.

Here, we set our edge weights to $W(i\to j)=b_{j}$ for all edges. and look at
an example:

0312$\hookleftarrow$

Vertices $1$ and $3$ are identifiable: each has exactly one edge to $0$ and
one edge to $1$. If we identify the two, we obtain the following graph (with
weights $w(2\to 0)=b_{0}$, $w(2\to 1)=b_{1}$, $w(2\to 3)=b_{3}$,
$w(\verb+blob+\to 0)=b_{0}$, and $w(\verb+blob+\to 1)=b_{1}$):

0231$\hookleftarrow$

In this graph, 2 and `blob` are not identifiable because 2 has an edge to 3,
while there is no loop $\verb+blob+\to 3$.

In the complete digraph with loops, all vertices are identifiable. This was
why we altered the matrix to allow for loops. Orlin used this idea to
manipulate formulas to get the formula $(n+1)^{n-1}$ for the number of trees.
We examine the relationship between this idea and the matrix method.

For the moment we illustrate the process with $n=3$. We begin with the
complete directed graph. The $4\times 4$ matrix corresponding to it, where the
edges are weighted by indeterminates indexed by the terminal vertex, is

$\hat{D}-\hat{A}=\Upsilon_{0}=\begin{bmatrix}B-b_{0}&-b_{1}&-b_{2}&-b_{3}\\\
-b_{0}&B-b_{1}&-b_{2}&-b_{3}\\\ -b_{0}&-b_{1}&B-b_{2}&-b_{3}\\\
-b_{0}&-b_{1}&-b_{2}&B-b_{3}\end{bmatrix}.$

Once we identify vertices $2$ and $3$, the graph looks like this (omitting
edges whose initial vertex is 0, since they never appear in a tree and we will
not be identifying vertex 0 with any of the others).

03$\hookrightarrow$1$\hookleftarrow$2$\hookrightarrow$

The corresponding matrix is

$\Upsilon_{1}=\begin{bmatrix}B-b_{0}&-b_{1}&-b_{2}-b_{3}\\\
-b_{0}&B-b_{1}&-b_{2}-b_{3}\\\ -b_{0}&-b_{1}&B-b_{2}-b_{3}\end{bmatrix}.$

The proper way to think of this is that there are two relevant rows (the
zeroth row, representing edges from $0$, is not relevant); the “oneth” row
represents edges out of $1$ and the second represents edges out of `blob`. The
zeroth column represents edges into $0$; the “oneth” column (not including
diagonal entries) represents edges into $1$, and the second represents edges
into `blob`. An edge $1\to\verb+blob+$ can be either $1\to 2$ or $1\to 3$. If
we were to cancel terms in the last row, we would have only $b_{0}+b_{1}$ in
the diagonal entry. The positive and negative copies of $b_{2}$ and $b_{3}$
represent the loops $\verb+blob+\to 2$ and $\verb+blob+\to 3$ respectively.

Once we have identified $1$ with `blob` (which we can do because both have
edges to 0, 1, 2, and 3), the graph is (with undrawn edges from 0):

03$\hookrightarrow$2$\curvearrowleft$1$\hookleftarrow$

The matrix corresponding to this is

$\Upsilon_{2}=\begin{bmatrix}B-b_{0}&-b_{1}-b_{2}-b_{3}\\\
-b_{0}&B-b_{1}-b_{2}-b_{3}\end{bmatrix}=\begin{bmatrix}B-b_{0}&-b_{1}-b_{2}-b_{3}\\\
-b_{0}&b_{0}\end{bmatrix}.$

We will be crossing out the zeroth row and column. Thus, only one entry
appears in the part of the matrix in whose determinant we are interested. This
is true because now there is only one vertex besides $0$ and it only has one
non-loop edge.

The determinants of $\Upsilon_{0},\Upsilon_{1},$ and $\Upsilon_{2}$ are
related as follows: $b_{0}B^{2}=\det(\Upsilon_{0})=\det(\Upsilon_{1})\times
B=\det(\Upsilon_{2})\times B^{2}$.

###  2 The sets

Much as we did with the Happy Code, we use the matrices in the definition of a
sequence of signed sets, but now we insert some of Orlin’s ideas as well. The
sets are
$G_{0},G_{0}^{\prime},S_{1},S_{1}^{\prime},T_{1},T_{1}^{\prime},G_{1},\dots,T_{n-1}^{\prime},G_{n-1},G_{n-1}^{\prime},S_{n}$.

In this sequence, the set $G_{0}$ is the set of trees, and $G_{0}^{\prime}$ is
the matrix set of arrays defined by $C_{0}^{\prime}$. There are more matrices
than we had for the Happy Code, and extra sets in between. For $1\leq i\leq
n-1$, $G_{i}$ is the set of ordered pairs $(\tau,\gamma)$ where $\tau$ is a
spanning tree (rooted at $0$) on a directed graph $D_{i}$ (described below)
and $\gamma$ is an ordered $i$-tuple of $b_{j}$’s. $D_{i}$ is defined to be
the complete digraph with $n-i$ vertices, where vertex $n-i$ is actually
`blob` which contains $n-i,n-i+1,\dots,n$. The labels in `blob` are terminal
vertices to edges, but they all share the same outgoing edges; in any tree,
`blob` has only one outgoing edge.

For $1\leq i\leq n$, $S_{i}$ and $S_{i}^{\prime}$ are the sets of arrays from
$R_{i}$ and $R_{i}^{\prime}$ respectively, and $T_{i}$ denotes the set of
arrays from $C_{i}$. Finally, we use both $T_{i}^{\prime}$ and
$G_{i}^{\prime}$ to denote the set of arrays from $C_{i}^{\prime}$, for $0\leq
i\leq n-1$. Arrays are signed, as they were in the Happy Code. The final set
is $S_{n}=\\{b_{0}\\}\times B^{n-1}$ where, in the set notation, $B$ is
understood to stand for the set $B=\\{b_{0},\ldots,b_{n}\\}$ and $B^{n-1}$
stands for the $(n-1)$-fold direct product $B\times B\times\ldots\times B$.

As an example we list the sets for the case $n=3$. Matrices are thought of as
sets of arrays. (In the graphs, edges with initial vertex $0$ have been
omitted from the pictures, since they never appear in a spanning tree and the
zeroth row of the matrix has already been ignored.)

$G_{0}$=the set of rooted spanning trees
of03$\hookrightarrow$1$\hookleftarrow$2$\hookrightarrow$
$G_{0}^{\prime}\leftrightarrow
C_{0}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}&-b_{3}\\\
-b_{1}&B-b_{2}&-b_{3}\\\ -b_{1}&-b_{2}&B-b_{3}\end{bmatrix}$
$S_{1}\leftrightarrow R_{1}=\begin{bmatrix}B-b_{1}&-b_{2}&-b_{3}\\\
-b_{1}&B-b_{2}&-b_{3}\\\
-b_{1}+b_{1}&-b_{2}-B+b_{2}&B-b_{3}+b_{3}\end{bmatrix}$
$S_{1}^{\prime}\leftrightarrow
R_{1}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}&-b_{3}\\\
-b_{1}&B-b_{2}&-b_{3}\\\ 0&-B&B\end{bmatrix}$ $T_{1}\leftrightarrow
C_{1}=\begin{bmatrix}B-b_{1}&-b_{2}-b_{3}&-b_{3}\\\
-b_{1}&B-b_{2}-b_{3}&-b_{3}\\\ 0&-B+B&B\end{bmatrix}$
$T_{1}^{\prime}\leftrightarrow
C_{1}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}-b_{3}&-b_{3}\\\
-b_{1}&B-b_{2}-b_{3}&-b_{3}\\\ 0&0&B\end{bmatrix}$

$G_{1}=$the set of rooted spanning trees
of03$\hookrightarrow$1$\hookleftarrow$2$\hookrightarrow$$\times B$
$G_{1}^{\prime}\leftrightarrow
C_{1}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}-b_{3}&-b_{3}\\\
-b_{1}&B-b_{2}-b_{3}&-b_{3}\\\ 0&0&B\end{bmatrix}$ $S_{2}\leftrightarrow
R_{2}=\begin{bmatrix}B-b_{1}&-b_{2}-b_{3}&-b_{3}\\\
-b_{1}-B+b_{1}&B-b_{2}-b_{3}+b_{2}+b_{3}&-b_{3}+b_{3}\\\ 0&0&B\end{bmatrix}$
$S_{2}^{\prime}\leftrightarrow
R_{2}^{\prime}=\begin{bmatrix}B-b_{1}&-b_{2}-b_{3}&-b_{3}\\\ -B&B&0\\\
0&0&B\end{bmatrix}$ $T_{2}\leftrightarrow
C_{2}=\begin{bmatrix}B-b_{1}-b_{2}-b_{3}&-b_{2}-b_{3}&-b_{3}\\\ -B+B&B&0\\\
0&0&B\end{bmatrix}$ $T_{2}^{\prime}\leftrightarrow
C_{2}^{\prime}=\begin{bmatrix}b_{0}&-b_{2}-b_{3}&-b_{3}\\\
0&\displaystyle{\sum_{j=0}^{3}}b_{j}&0\\\
0&0&\displaystyle{\sum_{j=0}^{3}}b_{j}\end{bmatrix}$

$G_{2}=$the set of rooted spanning trees
of03$\hookrightarrow$2$\curvearrowleft$1$\hookleftarrow$$\times B^{2}$
$G_{2}^{\prime}\leftrightarrow
C_{2}^{\prime}=\begin{bmatrix}b_{0}&-b_{2}-b_{3}&-b_{3}\\\
0&\displaystyle{\sum_{j=0}^{3}}b_{j}&0\\\
0&0&\displaystyle{\sum_{j=0}^{3}}b_{j}\end{bmatrix}$

The final set is $S_{3}=\\{b_{0}\\}\times B\times B$, where
$B=\\{b_{0},b_{1},\dots,b_{n}\\}$ by abuse of notation.

###  3 The involutions

Some of the involutions are defined similarly to the involutions we used for
the Happy Code, but there are many more of them.

##### Defining $\mu_{0}^{\prime}$

$\mu_{0}^{\prime}:G_{0}-G_{0}^{\prime}\to G_{0}-G_{0}^{\prime}$ maps a tree to
an array from $-G_{0}^{\prime}$ by taking the $b_{j}$ in the $i^{\rm{th}}$
diagonal entry for each edge $i\to j$. The remaining elements of
$-C_{0}^{\prime}$ are matched in pairs (by toggling the diagonality of the
cycle with the largest element) according to the bijective proof of the Matrix
Tree Theorem, just as they were for the Happy Code.

##### Defining $\rho_{i}$ for $1\leq i\leq n-1$

For $1\leq i\leq n-1$, $\rho_{i}:G_{i-1}^{\prime}-S_{i}\to
G_{i-1}^{\prime}-S_{i}$ maps corresponding arrays in $G_{i-1}^{\prime}$ and
$-S_{i}$ to each other, and then takes the extra elements of $-S_{i}$ and
matches them up according to the row operation that took $C_{i-1}^{\prime}$ to
$R_{i}$. If $-a\in-S_{i}$ and the entry in row $n-i+1$ is $+b_{j}$ or
$-B_{j}$, then $\rho_{i}(-a)=-a^{\prime}\in-S_{i}$ where $a^{\prime}$ is
obtained from $a$ by interchanging and negating rows $n-i$ and $n-i+1$.
Otherwise, $\rho_{i}(a)=-a$ (in $G_{i-1}^{\prime}$ if $a\in-S_{i}$ and vice
versa). Consider what happens if we begin with an element of $G_{1}^{\prime}$:

$\rho_{2}\left(\left[\begin{smallmatrix}B_{0}&&\\\ &B_{1}&\\\
&&B_{2}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{0}&&\\\
&B_{1}&\\\ &&B_{2}\end{smallmatrix}\right]\in-S_{2}.$

If we start with an element of $G_{1}^{\prime}$, there is always a
corresponding element of $-S_{2}$: the same array but with a negative sign
outside it. We could also start with an element of $-S_{2}$:

$\rho_{2}\left(-\left[\begin{smallmatrix}B_{0}&&\\\ &B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in G_{1}^{\prime}.$

In that example, there was a corresponding element of $G_{1}^{\prime}$.
Sometimes, there isn’t:

$\rho_{2}\left(-\left[\begin{smallmatrix}&-b_{2}&\\\ -B_{3}&&\\\
&&B_{0}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{3}&&\\\
&+b_{2}&\\\ &&B_{0}\end{smallmatrix}\right]\in-S_{2}.$

Here we switched the rows (and signs!) of the entries in the first and second
rows without changing the columns of these entries. Note that the resulting
element of $-S_{2}$ does not have a corresponding element in $G_{1}^{\prime}$
either (because the $b_{2}$ on that diagonal is not the one from B). It is
clear that $\rho_{i}$ is a sign-reversing involution.

##### Defining $\rho_{i}^{\prime}$ for $1\leq i\leq n-1$

$\rho_{i}^{\prime}:S_{i}-S_{i}^{\prime}\to S_{i}-S_{i}^{\prime}$, for $1\leq
i\leq n-1$, is defined as follows: If $a\in S_{i}$ and the entry in row
$n-i+1$ is $\pm b_{j}$, then $\rho_{i}^{\prime}(a)=a^{\prime}\in S_{i}$ where
$a^{\prime}$ is obtained by changing the sign of the entry in row $n-i+1$ of
$a$ and all other entries remain unchanged. Otherwise,
$\rho_{i}^{\prime}(a)=-a$ (in $-S_{i}^{\prime}$ if $a\in S_{i}$ and vice
versa). For example, if $n=3$ and we start with an element of $S_{1}$,

$\rho_{1}^{\prime}\left(\left[\begin{smallmatrix}&&-b_{3}\\\ &B_{0}&\\\
-b_{1}&&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&&-b_{3}\\\
&B_{0}&\\\ +b_{1}&&\end{smallmatrix}\right]\in S_{1}.$

Other elements of $S_{1}$ get mapped to elements of $-S_{1}^{\prime}$ (and all
elements of $-S_{1}^{\prime}$ get mapped to elements of $S_{1}$):

$\rho_{1}^{\prime}\left(\left[\begin{smallmatrix}B_{2}&&\\\ &B_{0}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{2}&&\\\
&B_{0}&\\\ &&B_{0}\end{smallmatrix}\right]\in-S_{1}^{\prime}$

and

$\rho_{1}^{\prime}\left(\left[\begin{smallmatrix}B_{2}&&\\\ &&-b_{3}\\\
&-B_{0}&\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{2}&&\\\
&&-b_{3}\\\ &-B_{0}&\end{smallmatrix}\right]\in-S_{1}^{\prime}.$

##### Defining $\kappa_{i}$ for $1\leq i\leq n-1$

For $1\leq i\leq n-1$, $\kappa_{i}:S_{i}^{\prime}-T_{i}\to
S_{i}^{\prime}-T_{i}$ works similarly to $\rho_{i}$. The difference is that
now the column operation is the key. If we begin with an element of
$S_{1}^{\prime}$, we get an element of $-T_{1}$:

$\kappa_{1}\left(\left[\begin{smallmatrix}B_{2}&&\\\ &B_{0}&\\\
&&B_{2}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{2}&&\\\
&B_{0}&\\\ &&B_{2}\end{smallmatrix}\right]\in-T_{1}.$

In fact, $\kappa_{i}$ applied to an element of $S_{i}^{\prime}$ always gives
the corresponding element of $T_{i}$: the same array, but with a negative
sign. The reverse sometimes happens if we apply $\kappa_{i}$ to an element of
$T_{i}$:

$\kappa_{1}\left(-\left[\begin{smallmatrix}B_{0}&&\\\ &B_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{1}^{\prime}.$

However, if there is no corresponding element in $S_{i}^{\prime}$, we switch
the columns of the entries in columns $n-i+1$ and $n-i$ (but not the signs
this time, since the column operations were addition). For example,

$\kappa_{1}\left(-\left[\begin{smallmatrix}&-b_{3}&\\\ -b_{1}&&\\\
&&B_{0}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\ &B_{0}&\end{smallmatrix}\right]\in-T_{1}.$

Here we switched the entries in columns $2$ and $3$, leaving them in their
original rows. In general, we have: If $a\in-T_{i}$ and the entry in column
$n-i$ is $B_{j}$ in row $n-i+1$ or $-b_{j}$ where $j\geq n-i+1$, then
$\kappa_{i}(a)=a^{\prime}\in-T_{i}$ where $a^{\prime}$ is obtained from $a$ by
interchanging columns $n-i$ and $n-i+1$. For all other $a$, $\kappa_{i}(a)=-a$
(in $S_{i}$ if $a\in-T_{i}$ and vice versa).

##### Defining $\kappa_{i}^{\prime}$ for $1\leq i\leq n-2$

$\kappa_{i}^{\prime}:T_{i}-T_{i}^{\prime}\to T_{i}-T_{i}^{\prime}$ works
similarly to $\rho_{i}^{\prime}$ for $1\leq i\leq n-1$. If $a\in T_{i}$ and
the entry in row $n-i+1$ is in column $n-i$, then
$\kappa_{i}^{\prime}(a)=a^{\prime}\in T_{i}$ where $a^{\prime}$ is obtained
from $a$ by changing the sign of the entry in the $(n-i+1,n-i)$ position.
Otherwise, $\kappa_{i}(a)=-a$ (in $T_{i}$ if $a\in-T_{i}^{\prime}$ and vice
versa). For example, starting with an element of $T_{1}$:

$\kappa_{1}^{\prime}\left(\left[\begin{smallmatrix}B_{0}&&\\\ &B_{2}&\\\
&&B_{2}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{0}&&\\\
&B_{2}&\\\ &&B_{2}\end{smallmatrix}\right]\in-T_{1}^{\prime}.$

If we start with an element of $T_{1}$, there are two possibilities: either
there is a corresponding array in $T_{1}^{\prime}$ as above, or else the array
cancels via arithmetic within an entry, as in the next example:

$\kappa_{1}^{\prime}\left(\left[\begin{smallmatrix}&&-b_{3}\\\ -b_{1}&&\\\
&B_{0}&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\ &-B_{0}&\end{smallmatrix}\right]\in T_{1}.$

##### Defining $\kappa_{n-1}^{\prime}$

$\kappa_{n-1}^{\prime}:T_{n-1}-T_{n-1}^{\prime}\to T_{n-1}-T_{n-1}^{\prime}$
is essentially the same as the previous $\kappa_{i}^{\prime}$s, except that
now we set $B_{j}=b_{j}$ and cancel in row 1. If $a\in T_{n-1}$ and the entry
in column 1 is anything other than $B_{0}$ in the upper-left corner of the
matrix, then $\kappa_{n-1}^{\prime}(a)=a^{\prime}\in T_{n-1}$ where
$a^{\prime}$ is obtained from $a$ by changing the sign of the entry in column
1 and making all $B_{j}$ lower-case. For all other $a$,
$\kappa_{n-1}^{\prime}(a)=-a^{\prime}\in T_{n-1}^{\prime}$ obtained by leaving
all entries the same but making $B_{j}$ lower-case.

$\kappa_{2}^{\prime}\left(\left[\begin{smallmatrix}B_{3}&&\\\ &B_{0}&\\\
&&B_{2}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}-b_{3}&&\\\
&b_{0}&\\\ &&b_{2}\end{smallmatrix}\right]\in T_{2},$
$\kappa_{2}^{\prime}\left(\left[\begin{smallmatrix}-b_{2}&&\\\ &B_{0}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}b_{2}&&\\\
&b_{0}&\\\ &&b_{0}\end{smallmatrix}\right]\in T_{2},\text{ and}$
$\kappa_{2}^{\prime}\left(\left[\begin{smallmatrix}&-b_{2}&\\\ -B_{0}&&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&-b_{2}&\\\
b_{0}&&\\\ &&b_{0}\end{smallmatrix}\right]\in T_{2}.$

##### Defining $\mu_{i}$ and $\mu_{i}^{\prime}$ for $1\leq i\leq n-1$

$\mu_{i}:T_{i}^{\prime}-G_{i}\to T_{i}^{\prime}-G_{i}$ reads the entries of
the matrix and translates them into the digraph. The upper-left
$(n-i)\times(n-i)$ corner represents (by the Matrix Tree Theorem) the spanning
trees of $D_{i}$ (in fact, these submatrices are obtained from the matrices
$\Upsilon_{i}$ from the example in §1 by crossing out the zeroth row and
column). When $\mu_{i}$ is applied to an element $x$ in $T_{i}^{\prime}$, one
of two things happens. Case 1: if edges are drawn from $k$ to $j$ for each
$b_{j}$ appearing in row $k\leq n-i$ in $x$ (remembering that it is okay for
$j$ to be inside `blob`), and the resulting graph is a tree, then $\mu_{i}(x)$
is the pair whose first element is that tree, and whose second element is the
$i$-tuple found by reading down the diagonal starting at row $n-i+1$. Case 2:
if those edges do not form a tree, then there is at least one cycle, and by
moving the cycle with the largest element onto or off of the diagonal
(according to where it already was), we find the element of $T_{i}^{\prime}$
that is $\mu_{i}(x)$. (Actually, there can only be one cycle, so we don’t have
to worry about which cycle to move). It is clear that for elements $x\in
T_{i}^{\prime}$ such that $\mu_{i}(x)\in T_{i}^{\prime}$, $\mu_{i}$ acts as an
involution. Define $\mu_{i}((\tau,\gamma))$ to be the element of
$T_{i}^{\prime}$ found by putting $b_{j}$ in the diagonal entry in row $k$
whenever there is an edge in the tree $k\to j$, and filling in the rest of the
diagonal entries from left to right by taking them from the code. Then it is
clear that $\mu_{i}$ acts as an involution in the rest of the cases too.

If $\mu_{i}(x)\in-G_{i}$ (in other words, it is a $-(\tau,\gamma)$ pair), then
step $i$ of the overall procedure is finished. For example,

$\mu_{1}\left(\left[\begin{smallmatrix}B_{2}&&\\\ &B_{0}&\\\
&&B_{3}\end{smallmatrix}\right]\right)=-\left(\begin{picture}(55.0,20.0)\put(0.0,0.0){1}
\put(5.0,3.0){\vector(1,0){20.0}} \put(28.0,10.0){\oval(9.0,23.0)}
\put(25.0,0.0){2} \put(25.0,12.0){3} \put(33.0,5.0){\vector(1,0){15.0}}
\put(50.0,0.0){0} \end{picture},(b_{3})\right)\in-G_{2},$

which signifies that step 1 is finished. On the other hand,

$\mu_{1}\left(\left[\begin{smallmatrix}B_{3}&&\\\ &B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&-b_{3}&\\\
-b_{1}&&\\\ &&B_{0}\end{smallmatrix}\right],$

indicating that we will have to apply several more involutions before step 1
is done.

$\mu_{i}^{\prime}:G_{i}-G_{i}^{\prime}\to G_{i}-G_{i}^{\prime}$ is essentially
the negative of $\mu_{i}$, since the sets $T_{i}^{\prime}$ and
$G_{i}^{\prime}$ are identical. Moving from $G_{i}$ into $G_{i}^{\prime}$ is
the beginning of the $(i+1)^{\rm th}$ step.

##### Defining $\rho_{n}$

The final involution, $\rho_{n}:G_{n-1}^{\prime}-S_{n}\to
G_{n-1}^{\prime}-S_{n}$ matches arrays from $C_{n-1}^{\prime}$ to negative
monomials that consist of the entries in order from left to right, similarly
to $\phi_{n}^{\prime}$ in the Happy Code.

$\rho_{n}\left(\left[\begin{smallmatrix}b_{0}&&&\\\ &b_{k_{2}}&&\\\
&&\ddots&\\\ &&&b_{k_{n}}\end{smallmatrix}\right]\right)=b_{0}b_{k_{2}}\dots
b_{k_{n}}.$

For example,

$\rho_{3}\left(\left[\begin{smallmatrix}b_{0}&&\\\ &b_{3}&\\\
&&b_{0}\end{smallmatrix}\right]\right)=-b_{0}b_{3}b_{0},$
$\rho_{3}\left(\left[\begin{smallmatrix}b_{0}&&\\\ &b_{2}&\\\
&&b_{2}\end{smallmatrix}\right]\right)=-b_{0}b_{2}^{2},\text{ and}$
$\rho_{3}\left(-b_{0}b_{1}b_{3}\right)=\left[\begin{smallmatrix}b_{0}&&\\\
&b_{1}&\\\ &&b_{3}\end{smallmatrix}\right].$

In fact, since all elements of $G_{n-1}^{\prime}$ are positive, and so are all
elements of $S_{n}$, $\rho_{n}$ is a simple bijection between the elements of
$G_{n-1}^{\prime}$ and the elements of $-S_{n}$.

###  4 How to Find the Blob Code

We use these involutions the same way we did for the Happy Code.

######  Theorem 4.7.

Given the sets
$G_{0},G_{0}^{\prime},S_{1},S_{1}^{\prime},T_{1},T_{1}^{\prime},G_{1},\dots,G_{n-1}^{\prime},S_{n}$
and the sign-reversing involutions
$\mu_{0}^{\prime},\rho_{1},\rho_{1}^{\prime},\kappa_{1},\kappa_{1}^{\prime},\mu_{1},\mu_{1}^{\prime},\dots,\kappa_{n-1}^{\prime},\mu_{n-1},\mu_{n-1}^{\prime},\rho_{n}$,
there is a bijection between $G_{0}$ (the set of trees) and $S_{n}$ (the set
of codes).

######  Proof 4.8.

The sets and involutions satisfy the conditions of Lemma 3.3. Thus we can
construct the bijection between the set of trees and the set of codes.

####  1 An example

To clarify the method, we use the matrix method to construct the Blob Code for
the tree $2\to 1\to 3\to 0\in G_{0}$. It will help to remember that elements
in each signed set can only have one of the involutions of types
$\rho_{i},\rho_{i}^{\prime},\kappa_{i},\kappa_{i}^{\prime},\mu_{i},\mu_{i}^{\prime}$
applied to them, and we always alternate between negative identity maps and
our defined involutions ($\mu$, $\kappa$, and $\rho$, with indices and with or
without primes).

Involution | Acts on
---|---
$\rho_{i}$ | $G_{i-1}^{\prime}-S_{i}$
$\rho_{i}^{\prime}$ | $S_{i}-S_{i}^{\prime}$
$\kappa_{i}$ | $S_{i}^{\prime}-T_{i}$
$\kappa_{i}^{\prime}$ | $T_{i}-T_{i}^{\prime}$
$\mu_{i}$ | $T_{i}^{\prime}-G_{i}$
$\mu_{i}^{\prime}$ | $G_{i}-G_{i}^{\prime}$

This particular example is a sort of “worst case scenario” for a small graph,
but for larger $n$ such a long process would be more likely. Coding trees with
no inversions is much easier, as is coding any tree that satisfies the
condition that for every $i$ whose path to $0$ goes through some $j>i$, it
also holds that $\verb+succ+(i)>i$.

##### Step 1

First we apply $\mu_{0}^{\prime}$ to get an element of $-G_{0}^{\prime}$:

$\mu_{0}^{\prime}\left(2\to 1\to 3\to
0\right)=-\left[\begin{smallmatrix}B_{3}&&\\\ &B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\in-G_{0}^{\prime}.$

Next we apply $\overline{I_{G_{0}^{\prime}}}$:

$\overline{-I_{G_{0}^{\prime}}}\left(-\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\ &&B_{0}\end{smallmatrix}\right]\in G_{0}^{\prime}$

As in the example for the Happy Code, we alternate between the involutions we
defined, and the negative identity maps.

$\overline{-I_{S_{1}}}\circ\rho_{1}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\ &&B_{0}\end{smallmatrix}\right]\in S_{1}$
$\overline{-I_{S_{1}^{\prime}}}\circ\rho_{1}^{\prime}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\ &&B_{0}\end{smallmatrix}\right]\in S_{1}^{\prime}$
$\overline{-I_{T_{1}}}\circ\kappa_{1}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\ &&B_{0}\end{smallmatrix}\right]\in T_{1}$
$\overline{-I_{T_{1}^{\prime}}}\circ\kappa_{1}^{\prime}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\ &&B_{0}\end{smallmatrix}\right]\in T_{1}^{\prime}$

Here is the first time the involutions do anything interesting:

$\overline{-I_{T_{1}^{\prime}}}\circ\mu_{1}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{1}&\\\
&&B_{0}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&-b_{3}&\\\
-b_{1}&&\\\ &&B_{0}\end{smallmatrix}\right]\in-T_{1}^{\prime}$

Since $\mu_{1}$ doesn’t move us out of $T_{1}^{\prime}$, the negative identity
map results in a move to $-T_{1}^{\prime}$. Note that any time we are in a
negative set, we are moving “up” the sequence of matrices (or stalled where we
are). Because the array did not correspond to a tree in the graph where $2$
and $3$ are identified, the basic effect of $\mu_{1}$ at that step was to find
the array with off-diagonal entries that cancels it in the matrix. From
$-T_{1}^{\prime}$, we apply $\kappa_{i}^{\prime}$.

$\overline{-I_{T_{1}}}\circ\kappa_{1}^{\prime}\left(-\left[\begin{smallmatrix}&-b_{3}&\\\
-b_{1}&&\\\
&&B_{0}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&-b_{3}&\\\
-b_{1}&&\\\ &&B_{0}\end{smallmatrix}\right]\in-T_{1}$

The next few involutions have the effect of switching columns:

$\overline{-I_{T_{1}}}\circ\kappa_{1}\left(-\left[\begin{smallmatrix}&-b_{3}&\\\
-b_{1}&&\\\
&&B_{0}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\ &B_{0}&\end{smallmatrix}\right]\in T_{1}$
$\overline{-I_{T_{1}}}\circ\kappa_{1}^{\prime}\left(\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\
&B_{0}&\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\ &-B_{0}&\end{smallmatrix}\right]\in-T_{1}$
$\overline{-I_{S_{1}^{\prime}}}\circ\kappa_{1}\left(-\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\
&-B_{0}&\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\ &-B_{0}&\end{smallmatrix}\right]\in-S_{1}^{\prime}$
$\overline{-I_{S_{1}}}\circ\rho_{1}^{\prime}\left(-\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\
&-B_{0}&\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\ &-B_{0}&\end{smallmatrix}\right]\in-S_{1}$

And switching rows:

$\overline{-I_{S_{1}}}\circ\rho_{1}\left(-\left[\begin{smallmatrix}&&-b_{3}\\\
-b_{1}&&\\\
&-B_{0}&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&&-b_{3}\\\
&B_{0}&\\\ b_{1}&&\end{smallmatrix}\right]\in S_{1}$
$\overline{-I_{S_{1}}}\circ\rho_{1}\left(\left[\begin{smallmatrix}&&-b_{3}\\\
&B_{0}&\\\
b_{1}&&\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&&-b_{3}\\\
&B_{0}&\\\ -b_{1}&&\end{smallmatrix}\right]\in-S_{1}$
$\overline{-I_{G_{0}^{\prime}}}\circ\rho_{1}\left(-\left[\begin{smallmatrix}&&-b_{3}\\\
&B_{0}&\\\
-b_{1}&&\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&&-b_{3}\\\
&B_{0}&\\\ -b_{1}&&\end{smallmatrix}\right]\in-G_{0}^{\prime}$

We have defined the involutions in such a way that there is no passing the set
$G_{i}$ when moving up; we apply the Matrix Tree Theorem again (the effect, in
this case, of $\mu_{0}^{\prime}$):

$\overline{-I_{G_{0}^{\prime}}}\circ\mu_{0}^{\prime}\left(-\left[\begin{smallmatrix}&&-b_{3}\\\
&B_{0}&\\\
-b_{1}&&\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in G_{0}^{\prime}$

And from here on, it’s easy for the rest of the step:

$\overline{-I_{S_{1}}}\circ\rho_{1}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{1}$
$\overline{-I_{S_{1}^{\prime}}}\circ\rho_{1}^{\prime}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{1}^{\prime}$
$\overline{-I_{T_{1}}}\circ\kappa_{1}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{1}$
$\overline{-I_{T_{1}^{\prime}}}\circ\kappa_{1}^{\prime}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{1}^{\prime}$
$\overline{-I_{G_{1}}}\circ\mu_{1}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left(\begin{picture}(55.0,20.0)\put(0.0,0.0){1}
\put(5.0,3.0){\vector(1,0){20.0}} \put(28.0,10.0){\oval(9.0,21.0)}
\put(25.0,0.0){3} \put(25.0,12.0){2} \put(33.0,5.0){\vector(1,0){15.0}}
\put(50.0,0.0){0} \end{picture},(1)\right)\in G_{1}$

Since we’ve gotten to $G_{1}$ and have a tree and a partial code, we are done
with this step.

##### Step 2

Starting where we left off,

$\overline{-I_{G_{1}^{\prime}}}\circ\mu_{1}^{\prime}\left(\begin{picture}(55.0,20.0)\put(0.0,0.0){1}
\put(5.0,3.0){\vector(1,0){20.0}} \put(28.0,10.0){\oval(9.0,21.0)}
\put(25.0,0.0){3} \put(25.0,12.0){2} \put(33.0,5.0){\vector(1,0){15.0}}
\put(50.0,0.0){0} \end{picture},(1)\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in G_{1}^{\prime}$
$\overline{-I_{S_{2}}}\circ\rho_{2}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{2}$
$\overline{-I_{S_{2}^{\prime}}}\circ\rho_{2}^{\prime}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{2}^{\prime}$
$\overline{-I_{T_{2}}}\circ\kappa_{2}\left(\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{2}$

Now is the first time in Step 2 that we cannot move on to the next set,
because for each of the above applications of involutions there was a
corresponding element in the next set. The elements of $T_{2}$ can only be
acted on by $\kappa_{2}^{\prime}$.

$\kappa_{2}^{\prime}\left(\left[\begin{smallmatrix}B_{3}&&\\\ &B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}-b_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{2}.$
$\overline{-I_{T_{2}}}\left(\left[\begin{smallmatrix}-b_{3}&&\\\ &B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}-b_{3}&&\\\
&B_{0}&\\\ &&B_{1}\end{smallmatrix}\right]\in-T_{2}.$

From $-T_{2}$, the involution $\kappa_{2}$ will either take us to $S_{2}$ or
else leave us in $-T_{2}$ (in this case, the latter):

$\kappa_{2}\left(-\left[\begin{smallmatrix}-b_{3}&&\\\ &B_{0}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&-b_{3}&\\\
B_{0}&&\\\ &&B_{1}\end{smallmatrix}\right]\in-T_{2}.$

Another application of a negative identity map is now required as part of the
algorithm of the Involution Principle.

$\overline{-I_{T_{2}}}\left(-\left[\begin{smallmatrix}&-b_{3}&\\\ B_{0}&&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&-b_{3}&\\\
B_{0}&&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{2}.$

Now we go back to the appropriate involution, $\kappa_{2}^{\prime}$ in this
case:

$\kappa_{2}^{\prime}\left(\left[\begin{smallmatrix}&-b_{3}&\\\ B_{0}&&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}&-b_{3}&\\\
-B_{0}&&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{2}.$
$\overline{-I_{T_{2}}}\left(\left[\begin{smallmatrix}&-b_{3}&\\\ -B_{0}&&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&-b_{3}&\\\
-B_{0}&&\\\ &&B_{1}\end{smallmatrix}\right]\in-T_{2}.$
$\overline{-I_{S_{2}^{\prime}}}\circ\kappa_{2}\left(-\left[\begin{smallmatrix}&-b_{3}&\\\
-B_{0}&&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&-b_{3}&\\\
-B_{0}&&\\\ &&B_{1}\end{smallmatrix}\right]\in-S_{2}^{\prime}.$
$\overline{-I_{S_{2}}}\circ\rho_{2}^{\prime}\left(-\left[\begin{smallmatrix}&-b_{3}&\\\
-B_{0}&&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}&-b_{3}&\\\
-B_{0}&&\\\ &&B_{1}\end{smallmatrix}\right]\in-S_{2}.$

Again we get stuck at a set. The involution $\rho_{2}$ should either send us
to $T_{1}^{\prime}$ or leave us where we are, and it is the latter that
occurs.

$\rho_{2}\left(-\left[\begin{smallmatrix}&-b_{3}&\\\ -B_{0}&&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{0}&&\\\
&b_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in-S_{2}$

It is time for another negative identity map:

$\overline{-I_{S_{2}}}\left(-\left[\begin{smallmatrix}B_{0}&&\\\ &b_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&b_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{2}.$

Since we are back in $S_{2}$, we apply $\rho_{2}^{\prime}$ followed by a
negative identity map:

$\overline{-I_{S_{2}^{\prime}}}\circ\rho_{2}^{\prime}\left(\left[\begin{smallmatrix}B_{0}&&\\\
&b_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{0}&&\\\
&-b_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in-S_{2}$
$\overline{-I_{G_{1}^{\prime}}}\circ\rho_{2}\left(-\left[\begin{smallmatrix}B_{0}&&\\\
&-b_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}B_{0}&&\\\
&-b_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in-G_{1}^{\prime}$

This array does not correspond to a tree because there is a loop
$\verb+blob+\to 3$. So we toggle the diagonality of the cycle.

$\overline{-I_{G_{1}^{\prime}}}\circ\mu_{1}^{\prime}\left(-\left[\begin{smallmatrix}B_{0}&&\\\
&-b_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in G_{1}^{\prime}$

Now we are all set to go through to the end of the step:

$\overline{-I_{S_{2}}}\circ\rho_{2}\left(\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{2}$
$\overline{-I_{S_{2}^{\prime}}}\circ\rho_{2}^{\prime}\left(\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in S_{2}^{\prime}$
$\overline{-I_{T_{2}}}\circ\kappa_{2}\left(\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{2}$

And we continue:

$\overline{-I_{T_{2}^{\prime}}}\circ\kappa_{2}^{\prime}\left(\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\ &&B_{1}\end{smallmatrix}\right]\in T_{2}^{\prime}$
$\overline{-I_{G_{2}}}\circ\mu_{2}\left(\left[\begin{smallmatrix}B_{0}&&\\\
&B_{3}&\\\
&&B_{1}\end{smallmatrix}\right]\right)=\left(\begin{picture}(40.0,20.0)\put(0.0,5.0){1}
\put(7.0,3.0){2} \put(5.0,12.0){3} \put(17.0,5.0){\vector(1,0){15.0}}
\put(35.0,0.0){0} \put(8.0,10.0){\circle{20.0}} \end{picture},(3,1)\right)\in
G_{2}.$

We are almost done, because the last step is always considerably shorter.

##### Step 3

From here we have

$\overline{-I_{G_{2}^{\prime}}}\circ\mu_{2}^{\prime}\left(\begin{picture}(40.0,20.0)\put(0.0,5.0){1}
\put(7.0,3.0){2} \put(5.0,12.0){3} \put(17.0,5.0){\vector(1,0){15.0}}
\put(35.0,0.0){0} \put(8.0,10.0){\circle{20.0}}
\end{picture},(3,1)\right)=\left[\begin{smallmatrix}b_{0}&&\\\ &b_{3}&\\\
&&b_{1}\end{smallmatrix}\right]\in G_{2}^{\prime},$

and finally,

$\rho_{3}\left(\left[\begin{smallmatrix}b_{0}&&\\\ &b_{3}&\\\
&&b_{1}\end{smallmatrix}\right]\right)=-(b_{0},b_{3},b_{1})\in-S_{3}.$

Thus, the Blob Code for the tree $2\to 1\to 3\to 0$ is (3,1).

Notice how the Blob Code differs from the Happy Code: we are constantly
referring back to the altered graph. It turns out we need not use matrices at
all.

##  Chapter 3 Tree Surgery for the Blob Code

A related algorithm for finding the Blob Code for a tree involves
progressively identifying vertices, starting at $n$ and ending with a blob-
vertex consisting of all the vertices from $1$ to $n$. As the blob grows, so
does the code; meanwhile, the number of edges shrinks. The idea, as in the
matrix method, is that if we consider our tree to be a spanning tree within
the complete directed graph (with loops), every pair of vertices is
identifiable. We keep track of the tree in the new graph that would correspond
to our original tree. The difference is that now we ignore the matrices.

###  1 Tree Surgery Algorithm

The algorithm takes as its input a rooted tree (as a set of edges) whose
vertices are the labels $\\{0,1,\dots,n\\}$. The algorithm uses a function
$\verb+path+(x)$ that finds the path (an ordered list of vertices) from $x$ to
0, that is,

$\verb+path+(x)=(x,\verb+succ+(x),\verb+succ+(\verb+succ+(x)),\dots,0).$

Other procedures used are “remove edge” and “add edge.”

Tree Surgery algorithm for the Blob Code
---
begin |
| $\verb+blob+\leftarrow\\{n\\}$
| $\verb+code+\leftarrow()$
| $i\leftarrow 1$
| repeat |
|  |  if |  $\verb+path+(n-i)\cap\verb+blob+\neq\emptyset$ then
|  |  | $\verb+code+\leftarrow(\verb+succ+(n-i),\verb+code+)$
|  |  | remove edge $(n-i)\to\verb+succ+(n-i)$
|  |  | $\verb+blob+\leftarrow\verb+blob+\cup\\{n-i\\}$
|  | else
|  |  | $\verb+code+\leftarrow(\verb+succ+(\verb+blob+),\verb+code+)$
|  |  | remove edge $\verb+blob+\to\verb+succ+(\verb+blob+)$
|  |  | add edge $\verb+blob+\to\verb+succ+(n-i)$
|  |  | remove edge $(n-i)\to\verb+succ+(n-i)$
|  |  | $\verb+blob+\leftarrow\verb+blob+\cup\\{n-i\\}$
|  | $i\leftarrow i+1$
|  until $i=n$
end.

Example:

04321

Beginning with this tree, we create a `blob` containing a single vertex (the
one with the largest label).

##### Step 1

04321

The blob contains only the vertex $4$; $n-i=3$ and $\verb+code+=()$. Does the
path from $3$ to $0$ go through the blob? No. So we follow the then
instructions. We take `succ(blob)`, which is 0, and put it at the beginning of
the code, then delete that edge and add an edge from `blob` to `succ(3)`
(which is 0). Then we delete the edge from $3$ to $0$ and put $3$ into the
blob. The new tree is:

04321

##### Step 2

$n-i=2$ and $\verb+code+=(0)$. Since $i<n$, we continue. Does the path from
$2$ to $0$ go through the blob? Yes. We follow the else in the algorithm. Put
`succ(2)`, which is $3$, at the beginning of the code, get rid of that edge
and put $2$ in the blob.

04321

##### Step 3

Now $n-i=1$ and $\verb+code+=(3,0)$. Since $i>0$, we continue. Does the path
from $1$ to $0$ go through the blob? Yes. Prepend `succ(1)`, which is $3$
again, to the code, get rid of that edge and put $1$ in the blob.

Now we are done. $i=n$ and $\verb+code+=(3,3,0)$, and we stop. Here is the new
tree:

04321

To see what the tree algorithm (which doesn’t even refer to matrices at all)
has to do with the matrix method, we note that the $i^{\rm th}$ row of the
initial matrix $C_{0}^{\prime}$ represents the possible edges out of $i$.
Thus, a row operation that cancels most of the entries of that row obliterates
the information of what the edge out of $i$ was. This resembles the placing of
$i$ into the blob–since there is only one edge leaving the blob, we no longer
know where the individual vertex $i$ was pointing. However, the information is
not entirely lost because the code-in-progress is still in the matrix. In
fact, the row operation followed by the column operation corresponds directly
to the blobbing of vertices and adding to the code.

More specifically, the relationship between the tree method and the matrix
method is as follows: At the end of step $i$, we are in the set $G_{i}$. The
matrix $C_{i}^{\prime}$ represents the graph with vertices $n-i,\dots,n$ in
the blob. The upper-left corner with $n-i$ rows and columns is the Matrix Tree
Theorem matrix for that graph, and the $i$ rows with nothing except $B$ on the
diagonal represent the set of possible codes-in-progress. If the path from
$n-i$ to 0 does not pass through the `blob`, we follow the else at step $i$ in
the tree surgery algorithm, which corresponds to getting to pass through
matrices easily from $G_{i-1}^{\prime}$ to $G_{i}$. If it does (ie, we follow
the then at step $i$ in the tree surgery algorithm), the matrix method will
involve several bounces up and down within the matrices between $S_{i}$ and
$T_{i}^{\prime}$.

###  2 Tree Surgery Is A Bijection

The tree surgery method is reversible. The inverse algorithm takes a code
$(c_{1},c_{2},\dots c_{n-1})$ and finds the corresponding tree:

Algorithm to go from Blob Code to Tree
---
begin |
| $i\leftarrow 0$
| $\verb+blob+=\\{1,\dots,n\\}$
| $\verb+edges+=\\{\verb+blob+\to 0\\}$
| repeat |
|  | $i\leftarrow i+1$
|  | $\verb+blob+\leftarrow\verb+blob+\setminus\\{i\\}$
|  |  if |  $\verb+path+(c_{1})\cap\verb+blob+\neq\emptyset$ then
|  |  | add edge $i\to c_{1}$
|  | else
|  |  | add edge $i\to\verb+succ+(\verb+blob+)$
|  |  | remove edge $\verb+blob+\to\verb+succ+(\verb+blob+)$
|  |  | add edge $\verb+blob+\to c_{1}$
|  | behead `code`
|  until $i=n-1$
end.

It is easy to check that this algorithm undoes the Blob Code algorithm, one
step at a time.

###  3 The Two Methods Give the Same Blob Code

######  Theorem 3.9.

The matrix method and the tree surgery method give the same Blob Code.

######  Proof 3.10.

We assume constant $n$ and proceed by induction on the number of steps $i$
taken so far. The base case is $i=0$, the zeroth step. Before we do anything
(using either method), we have a tree and an empty code. We consider the
vertex $n$ to be a `blob` containing only one label ($n$). At the end of the
$0^{\rm th}$ step, both methods have the same code-in-progress (namely, an
empty code) and the same tree.

Now we assume that at the end of the $(i-1)^{\rm th}$ step, the two methods
result in the same tree and code-in-progress.

At the beginning of step $i$, each method has a pair consisting of a tree with
a `blob` as one of the vertices and a partial code of length $(i-1)$. The
`blob` contains $n-i+1,n-i+2,\dots,n$, so its size is $i$.

The matrix method requires following the involutions through sets of arrays.
Rows $n-i$ through $n-i+1$ look like this in the sequence of matrices:

$C_{i-1}^{\prime}=\\\
\left[\begin{array}[]{r|ccccccc}&1&\dots&n-i&n-i+1&n-i+2&\dots&n\\\
\hline\cr\\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots&&\vdots\\\
n-i&-b_{1}&\dots&B-b_{n-i}&-\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+2}^{n}b_{k}}&\dots&-b_{n}\\\
n-i+1&-b_{1}&\dots&-b_{n-i}&B-\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+2}^{n}b_{k}}&\dots&-b_{n}\\\
n-i+2&0&\dots&0&0&B&\dots&0\\\
\vdots&\vdots&&\vdots&\vdots&\vdots&\ddots&\vdots\end{array}\right]$
$R_{i}=\\\ {\footnotesize\begin{bmatrix}&\vdots&\vdots&\vdots&&\vdots\\\
\dots&B-b_{n-i}&-\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+2}^{n}b_{k}}&\dots&-b_{n}\\\
\dots&-b_{n-i}-B+b_{n-i}&B-\displaystyle{\sum_{n-i+1}^{n}b_{k}}+\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+2}^{n}b_{k}}+\displaystyle{\sum_{n-i+2}^{n}b_{k}}&\dots&-b_{n}+b_{n}\\\
\dots&0&0&B&\dots&0\\\ &\vdots&\vdots&\vdots&&\vdots\end{bmatrix}}$
$R_{i}^{\prime}=\begin{bmatrix}\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
-b_{1}&\dots&B-b_{n-i}&-\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+2}^{n}b_{k}}&\dots&-b_{n}\\\
0&\dots&-B&B&0&\dots&0\\\ 0&\dots&0&0&B&\dots&0\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\end{bmatrix}$
$C_{i}=\begin{bmatrix}\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
-b_{1}&\dots&B-b_{n-i}-\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+2}^{n}b_{k}}&\dots&-b_{n}\\\
0&\dots&-B+B&B&0&\dots&0\\\ 0&\dots&0&0&B&\dots&0\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\end{bmatrix}$
$C_{i}^{\prime}=\begin{bmatrix}\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
-b_{1}&\dots&B-\displaystyle{\sum_{n-i}^{n}b_{k}}&-\displaystyle{\sum_{n-i+1}^{n}b_{k}}&-\displaystyle{\sum_{n-i+2}^{n}b_{k}}&\dots&-b_{n}\\\
0&\dots&0&B&0&\dots&0\\\ 0&\dots&0&0&B&\dots&0\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\end{bmatrix}$

At step $i$ in the matrix method, we are dealing with the sets
$G_{i-1}^{\prime}$ (the set of trees (with a `blob` containing $i$ labels) and
partial codes of length $i-1$), $S_{i},S_{i}^{\prime},T_{i},T_{i}^{\prime}$
(the sets of arrays in the matrices above, respectively), and $G_{i}$ (the set
of trees with a `blob` containing $i+1$ labels together with partial codes of
length $i$).

Suppose we are at the start of step $i$. This means that no matter which
method we are using, we have a tree and a partial code. Let
$\verb+succ+(\verb+blob+)=l$ and $\verb+succ+(n-i)=k$. Also suppose that the
first element in the partial code is $b_{m}$. Note that since we have a tree,
$l\leq n-i$ because all vertices with labels greater than $n-i$ are in the
`blob`.

An application of $\overline{-I_{S_{i}}}\circ\rho_{i}$ leaves us with
$\left[\begin{smallmatrix}\ddots&&&&\\\ &B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\in S_{i}$.

$\overline{-I_{S_{i}^{\prime}}}\circ\rho_{i}^{\prime}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in
S_{i}^{\prime}.$
$\overline{-I_{T_{i}}}\circ\kappa_{i}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in
T_{i}.$

Note that these positive capitalized entries on the diagonal do not disappear
from the matrices.

$\overline{-I_{T_{i}^{\prime}}}\circ\kappa_{i}^{\prime}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in
T_{i}^{\prime}.$

Next we will be applying $\overline{-I_{G_{i}}}\circ\mu_{i}$, and there are
two possible outcomes.

Case 1 Consider the case where the path from $n-i$ to 0 does not go through
the `blob` (that is, $k$ is not inverted in the original tree). If the path
from $k$ to $0$ does not pass through the `blob`, then
$\overline{-I_{G_{i}}}\circ\mu_{i}=(\tau,\gamma)$ where $\gamma$ is the code
from $G_{i-1}$ with $b_{l}$ prepended to it and $\tau$ is a tree containing
the same edges as the tree from $G_{i-1}$ with the following exceptions:
$n-i\to k$ has been deleted, $n-i$ has been added to the `blob`, and the edge
$\verb+blob+\to l$ has been replaced by the edge $\verb+blob+\to k$. This is a
tree because if the path from $n-i$ to 0 does not pass through the `blob`,
then moving the `blob` to the position where $n-i$ was does not create a
cycle.

Note that the effect is exactly the same as the result of the tree surgery
method. Tree surgery would have removed and added exactly those same edges,
and prepended the same label to the code.

Case 2 This is the more complicated case. Here, when we apply $\mu_{i}$, we
don’t get a tree because a cycle would be created (the path from $n-i$ to 0
goes through the `blob`, but now $n-i$ should be in the `blob` with
$\verb+succ+(\verb+blob+)=k$. Hence there is a cycle containing `blob` and
other vertices all of whose labels are less than $n-i$). Thus,
$\overline{-I_{T_{i}^{\prime}}}\circ\mu_{i}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)$ is a negative element in
$T_{i}^{\prime}$ with all entries that correspond to edges in the cycle moved
off the diagonal. In this matrix, row $n-i$ contains $-b_{k}$ in the $k^{\rm
th}$ column; the rest of the off-diagonal entries are higher up in the matrix,
including some unique entry in the $n-i$ column (say $b_{r}$, where $r\geq
n-i$; this corresponds to an edge into `blob`). If $k>n-i$ (that is,
$\verb+succ+(n-i)\in\verb+blob+$), then the matrix will look a little
different than the one below; we will deal with that case later.

Case 2a If $k<n-i$ ($k\neq n-i$ because then we would have a loop in the tree
at the start of the step), we have

$\overline{-I_{T_{i}^{\prime}}}\circ\mu_{i}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&-b_{r}&&&\\\ &&\ddots&&&&\\\ &-b_{k}&&&&\\\ &&&&B_{l}&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\in-T_{i}^{\prime}$

Note that this $-b_{r}$ represents an edge into the `blob` and thus $r$ can be
any label greater than or equal to $n-i$. Also, there may be many vertices in
the cycle that is now off the diagonal.

$\overline{-I_{T_{i}}}\circ\kappa_{i}^{\prime}$ of this gives the same array
in $-T_{i}$. However, $\overline{-I_{T_{i}}}\circ\kappa_{i}$ of that switches
the entries in columns $n-i$ and $n-i+1$, leaving us with an element of
$T_{i}$ because $R_{i}^{\prime}$ only has $-b_{n-i}$ above the diagonal in
column $n-i$. In some row above $n-i$, our array in $T_{i}$ has $-b_{r}$ in
column $n-i+1$; it also has $B_{l}$ in the $(n-i+1,n-i)$ position; nothing
else has moved (the $(n-i,k)$ position contains $-b_{k}$).

$\overline{-I_{T_{i}}}\circ\kappa_{i}\left(-\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&-b_{r}&&&\\\ &&\ddots&&&&\\\ &-b_{k}&&&&\\\ &&&&B_{l}&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &-b_{k}&&&&\\\ &&&B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]$

$\overline{-I_{T_{i}}}\circ\kappa_{i}^{\prime}$ changes the sign of the
$B_{l}$ in row $n-i+1$, leaving us in $-T_{i}$. This new array appears in
$-S_{i}^{\prime}$ and $-S_{i}$ too:
$\overline{-I_{S_{i}^{\prime}}}\circ\kappa_{i}$ takes us to $-S_{i}^{\prime}$
and $\overline{-I_{S_{i}}}\circ\rho_{i}^{\prime}$ takes us to $-S_{i}$.

$\overline{-I_{T_{i}}}\circ\kappa_{i}^{\prime}\left(\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &-b_{k}&&&&\\\ &&&B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\right)=\\\
-\left[\begin{smallmatrix}\ddots&&&&&&\\\ &&&&-b_{r}&&\\\ &&\ddots&&&&\\\
&-b_{k}&&&&\\\ &&&-B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\in-T_{i};$
$\overline{-I_{S_{i}^{\prime}}}\circ\kappa_{i}\left(-\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &-b_{k}&&&&\\\ &&&-B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\right)=\\\
-\left[\begin{smallmatrix}\ddots&&&&&&\\\ &&&&-b_{r}&&\\\ &&\ddots&&&&\\\
&-b_{k}&&&&\\\ &&&-B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\in-S_{i}^{\prime};$

and

$\overline{-I_{S_{i}}}\circ\rho_{i}^{\prime}\left(-\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &-b_{k}&&&&\\\ &&&-B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\right)=\\\
-\left[\begin{smallmatrix}\ddots&&&&&&\\\ &&&&-b_{r}&&\\\ &&\ddots&&&&\\\
&-b_{k}&&&&\\\ &&&-B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\in-S_{i}.$

Now we will end up switching the entries in rows $n-i$ and $n-i+1$:
$\overline{-I_{S_{i}}}\circ\rho_{i}$ has this effect, with the result that our
new array in $S_{i}$ has $B_{l}$ in the $(n-1)^{\rm th}$ diagonal entry and
$b_{k}$ in the $(n-i+1,k)$ position.

$\overline{-I_{S_{i}}}\circ\rho_{i}\left(-\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &-b_{k}&&&&\\\ &&&-B_{l}&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &&&B_{l}&&\\\ &b_{k}&&&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\in S_{i}.$

An application of $\overline{-I_{S_{i}}}\circ\rho_{i}^{\prime}$ changes the
sign of the $b_{k}$ in row $n-i+1$, putting us in $-S_{i}$:

$\overline{-I_{S_{i}}}\circ\rho_{i}^{\prime}\left(\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &&&B_{l}&&\\\ &b_{k}&&&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &&&B_{l}&&\\\ &-b_{k}&&&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\in-S_{i}.$

This same array appears in $-G_{i-1}^{\prime}$ and is what we get by applying
$\overline{-I_{G_{i-1}^{\prime}}}\circ\rho_{i}$. Now when we apply
$\overline{-I_{G_{i-1}^{\prime}}}\circ\mu_{i-1}^{\prime}$ we have a different
cycle. Here, the graph in question has edges $\verb+blob+\to k$ and $(n-i)\to
l$ instead of vice versa. The off-diagonal entries must correspond to a cycle,
so we move the cycle back onto the diagonal, landing in $G_{i-1}^{\prime}$.

$\overline{-I_{G_{i-1}^{\prime}}}\circ\mu_{i-1}^{\prime}\left(-\left[\begin{smallmatrix}\ddots&&&&&&\\\
&&&&-b_{r}&&\\\ &&\ddots&&&&\\\ &&&B_{l}&&\\\ &-b_{k}&&&&&\\\ &&&&&B_{m}&\\\
&&&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&B_{k}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right].$

Note that the only way this array differs from the one we started with at the
very beginning of step $i$ is that the entries in rows $n-i$ and $n-i+1$ have
been interchanged.

Now when we apply $\rho_{i},\rho_{i}^{\prime},\kappa_{i},\kappa_{i}^{\prime}$
with the appropriate negative identity maps in between, we eventually reach

$\left[\begin{smallmatrix}\ddots&&&&\\\ &B_{l}&&&\\\ &&B_{k}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\in T_{i}^{\prime},$

and then

$\overline{-I_{G_{i}}}\circ\mu_{i}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&B_{k}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right),$

which is a tree with edge $\verb+blob+\to l$ (where $n-i$ is now in the
`blob`) together with a code beginning with $(b_{k},b_{m},\dots)$. Since the
tree surgery method would have deleted the edge from $n-i$ to $k$, placed
$n-i$ in the `blob`, prepended $b_{k}$ to the code and left the edge
$\verb+blob+\to l$, the matrix method had exactly the same effect.

Case 2b Here we treat separately the case where
$\verb+succ+(n-i)\in\verb+blob+$. In this case, we have

$\overline{-I_{T_{i}^{\prime}}}\circ\mu_{i}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&\\\
&-b_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in-
T_{i}^{\prime}.$
$\overline{-I_{T_{i}}}\circ\kappa_{i}^{\prime}\left(-\left[\begin{smallmatrix}\ddots&&&&\\\
&-b_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&\\\
&-b_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in-
T_{i}.$

Now $\kappa_{i}$ will switch the columns of two of the entries.

$\overline{-I_{T_{i}}}\circ\kappa_{i}\left(-\left[\begin{smallmatrix}\ddots&&&&\\\
&-b_{k}&&&\\\ &&B_{l}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&\\\
&&-b_{k}&&\\\ &B_{l}&&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in
T_{i}.$
$\overline{-I_{T_{i}}}\circ\kappa_{i}^{\prime}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&&-b_{k}&&\\\ &B_{l}&&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&\\\
&&-b_{k}&&\\\ &-B_{l}&&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\in-T_{i}.$

$\kappa_{i}^{\prime}$ is defined to change the sign of the entry $B_{l}$ in
row $n-i+1$, but nothing else in the array changes. This element also occurs
in the sets $-S_{i}^{\prime}$ and $-S_{i}$, so

$\overline{-I_{S_{i}}}\circ\rho_{i}^{\prime}\overline{-I_{S_{i}^{\prime}}}\circ\kappa_{i}\left(-\left[\begin{smallmatrix}\ddots&&&&\\\
&&-b_{k}&&\\\ &-B_{l}&&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&\\\
&&-b_{k}&&\\\ &-B_{l}&&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\in-S_{i}.$

In Case 2a we actually made it all the way up to the set $G_{i-1}^{\prime}$,
but this time we do not; the next thing that happens is that the entries in
rows $n-i$ and $n-i+1$ are interchanged, with the requisite sign changes:

$\overline{-I_{S_{i}}}\circ\rho_{i}\left(-\left[\begin{smallmatrix}\ddots&&&&\\\
&&-b_{k}&&\\\ &-B_{l}&&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&b_{k}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in
S_{i}.$
$\overline{-I_{S_{i}}}\circ\rho_{i}^{\prime}\left(\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&b_{k}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&-b_{k}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in-
S_{i}.$
$\overline{-I_{G_{i-1}^{\prime}}}\circ\rho_{i}\left(-\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&-b_{k}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=-\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&-b_{k}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in-
G_{i-1}^{\prime}$

This array does not correspond to a tree because there is a loop
$\verb+blob+\to k$

$\overline{-I_{G_{i-1}^{\prime}}}\circ\mu_{i-1}^{\prime}\left(-\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&-b_{k}&&\\\ &&&B_{m}&\\\
&&&&\ddots\end{smallmatrix}\right]\right)=\left[\begin{smallmatrix}\ddots&&&&\\\
&B_{l}&&&\\\ &&B_{k}&&\\\ &&&B_{m}&\\\ &&&&\ddots\end{smallmatrix}\right]\in
G_{i-1}^{\prime}$

Now we can go ahead and apply (with the obvious negative identity maps in
between) $\rho_{i},\rho_{i}^{\prime},\kappa_{i},$ and $\kappa_{i}^{\prime}$,
eventually ending up with this same array in the set $T_{i}^{\prime}$. All of
this had exactly the same effect that the manipulations in Case 2a did–namely,
we interchanged the two entries on the diagonal, switching $b_{k}$ with
$b_{l}$. The same argument we used above shows that this had the same effect
as the tree surgery method.

Since we have accounted for all possible cases, we conclude that these two
methods give the same code at step $i$. Thus at step $n$ the effect of the two
methods is the same, so by induction the Blob Code can be found using either
method.

##  Chapter 4 Tree Surgery for the Happy Code

Considering that the matrix method did not refer back to the graph at each
step, it is surprising that there is a purely bijective method for finding the
Happy Code. In fact, we do have another form of tree surgery for the Happy
Code, so we can avoid resorting to matrices and involutions.

###  1 Tree Surgery Algorithm

Begin by finding the path from $1$ to 0. The method consists of deleting
$\verb+succ+(1)$ from the path and moving it to a separate connected component
of the graph, and forming a cycle with it, then repeating the process. The
algorithm corresponds directly to the matrix/involution algorithm of chapter
1. The algorithm below takes as its input a tree in the form of a set of
edges.

The Tree Surgery Algorithm for Happy Code
---
begin |
| $J\leftarrow\verb+succ+(1)$
|  if $J\neq 0$ | then
|  | repeat |
|  |  | $j\leftarrow\verb+succ+(1)$
|  |  | remove edge $1\to j$
|  |  | add edge $1\to\verb+succ+(j)$
|  |  |  if $j\geq J$ | then
|  |  |  | add edge $j\to j$
|  |  |  | $J\leftarrow j$
|  |  | else
|  |  |  | add edge $j\to\verb+succ+(J)$
|  |  |  | remove edge $J\to\verb+succ+(J)$
|  |  |  | add edge $J\to j$
|  |  until $\verb+succ+(1)=0$
| else
|  | {the Happy Code is practically the same as the naïve code}
| $\verb+code+\leftarrow(\verb+succ+(2),\verb+succ+(3),\dots,\verb+succ+(n))$
end.

This algorithm turns out to be essentially equivalent to the matrix method
shown in Chapter 1.

###  2 An Example

Consider the tree $1\to 3\to 2\to 4\to 0$. Step 1: pull $\verb+succ+(1)=3$ out
of the path from $1$ to $0$ and put it in a cycle.

12403$\hookleftarrow$

One nice thing about the Happy Code is that we don’t have to keep track of the
code as we go; we just read it off at the end. Step 2: pull 2 (the new
$\verb+succ+(1)$) out of the path from $1$ to $0$ and put it in a cycle. Since
it is not the largest vertex in a cycle, we insert it after the largest (which
is $3$).

14032

The last step is to pull $4$ out of the path from $1$ to $0$; it gets a loop
because it is the largest element of the cycles.

104$\hookleftarrow$32

Now we can write down, in order, the successors of $2,3,4$ to find the code:
$(3,2,4)$. Notice how much faster the tree surgery procedure is! Also, it is
nice to know that it would be even faster if the path from $1$ to $0$ were
shorter. Another nice feature of this method is that we no longer have to keep
track of the code as we go; instead, we find it directly once we have finished
performing surgery on the tree. The weight of the happy functional digraph at
the end of the process is equal to the weight of the original tree.

If the tree were branchier, the method would not be any more complicated.
Edges that are not part of the path from 1 to 0 are not affected by tree
surgery; at the end of the surgical procedures the code is the list of the
respective successors of all vertices $\geq 2$.

This tree surgery method is related to Joyal’s proof that there are
$(n+1)^{n-1}$ trees. See §2 for a discussion.

###  3 Tree surgery is a bijection

Again, there is a simple inverse for the Happy Code tree surgery. We assume
that we have a procedure that figures out which vertices are in cycles. The
input is a code $(c_{1},c_{2},\dots,c_{n-1})$.

Algorithm to go from Happy Code to Tree
---
begin |
| $\verb+edges+=\\{1\to 0\\}$
|  for |  $i=2$ to $n$ do
|  | add edge $i\to c_{i-1}$
|  while $\verb+cycles+\neq\emptyset$ do
|  | $J\leftarrow\displaystyle{\max_{j\in\verb+cycles+}j}$
|  | $k\leftarrow\verb+succ+(J)$
|  | add edge $J\to\verb+succ+(k)$
|  | remove edge $J\to k$
|  | add edge $k\to\verb+succ+(1)$
|  | remove edge $1\to\verb+succ+(1)$
|  | add edge $1\to k$
end.

It is clear that this algorithm undoes the Happy Code tree surgery, one step
at a time.

###  4 The Two Methods Give the Same Happy Code

####  1 A Lemma

In order to prove that the tree surgery method gives the same code as the
matrix method, we will need the following lemma. The notion of a cycle being
“active” or “inactive” is content-free. A cycle is “active” if we label it as
active, and inactive otherwise. Actually we will see later that “active”
corresponds to appearing off the diagonal in the matrix, and “inactive”
corresponds to being on the diagonal.

######  Lemma 4.11.

The input for the following algorithm is an active loop at vertex $L$ and an
active cycle (which may also be a loop) containing at least one vertex greater
than $L$. Let $J$ be the largest element in the cycle. Then the output is the
original cycle, now inactive, with $L$ inserted between $J$ and
$\verb+succ+(J)$.

begin |
---|---
| repeat |
|  |  $p\leftarrow$ largest vertex in an active cycle
|  |  $q\leftarrow$ second-largest vertex in an active cycle
|  | $m\leftarrow\verb+succ+(q)$
|  | add edge $q\to\verb+succ+(p)$
|  | remove edge $p\to\verb+succ+(p)$
|  | remove edge $q\to m$
|  | add edge $p\to m$
|  | toggle “activity” of the cycle containing $J$
|  until there are no active cycles.
end.

######  Proof 4.12.

We begin by noting that for a cycle of length $c$, the worst-case scenario is
that each edge (other than $J\to\verb+succ+(J)$) is an ascent and all vertices
are larger than the one in the loop. For such a cycle, the algorithm
terminates after $2^{c}-1$ iterations. In fact, in this situation the
iterative algorithm above is actually equivalent to a recursive algorithm.
This is proven by induction.

The base case is that the cycle is a loop at $J$. This is an Escher cycle of
length $c=1$. The algorithm sets $p=J$, $q=$ the vertex of the loop, and
$m=q$. It removes the loops and adds edges $J\to q$ and $q\to J$, then toggles
the activity of the cycle containing $J$. There are no more active cycles and
the algorithm has inserted $q$ directly after $J$ in its cycle. Furthermore it
has taken $2^{1}-1=1$ step.

The induction hypothesis is that it takes $2^{c-1}-1$ steps to complete the
algorithm if the cycle is an Escher cycle of length $c-1$, and that the result
is that of inserting the loop vertex after $J$ in the cycle.

Now we consider an Escher cycle of length $c$ containing only vertices larger
than the loop vertex. Since each vertex of the cycle is larger than the loop
vertex, the only way to be able to change the edge from the loop vertex (call
it $L$) is to make all but one of the vertices in the cycle inactive.

This is a slow process. The first step of the algorithm removes $J$ from the
cycle, forming a loop which becomes inactive. Next, the second-largest vertex
is removed, and $J$ becomes active again. The following step will form a
2-cycle with these two vertices and make it inactive. The procedure continues
until only the smallest vertex from the cycle (the original $\verb+succ+(J)$)
is left in a loop, with $J$ and the rest of the vertices in an inactive cycle.
By the induction hypothesis, this takes $2^{c-1}-1$ steps because it is
precisely the reverse of adding that smallest vertex to the cycle. The next
step of the iterative algorithm switches the successors of $L$ and the old
$\verb+succ+(J)$ and makes the rest of the vertices active again. The
remaining steps merely undo all of the previous steps, with the exception that
$L$ has been inserted before the old $\verb+succ+(J)$ in all the cycles
containing it. The number of steps before we finish is thus
$2\cdot(2^{c-1}-1)+1=2^{c}-1$. Furthermore, since $L$ has been inserted before
$\verb+succ+(J)$, in the final cycle it appears right after $J$.

Thus we have the result in the case where the cycle is an Escher cycle all of
whose vertices are greater than $L$. However, in fact any cycle reduces to an
Escher cycle of vertices greater than $L$ in the following way: any vertices
smaller than $L$ will never be affected by the edge switching, because $L$ is
active until the bitter end and is never the largest active vertex. So these
vertices can be considered to be chained to their successors and thus do not
effect the length of time the algorithm takes nor its effect. Furthermore, any
vertices that fall in between a vertex and its nearest greater neighbor are
also chained to their successors.

Example:

9236874$\hookleftarrow$Step 0ActiveInactive

When we switch the successors of the two largest vertices, we replace the
edges $9\to 2$ and $8\to 7$ by the edges $9\to 7$ and $8\to 2$. This breaks
our cycle into two cycles, one of which is inactive:

Step 1ActiveInactive82364$\hookleftarrow$97

We repeat. We replace the edges $8\to 2$ and $6\to 8$ by the edges $6\to 2$
and $8\to 8$ (a loop) and reactivate the cycle containing 9.

Step 2ActiveInactive8$\hookleftarrow$2364$\hookleftarrow$97

The two largest active vertices are 8 and 9, so 8 is inserted into 9’s cycle.

Step 3ActiveInactive8792364$\hookleftarrow$

Now that the loop vertex, 4, is the second-largest active vertex, it gets
inserted into the other active cycle. Note that it ends up inserted just
before $\verb+succ+(9)$. This marks the approximate halfway point of the
process. From now on we basically undo everything we did.

Step 4ActiveInactive8794236

Now we switch the edges from 8 and 9, which has the effect of removing 8 from
9’s cycle. Step 5 corresponds to Step 2, only with 4 inserted before 2 and the
activity of 9’s cycle toggled.

Step 5ActiveInactive4236978$\hookleftarrow$

Now 8 will get inserted into the larger cycle, and 9’s cycle is reactivated.
Step 6 corresponds to Step 1, except that 4 has been inserted before 2 and the
cycle containing 9 has the opposite activity.

Step 6ActiveInactive8423697

Step 7 corresponds to Step 0.

Step 7ActiveInactive9423687

The end result is that of inserting 4 into the cycle, right after 9. It took,
in this case, $7=2^{3}-1$ steps, because the cycle we started with is
“equivalent” to the following Escher cycle with vertices larger than 4:

968

Note that 2 and 3 (the two vertices less than 4, our loop vertex) are
“chained” together and to 6, and their outgoing edges never change. Meanwhile,
7 is “chained” to its successor, 9, because the edge into 7 is not an ascent.

####  2 The proof

######  Theorem 4.13.

The tree surgery method gives the same Happy Code as the matrix method.

######  Proof 4.14.

We assume constant $n$ and proceed by induction on the length of the path from
1 to 0. The base case is the case where the tree includes the edge $1\to 0$.
In that case, the tree surgery method doesn’t have to go through the repeat
loop at all and the code is given by
$(\verb+succ+(2),\verb+succ+(3),\dots,\verb+succ+(n))$. The matrix method goes
as follows for the base case: first, an application of
$\overline{-I_{A_{0}^{\prime}}}\circ\phi_{0}$ gives us an array with
$B_{\verb+succ+(i)}$ in the $i^{\rm th}$ diagonal position. Let
$j_{i}=\verb+succ+(i)$. Next,

$\overline{-I_{A_{1}}}\circ\phi_{0}^{\prime}\left(\begin{bmatrix}\lambda&&&&\\\
&B_{0}&&&\\\ &&B_{j_{2}}&&\\\ &&&\ddots&\\\
&&&&B_{j_{n}}\end{bmatrix}\right)=\begin{bmatrix}\lambda&&&&\\\ &B_{0}&&&\\\
&&B_{j_{2}}&&\\\ &&&\ddots&\\\ &&&&B_{j_{n}}\end{bmatrix}\in A_{1}.$

Since the involutions have been defined in such a way that none of these
diagonal entries ever get cancelled by a matrix operation, we have after many
similar applications

$\overline{-I_{A_{n}^{\prime}}}\circ\phi_{n}\left(\begin{bmatrix}\lambda&&&&\\\
&B_{0}&&&\\\ &&B_{j_{2}}&&\\\ &&&\ddots&\\\
&&&&B_{j_{n}}\end{bmatrix}\right)=\begin{bmatrix}\lambda&&&&\\\ &B_{0}&&&\\\
&&B_{j_{2}}&&\\\ &&&\ddots&\\\ &&&&B_{j_{n}}\end{bmatrix}\in A_{n}^{\prime}.$

Now we have

$\overline{-I_{A_{n+1}}}\circ\phi_{n}^{\prime}\left(\begin{bmatrix}\lambda&&&&\\\
&B_{0}&&&\\\ &&B_{j_{2}}&&\\\ &&&\ddots&\\\
&&&&B_{j_{n}}\end{bmatrix}\right)=B_{0}B_{j_{2}}\dots B_{j_{n}}\in A_{n+1}.$
$\phi_{n+1}\left(B_{0}B_{j_{2}}\dots B_{j_{n}}\right)=-b_{0}B_{j_{2}}\dots
B_{j_{n}}\in-A_{n+1}^{\prime}.$

Here, since $j_{i}=\verb+succ+(i)$, we end up with the same code we got by
tree surgery. Thus the base case is true.

Our induction hypothesis is that the two methods give the same code for all
happy functional digraphs where the path from 1 to 0 is of length $i-1$. We
show that if we start with a functional digraph whose path from 1 to 0 is of
length $i$, both methods will manipulate the graph into one with a shorter
path from 1 to 0.

The length of the path from 1 to 0 is $i$. As we start, we have an array with
all entries on the diagonal. We will automatically (as in the base case) make
it down to $A_{n+1}$ by a sequence of involutions with no complications,
because none of these diagonal entries get cancelled in the row operation
arithmetic. Let $\verb+succ+(i)=j_{i}$ and $j_{1}=r$. Then

$\overline{-I_{A_{n+1}}}\circ\phi_{n}^{\prime}\circ\dots\circ\overline{-I_{A_{0}^{\prime}}}\circ\phi_{0}\left(\begin{bmatrix}\lambda&&&&\\\