Permanents of circulants: a transfer matrix approach (extended abstract)

DOI10.1137/1.9781611972962.11zbMATH Open1423.15007arXiv0708.0907OpenAlexW4206263841MaRDI QIDQ5233154FDOQ5233154

Authors:

Publication date: 16 September 2019

Published in: 2006 Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/0708.0907

Recommendations

• scientific article; zbMATH DE number 1577997
• On the number of different permanents of some sparse (0,1)-circulant matrices.
• How fast can one compute the permanent of circulant matrices?
• Recurrence formulas for permanents of (0,1)-circulants
• Computation of sparse circulant permanents via determinants

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Boolean and Hadamard matrices (15B34) Determinants, permanents, traces, other special matrix functions (15A15)

Cited In (4)

• Title not available (Why is that?)
• Permanental compounds and permanents of (0,1)-circulants
• Title not available (Why is that?)
• On the permanents of circulant and degenerate Schur matrices

This page was built for publication: Permanents of circulants: a transfer matrix approach (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233154)