English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Calculating the permanent of a (0,1) matrix is a #P-complete problem butthere are some classes of structured matrices for which the permanent iscalculable in polynomial time. The most well-known example is the fixed-jump(0,1) circulant matrix which, using algebraic techniques, was shown by Minc tosatisfy a constant-coefficient fixed-order recurrence relation.  In this note we show how, by interpreting the problem as calculating thenumber of cycle-covers in a directed circulant graph, it is straightforward toreprove 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 graphscan be evaluated using a transfer matrix argument. The second is to show thatthe associated transfer matrices, while very large, actually have much smallercharacteristic polynomials than would a-priori be expected.  An important consequence of this new viewpoint is that, in combination with anew recursive decomposition of circulant-graphs, it permits extending Minc'sresult to calculating the permanent of the much larger class of circulantmatrices with non-fixed (but linear) jumps. It also permits us to count othertypes of structures in circulant graphs, e.g., Hamiltonian Cycles.

Permanents of Circulants: a Transfer Matrix Approach (Expanded Version)