Combinatorial algorithms for determinant based problems

Abstract

The thesis started with the early history and development of the theory of determinants. All the important results up to the 1880s were presented through a computing perspective. Pfaffians are closely related to determinants; in fact Knuth [Knu96] states that Pfaffians are more fundamental than determinants. We described the early history and development of the theory of Pfaffians and the motivation for their continued interest. The fundamental framework of this thesis is the representation of numbers as graphs. We showed several graphical representations of numbers and showed that Fibonacci graphs are the most optimal building blocks. Combinatorial algorithms for determinant, Pfaffian and counting spanning trees are the other facet of this framework. We gave the first fully combinatorial polynomial?time algorithm that computes the sign of a Pfaffian correctly. We showed that this is used to show that counting perfect matchings in a planar graph is in GapL. We showed that there is a combinatorial polynomial?time algorithm for counting the number of spanning trees in a graph. We described the implementation issues of the combinatorial algorithms for determinant, Pfaffian and counting spanning trees and tabulated the experimental results. The original contributions of this thesis can be summarized thus:

We give a computational perspective of the rich history and development of the theory of determinants and Pfaffians. We give an alternate representation of numbers as graphs. We show that a particular type of graph which we call Fibonacci graph is the optimal representation for numbers as graphs. We give a tight upper bound for the number of clows (closed walks) in the complete graph KnK_nKn? on nnn vertices. We give a fully combinatorial polynomial?time algorithm for computing the Pfaffian of a skew?symmetric matrix. We show that counting the number of perfect matchings in a planar embeddable graph is in GapL. We give a polynomial?time combinatorial algorithm for counting the number of spanning trees in a graph. We provide efficient implementations of the combinatorial algorithms for determinant, Pfaffian and counting spanning trees. These implementations have been extensively checked on large matrices.

We conjecture that all the determinant and Pfaffian identities and theorems stated in Chapters 2 and 3 can be proved combinatorially using clows and pclows. We have sufficient reason to believe that such proofs exist because all the computational algorithms for computing the determinant such as Samuelson, Berkowitz, Csanky, Chistov and Leverrier have combinatorial proofs in terms of clow sequences or its minor variants. In Chapter 5, we showed an upper bound of nnn^nnn for the number of clow sequences in a complete graph, KnK_nKn?. We conjectured there that the closed?form expression for the number of clow sequences is n?(n?1)n?1n \cdot (n - 1)^{n - 1}n?(n?1)n?1. A proof of this is left open as of this writing. The representation of numbers as graphs needs further investigation. We would like to explore the impact of this representation on graph algorithms and computations on graphs. Additionally, we believe that the optimality of the Fibonacci graph with respect to the number of paths has far greater significance than we have explored in this thesis. Counting the number of Eulerian paths has a determinant?based algorithm. We would like to explore the possibility of a clow?based combinatorial algorithm for the problem.