Matrix Tree Theorem

The Matrix Tree Theorem
Janneke van den Boomen June 29, 2007

The Matrix Tree Theorem
Janneke van den Boomen

Bachelor Thesis Supervisor: Dr. W. Bosma Second Reader: Dr. A.R.P. van den Essen Opleiding Wiskunde Radboud Universiteit Nijmegen

Contents
1 Introduction 2 Properties 2.1 Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Matrices and trees . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Binet-Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Proof of the Matrix Tree Theorem 4 Implementation in magma 5 Special formulas 5 7 7 7 8 9 11 12 13

5.1 Complete graph . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.2 Complete bipartite graph . . . . . . . . . . . . . . . . . . . . . 15 5.3 Wheels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6 References 17

4

1

Introduction

In a connected graph G, it is (usually) easy to find a tree that contains all the vertices and some edges of G; such a subgraph is called a a spanning tree. And maybe one can find two, or three such trees. But how many spanning trees does that graph contain? That is what Gustav Robert Kirchhoff (1824-1887) was wondering. Kirchhoff was a German physicist, who contributed to the fundamental understanding of electrical circuits, spectroscopy and radiation. Kirchhoff found an answer to this question, which is formulated in the Matrix Tree Theorem. By means of this theorem, solutions to (among others) linear resistive electrical network problems can be expressed much easier. To formulate the Matrix Tree Theorem, we first have to define a matrix AG . Definition 1.1 Let G be a connected graph with n vertices and m edges (numbered arbitrarily). We orient each edge random. The incidence matrix of G is the n × m matrix AG = [aij ] with   +1 if the j