Permanents of circulants: a transfer matrix approach (extended abstract)
From MaRDI portal
Publication:5233154
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.
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
Cited in
(4)
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)
