Browse Prior Art Database

Skew Symmetric Matrices aced the Pfaffian

IP.com Disclosure Number: IPCOM000128368D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 30K

Publishing Venue

Software Patent Institute

Related People

Omer Egecioglu: AUTHOR [+3]

Abstract

The Pfaffian of the symbols a=, with i < j has a combinatorialinterpretation as the signed weight generating function of perfect matching in the complete graph. By properly specializing the variables, this generating function reduces to the signed weight generating function for the perfect matchings in an arbitrary simple graph. We construct a weight and sign preserving bijection between two appropriately con-structed spaces of permutations: permutations with even cycles and pairs of involutions without fixed points. This bijection gives a combinatorial proof that the determinant of a zero-axial skew symmetric matrix is equal to the square of the Pfaflian. ' Research Supported in part by NSF Grant No. DCI2-8603722.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Skew Symmetric Matrices aced the Pfaffian

Omer Egecioglu Department of Computer Science August 1986

Skew symmetric matrices and the Pfafhan

Omer Egecioglu

Department of Computer Science University of California Santa Barbara, Santa Barbara, CA 93106

ABSTRACT

The Pfaffian of the symbols a=, with i < j has a combinatorialinterpretation as the signed weight generating function of perfect matching in the complete graph. By properly specializing the variables, this generating function reduces to the signed weight generating function for the perfect matchings in an arbitrary simple graph. We construct a weight and sign preserving bijection between two appropriately con-structed spaces of permutations: permutations with even cycles and pairs of involutions without fixed points. This bijection gives a combinatorial proof that the determinant of a zero-axial skew symmetric matrix is equal to the square of the Pfaflian. ' Research Supported in part by NSF Grant No. DCI2-8603722.

1.0 Introduction

Let G = (V, E) be a simple graph with vertex set Y and edge set E . A subset AT of edges in G such that no edge in M is incident upon the same vertex in Y is a matching in G . If every vertex in V is incident to some edge in M , then the matching is perfect. If G has a perfect matching then clearly # Y = 2m for some m . Let S2m denote the set of permutations on 2m symbols. A perfect matching M in G can be viewed as an involution Q,,3 without fixed points in S2m by interpreting the endpoints of edges in M as forming the 2-cycles of Q,,, . We associate a sign to Q,,t by taking the parity of the fundamental transform of QM as defined by Foata [2]. Next we construct the space P12M whose elements are ordered pairs (a , ,Q) of involutions without fixed points with weight 2m 2m

(Equation Omitted)

The sign of the pair (cx , ,Q) is the product of the parities of the fundamental transforms of each one of the components a and 0 . Let E,m denote the collection of permutations in Sam whose cycle decomposition contains only cycles of even lengths. E2m is turned into a weighted, signed space by set-ting for each

(Equation Omitted)

i=1 where i(a) and f(Q) are the number of inversions and the number of falls of Q, respec-tively. In this combinatorial setting, constructing a weight and sign preserving bijection between the spaces PIZm and E2m gives a combinatorial proof that the square of the Pfaffian of the symbols

University of California at Santa Barbara Page 1 Dec 31, 1986

Page 2 of 10

Skew Symmetric Matrices aced the Pfaffian

a=j is the determinant D2m of the corresponding skew sym-metric matrix in the aij 's. The proof of the above result about the PfafTian goes back to Pfaff [7], Jacobi [-(), Cayley [1] and Horner
[3]. A detailed account of their individual contributions can be found in the comprehensive treatise by Muir (5]. Tutte (8J gave a graph theoretic interpretation of skew symmetric matri...