Mathematics – Combinatorics
Scientific paper
2007-08-07
Mathematics
Combinatorics
33 pages, 8 figures
Scientific paper
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 new 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. It also permits us to count other types of structures in circulant graphs, e.g., Hamiltonian Cycles.
Golin Mordecai J.
Leung Yiu Cho
Wang Yajun
No associations
LandOfFree
Permanents of Circulants: a Transfer Matrix Approach (Expanded Version) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Permanents of Circulants: a Transfer Matrix Approach (Expanded Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Permanents of Circulants: a Transfer Matrix Approach (Expanded Version) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-170235