Title:  Permanents of Circulants
Speaker: Yiu Cho Leung

HKUST

Date: Friday Dec 2, 2005
Time 11-12 Venue: Room 3464, HKUST   


Abstract 
Calculating the permanent of a 0/1-matrix is a #P-complete 
problem but there are some classes of structured matrices 
for which the permanent is calculable in polynomial time.  
The most well-known example is the fixed-jump 0/1
circulant matrix  which, using algebraic techniques,
was shown by Minc to satisfy a constant-coefficient 
fixed-order recurrence relation.

In this note we show how, by interpreting the problem 
as calculating the number of  cycle-covers in a directed 
circulant graph, it is straightforward to reprove Minc's
result using  combinatorial methods.  This is a two step
process: the first step is to show that the cycle-covers 
of directed circulant graphs  can be evaluated using a 
transfer matrix argument.  The second is to show that 
the associated transfer matrices, while very large, actually 
have much smaller characteristic polynomials than would a-priori 
be expected.
 
An important consequence of this viewpoint is that, 
in combination with a new recursive decomposition of 
circulant-graphs,  it permits extending Minc's result 
to calculating the permanent  of the much larger
class of circulant matrices with  non-fixed (but linear) jumps.

This is joint work with Yajun Wang and Mordecai Golin