Exact Recursive Calculation of Circulant Permanents: A Band of Different Diagonals inside a Uniform Matrix

Abstract

We present a finite-order system of recurrence relations for the permanent of circulant matrices containing a band of k any-value diagonals on top of a uniform matrix (for $k=1,2$ and 3) and the method for deriving such recurrence relations, which is based on the permanents of the matrices with defects. The proposed system of linear recurrence equations with variable coefficients provides a powerful tool for the analysis of the circulant permanents, their fast, linear-time computing; and finding their asymptotics in a large-matrix-size limit. The latter problem is an open fundamental problem. Its solution would be tremendously important for a unified analysis of a wide range of the nature’s $♯P$-hard problems, including problems in the physics of many-body systems, critical phenomena, quantum computing, quantum field theory, theory of chaos, fractals, theory of graphs, number theory, combinatorics, cryptography, etc.

1. Introduction: Significance and Complexity of Circulant Permanents

The permanent, $\mathrm{per}C$, and the determinant, $\det C$, of a $n\times n$ matrix C correspond to two major operations—the symmetrization and the anti-symmetrization, respectively. This fact predetermines their fundamental role in the quantum theory of many-body systems, which are either bosonic (symmetric) or fermionic (anti-symmetric). The permanents are well-known in mathematical physics, especially in quantum computing science and the quantum field theory of interacting Bose fields [1,2,3,4,5,6,7,8]. However, compared to the determinants, the permanents are much more difficult to compute and they account for much more complicated many-body phenomena, such as the critical phenomena in phase transitions. For instance, an exact general solution to a long-standing three-dimensional Ising model [9] has been represented recently in terms of the permanent of a circulant matrix [10,11,12].

The permanents have been studied in mathematics for more than a century (for a review, see [13,14,15,16,17,18]), the most actively after discovery of the Ryser’s algorithm [19], the publication of the comprehensive book “Permanents” [13], proof of the famous Valiant’s theorem stating that their computing is a $♯P$-hard problem within the computational complexity theory [20] and a recent development of a fully polynomial randomized approximation scheme [21,22] for their computing. In fact, the permanents are intimately related to many fields of mathematics, including matrix algebra, combinatorics, number theory, theory of symmetric polynomials, discrete Fourier transform, q-analysis, dynamical systems, generalized harmonic and wavelet analysis [23,24,25] and computational complexity theory. For instance, in combinatorics, matching in the bipartite graphs is enumerated by the permanents of 0-1 matrices [26]. Another example is provided by the permanent of the Schur matrix, which is equal to a sum that explicitly includes the ordinary Möbius function of the number theory [27]. Importantly, the permanents play a significant role in the algebraic complexity theory as universal polynomials [28]. Nevertheless, despite amazing recent activity and interest (see, e.g., [1,5,6,7,8,15,18,22,29,30,31,32,33,34,35,36,37,38] and references therein), the methods for analyzing and calculating the permanents and their asymptotics for most of large matrices remain illusive.

The general deterministic algorithms [19,36,37,38] for computing the permanent of a $n\times n$ matrix with $n^2$ entries require exponentially large number of operations, at least ∼$n{2}^n$. A circulant matrix, whose permanent has been analyzed by many authors [13,39,40,41,42,43,44], has just n independent parameters, as per Definition 2 below, and requires smaller, but still exponentially large number of operations. The point is [45] that a circulant graph on n vertices with enough nonzero entries contains an arbitrary subgraph of size proportional to $n^{1/2}$. No efficient algorithm has been found for computing the permanent of a general circulant matrix of a large or moderate size in polynomial time.

The situation could be very different for the permanent of matrices with a fixed number k of any-value parameters which is not increasing with the matrix size n or of a special structure, say, confining all nonzero entries to a band or restricted diagonal or rectangular blocks. One expects that for some classes of matrices with such additional constraints, computing their permanents is possible in polynomial time, and hence, accessible for applications. The latter has been demonstrated for matrices whose nonzero entries are confined to a band or just a few diagonals [13,32,44,46,47,48]. Efficient computing of the permanent of very sparse circulants [35,45,49] is another example. In the present paper we consider an alternative class of matrices—the circulant matrices composed of a band of k any-value diagonals on top of a uniform $n\times n$ matrix.

The presence of nonzero, even constant entries spreading over an entire two-dimensional matrix plane in all directions drastically changes the behavior and asymptotics of the permanent and significantly complicates the problem of its calculation. The two aforementioned classes of matrices, with zero and nonzero entries outside a finite number of diagonals, constitute two different universality classes for permanents. Based on the reduction of the critical behavior in phase transitions to the asymptotics of the permanent of a mean-field correlation matrix [10,11,12], these two classes could be related to two scaling asymptotics of the critical phenomena in the disordered and ordered phases, respectively. As is known from a phenomelogical renormalization-group approach [9,50], they are very different, since the correlation matrix abruptly tends to zero in the disordered phase, but remains nonzero for a very long distance due to long-range correlations in the ordered phase. Note that we can choose any (except the truly special, trivial zero) constant nonzero value, $c=1$ or $c\ne 1$, for the entries of the uniform background matrix (see Equation (22)) in the considered model of the circulant matrix with a band of k any-value diagonals since it amounts to a simple rescaling of the permanent, as is explained in Remark 3. Computing the permanent of such matrices is very important in a number of applications in mathematics, physics, computing, information systems, cryptography, etc. (see the references above). We aim at finding a system of recurrence relations for it. It would allow one to compute the permanent of such matrices in linear time.

A base goal of the paper is to present a new method for finding the aforementioned system of recurrence relations: Recursion of permanents of the matrices with defects. One specific goal is to demonstrate practical ways of this method and communicate the new results on finding the system of recurrence relations for calculating nontrivial, multi-parametric circulant permanents with a band of $k=1,2$ or 3 different diagonals. In particular, such a recurrence, in the case of the zero-valued k-diagonal band, provides a solution to a famous problem of finding a finite recurrence for the k-ménage numbers, or k-discordant permutations (for a discussion of k-ménage numbers, see [51,52,53,54,55,56,57,58]). For calculating the permanents, especially of matrices whose entries are continuous variables, the proposed method of the recursion of permanents with defects is more powerful and efficient than a widely known method of rook polynomials [17,51,52,53,54,57]. The former incorporates all entire analytic, algebraic and combinatorial information on the permanental polynomial of k variables. The latter is limited to just one artificial variable and mainly combinatorial information on the associated 0-1 matrices and is not directly suitable for finding the permanent as a function of all k variables and revealing its asymptotics.

Notation 1.

For brevity, we denote the permanent, $C_n=perC$, of any $n\times n$ matrix C by a symbol of its size, n, placed next to the matrix’s symbol as a subscript which simultaneously plays a part of a recursion variable.

2. Definitions

Definition 1.

The permanent and determinant of a $n\times n$ matrix $C=\left(c_p^q\right)$ are

$$C_n\equiv perC=\sum _{\sigma \in S_n}\prod _{p=1}^n{c}_p^{\sigma \left(p\right)}\mathrm{and}\det C=\sum _{\sigma \in S_n}\mathrm{sgn}\left(\sigma \right)\prod _{p=1}^n{c}_p^{\sigma \left(p\right)}.$$

(1)

The sums run over the symmetric group $S_n$, i.e., over the permutations σ of $1,2,\dots ,n$.

Definition 2.

The $n\times n$ circulant matrix $C=Circ(c_0,c_1,\dots ,c_{n-1})$ with the p-th row and q-th column entry $c_p^q$ is the matrix with the rows obtained via consecutive cyclic permutations of the entries of the first row $(c_0,c_1,\dots ,c_{n-1})$, or via the discrete Fourier transform of the set of its eigenvalues $\{{\lambda }_l\mid l=1,\dots ,n\}$:

$$c_p^q\equiv c_{q-p\left(\mathrm{mod}n\right)}=\frac{1}{n}\sum _{l=1}^n{\lambda }_l{e}^{2\pi i(q-p)(l-1)/n},{\lambda }_l=\sum _{j=0}^{n-1}{c}_j{e}^{2\pi ij(l-1)/n}.$$

(2)

Next, we consider a circulant matrix $C=Circ(c_0,\dots ,c_{k-1},1,\dots ,1)$, say,

$$C=Circ(c_0,c_1,c_2,1,\dots ,1)=\left[\begin{array}{cccccccc}{c}_0& c_1& c_2& 1& \cdots & 1& 1& 1\\ 1& c_0& c_1& c_2& \cdots & 1& 1& 1\\ 1& 1& c_0& c_1& \cdots & 1& 1& 1\\ 1& 1& 1& c_0& \cdots & 1& 1& 1\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 1& 1& 1& 1& \cdots & c_0& c_1& c_2\\ c_2& 1& 1& 1& \cdots & 1& c_0& c_1\\ c_1& c_2& 1& 1& \cdots & 1& 1& c_0\end{array}\right],$$

(3)

whose first row includes a set $\{c_0,\dots ,c_{k-1}\}$ of just $k=1,2,\mathrm{or}3$ any-value entries, and the rest of the first row’s entries equal unity: $c_q=1,q=k,\dots ,n-1$. In other words, the circulant matrix C contains a band of k any-value diagonals inside a uniform $n\times n$ matrix $J=\left(J_p^q\right)$ with unity entries $J_p^q=1;p,q=1,\dots ,n$.

It is convenient to derive the recurrence relations for its permanent on the basis of the following two matrices A and B defined for any matrix size $n\ge k$.

Definition 3.

The matrix $A=\left(a_p^q\right)$ is obtained from the original circulant matrix $C=Circ(c_0,\dots ,c_{k-1},1,\dots ,1)$ by replacing all entries in the lower left ($p-q>n-k$) triangle of entries with unities:

$$a_p^q=c_p^q\mathrm{if}p-q\le n-k;a_p^q=1\mathrm{if}p-q>n-k.$$

(4)

Definition 4.

The matrix $B=\left(b_p^q\right)$ is obtained from the shifted circulant matrix

$$\tilde{C}=Circ(c_1,\dots ,c_{k-1},1,\dots ,1,c_0)\equiv \left({\tilde{c}}_p^q\right)$$

(5)

by replacing the upper rightmost and lower leftmost entries ${\tilde{c}}_1^n$ and ${\tilde{c}}_n^1$ with 1s (hereinafter, ${\delta }_{q,j}$ is the Kronecker delta):

$$b_p^q={\tilde{c}}_p^q+(1-{\tilde{c}}_n^1){\delta }_{p,n}{\delta }_{q,1}+(1-{\tilde{c}}_1^n){\delta }_{p,1}{\delta }_{q,n}.$$

(6)

Definition 5.

Two auxiliary matrices, $A^{\prime }=\left({a_p^{\prime }}^q\right),R=\left(r_p^q\right)$, with entries

$${a_p^{\prime }}^q=a_p^q+(c_2-1){\delta }_{p,n}{\delta }_{q,1},r_p^q={\tilde{c}}_p^q+\sum _{l=2}^n(1-c_l^1){\delta }_{p,l}{\delta }_{q,1}$$

(7)

are used to prove the Theorem. The $A^{\prime }$ differs from A, Equation (4), just by the lowest left entry $c_2$. The R is obtained from the shifted circulant $\tilde{C}$, Equation (5), by replacing all entries in the first column, except the upper one, with unity.

Definition 6.

A symbol $M^{\left(l\right)}$ stands for a matrix $M=\left(m_p^q\right)$ whose l-th column is replaced with a column of 1s—that is, $m_p^{\left(l\right)q}=m_p^q+(1-m_p^q){\delta }_{q,l}$.

We found that in order to get the closed, finite-order recurrence relations, we need to consider the permanent of the matrices with a unity-column defect, namely, $C_n^{\left(l\right)},A_n^{\left(l\right)},B_n^{\left(l\right)}$, and the following sums of such permanents.

Definition 7.(Here a sum’s index in the parenthesis, $\left(n\right)$, is a matrix size plus 1.)

$$A_{\left(n\right)}=\sum _{l=1}^{n-1}{A}_{n-1}^{\left(l\right)},B_{\left(n\right)}=\sum _{l=1}^{n-1}{B}_{n-1}^{\left(l\right)},C_{\left(n\right)}=\sum _{l=1}^{n-1}{C}_{n-1}^{\left(l\right)}=(n-1)C_{n-1}^{\left(1\right)}.$$

(8)

Definition 8.

A star $(\ast )$-conjugation of any k-diagonal-band matrix M with defects means a matrix $M(\ast )$ obtained from M by just renaming its parameters in the inverse order: $c_0,\dots ,c_{k-1}\to c_{k-1},\dots ,c_0$.

Definition 9.

$M\left(i\right|j)$ is the $(n-1)\times (n-1)$ submatrix obtained from a $n\times n$ matrix M after deleting the i-th row and j-th column. $M\left(i_1{i}_2\right|j_1{j}_2)$ is the $(n-2)\times (n-2)$ submatrix obtained from a $n\times n$ matrix M after deleting rows $i_1$ and $i_2$, and columns $j_1$ and $j_2$.

3. Method: Recursion of Permanents with Defects

We calculated the circulant permanent $C_n=\mathrm{per}C$ via the permanents of a few matrices obtained from the circulant C by introducing certain defects, like those in the Definitions 3–9. The set of those matrices with defects is dictated by a requirement of its self-closure in the course of the reducing their permanents to the permanents of the lower-size matrices by means of the Laplace expansion [14], certain relations between different permanents valid due to particular patterns and symmetries of the k-diagonal-band circulants; and various matrix transformations leaving the permanent invariant, such as transposing with respect to the main or minor diagonals, and permutations of rows or/and columns. In particular, the matrices such as A and B in Equations (4) and (6) have the non-unity entries just within the main band of the k diagonals. The matrix R in Equation (7) whose first-column entries are all unities, except the upper one, is instrumental for establishing a recursive coupling with the sums of permanents, Equation (8), via the Laplace expansion over the first row. Some important matrices with defects arise naturally as minors in the Laplace expansion or Lemmas 1 and 2 below.

In general, we introduce the matrices with defects located as close to the corners of the matrices as possible in order to avoid recursive chains of matrices with the defects penetrating deeper and deeper inside the matrices.

The permanent of each matrix with defects is associated with a particular combinatorial meaning. The permanents of, say, circulant C and matrix with defects A, in the case of zero parameters $c_0=\dots =c_{k-1}=0$, are equal to the famous k-ménage numbers for the circular-table and straight-table problems, respectively.

One of the key ingredients of the method is explicit involvement of the sums of permanents over the matrices with the unity-column or unity-row defects (see Equation (8)) into the permanents’ recurrence relations.

The star $(\ast )$-conjugation introduced in Definition 8 reveals an important symmetry and helps to reduce the number of matrices with defects needed for achieving completeness of the system of recurrence relations.

Especially, we employ the following lemmas which immediately follow from the permanent’s definition and the Laplace expansion of the permanent along the $p^{\ast }$-th row or the $p^{\ast }$-th row and $q^{\ast }$-th column, etc.

Lemma 1.

If a matrix $\tilde{M}=\left({\tilde{m}}_p^q\right)$ differs from a matrix $M=\left(m_p^q\right)$ by just the entries (defects) ${\tilde{m}}_{p^{\ast }}^q$ in a single row $p=p^{\ast }$, then its permanent ${\tilde{M}}_n=per\tilde{M}$ differs from the permanent $M_n=perM$ of the unperturbed matrix by just the sum over separate linear corrections per each $p^{\ast }$-row entry, $({\tilde{m}}_{p^{\ast }}^q-m_{p^{\ast }}^q)$, multiplied by the corresponding permanental minor, i.e., by the permanent $M{\left(p^{\ast }\right|q)}_{n-1}=perM\left(p^{\ast }\right|q)$ of the submatrix $M\left(p^{\ast }\right|q)$ of the lower size $n-1$:

$${\tilde{M}}_n=M_n+\sum _{q=1}^n({\tilde{m}}_{p^{\ast }}^q-m_{p^{\ast }}^q)M{\left(p^{\ast }\right|q)}_{n-1}.$$

(9)

A similar representation is valid when all defects are located in a single column.

Lemma 2.

If a matrix $\tilde{M}=\left({\tilde{m}}_p^q\right)$ differs from a matrix $M=\left(m_p^q\right)$ by just the entries (defects) ${\tilde{m}}_{p^{\ast }}^q$ in a row $p=p^{\ast }$ and ${\tilde{m}}_p^{q^{\ast }}$ in a column $q=q^{\ast }$, then its permanent ${\tilde{M}}_n=per\tilde{M}$ differs from the permanent $M_n=perM$ of the unperturbed matrix by the following superposition of (i) the separate linear corrections per each $p^{\ast }$-row entry and each $q^{\ast }$-column entry, multiplied by the corresponding permanental minor of the size $n-1$, and (ii) the cross-correlated quadratic corrections per each pair of defects, one from the $p^{\ast }$-row and one from the $q^{\ast }$-column, multiplied by the permanent of the corresponding submatrix $M\left(p^{\ast }p\right|q{q}^{\ast })$ of the size $n-2$:

$$\begin{array}{cc}{\tilde{M}}_n=M_n\hfill & +{\displaystyle \sum _{q=1}^n}({\tilde{m}}_{p^{\ast }}^q-m_{p^{\ast }}^q)M{\left(p^{\ast }\right|q)}_{n-1}+{\displaystyle \sum _{p=1,p\ne p^{\ast }}^n}({\tilde{m}}_p^{q^{\ast }}-m_p^{q^{\ast }})M{\left(p\right|q^{\ast })}_{n-1}\hfill \\ \hfill & +{\displaystyle \sum _{q=1,q\ne q^{\ast }}^n}{\displaystyle \sum _{p=1,p\ne p^{\ast }}^n}({\tilde{m}}_{p^{\ast }}^q-m_{p^{\ast }}^q)({\tilde{m}}_p^{q^{\ast }}-m_p^{q^{\ast }})M{\left(p^{\ast }p\right|q{q}^{\ast })}_{n-2}.\hfill \end{array}$$

(10)

Note that the defect ${\tilde{m}}_{p^{\ast }}^{q^{\ast }}$ at the intersection of the $p^{\ast }$-th row and $q^{\ast }$-th column contributes to the right-hand side of Equation (10) just once through a linear correction and does not contribute at all to the cross-correlated quadratic corrections.

A generalization of Lemmas 1 and 2 to a general case when the defects are located in the three or more different rows and columns is straightforward.

4. The Permanent of a Uniform Circulant Matrix with One Any-Value Diagonal ($\mathbf{k}=\mathbf{1}$) and the Rencontres Numbers

In this section, we consider the simplest nontrivial case of a uniform circulant $n\times n$ matrix with a band of k any-valued diagonals, namely, the case of just one $(k=1)$ diagonal with the entries $c_0$ inside the matrix J of all 1s:

$$C=\left[\begin{array}{ccccc}{c}_0& 1& \cdots & 1& 1\\ 1& c_0& \cdots & 1& 1\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& 1& \cdots & c_0& 1\\ 1& 1& \cdots & 1& c_0\end{array}\right].$$

(11)

Proposition 1.

The recurrence equation for the permanent of this circulant is

$$C_n=n{C}_{n-1}+(c_0-1)[C_{n-1}-(n-1)C_{n-2}],\mathrm{or}{C}_n-n{C}_{n-1}={(c_0-1)}^n,$$

(12)

and yields the exact solution for the permanent,

$$C_n=e^{c_0-1}\Gamma (n+1,c_0-1),$$

(13)

via the well-known upper incomplete gamma function

$$\Gamma (n+1,x)={\int }_x^{\infty }{t}^n{e}^{-t}dt.$$

(14)

Proof. 

The permanent is given by the Laplace expansion over the first row as

$$C_n=c_0{C}_{n-1}+C_{\left(n\right)}$$

(15)

via the sum of permanents $C_{\left(n\right)}$, Equation (8), which consists of $n-1$ equal permanents of the circulant matrices with a 1’s-column defect $C_{n-1}^{\left(q\right)}=C_{n-1}^{\left(1\right)}(q=1,\dots ,n-1)$. The latter can be evaluated by means of Lemma 1, and so we have

$$C_{\left(n\right)}=(n-1)C_{n-1}^{\left(1\right)},C_{n-1}^{\left(1\right)}=C_{n-1}+(1-c_0)C_{n-2}.$$

(16)

The first part of Equation (12) follows from (15), (16). It is immediate to solve it for

$$C_n-n{C}_{n-1}={(c_0-1)}^n$$

(17)

via a geometrical progression that could be started from the matrix size $n=2$, for which the relevant permanents are easy to calculate from the definition (1) ($C_1=c_0,C_2=c_0^2+1$). It is valid even for $n=1$ if one assigns the unity value for the permanent of the zero-size matrix, $C_0=1$, so that $C_1-C_0=c_0-1$. The latter Equation (17) is exactly the known recurrence equation for the upper incomplete gamma function, which follows from integration by parts of Equation (14). This fact proves Equation (13) and completes the proof of the Proposition 1. □

Remark 1.

According to the Definition (1), the permanent of the matrix (11) is a polynomial of one variable $c_0$ of the order n. It can be represented as

$$C_n=\sum _{j=0}^n{P}_j{c}_0^j=n!\sum _{j=0}^n{(c_0-1)}^j/j!.$$

(18)

Here the second representation follows from Equation (13) and the known fact that a Taylor series of the function $e^x\Gamma (n+1,x)=n!{\sum }_{j=0}^n{x}^j/j!$ becomes finite at the integer values of $n=0,1,2,\dots$. Thus, the analytic formula in Equation (13) gives the exact solution for this permanent, and importantly, allows one to find its asymptotics in the limit of a large matrix size $n\to \infty$ via the known properties of the upper incomplete gamma function.

Remark 2.

Famous derangement numbers, or subfactorials [17], counting the number of permutations of the set $\{1,\dots ,n\}$ that have no fixed points,

$$D_{n,0}\equiv !n=\lfloor n!/e\rceil =n!\sum _{j=0}^n{(-1)}^j/j!={\int }_0^{\infty }{(t-1)}^n{e}^{-t}dt,$$

(19)

and more general rencontres numbers counting the number of permutations of the set $\{1,\dots ,n\}$ with exactly k fixed points ($0\le k\le n$),

$$D_{n,k}=\frac{n!}{k!(n-k)!}{D}_{n-k,0},$$

(20)

are closely related to the permanent of the matrix (11). Namely, the number of derangements is equal to the permanent of the matrix C with the zero diagonal, that is, just to the constant term $P_0$ of the permanental polynomial in Equation (18):

$$D_{n,0}=C_n{|}_{c_0=0}=P_0.$$

(21)

Remark 3.

The permanent $C_n^{\prime }$ of a somewhat more general circulant $n\times n$ matrix $C^{\prime }$ with one $c_0$-diagonal inside a uniform matrix with one and the same value c, not necessarily unity, assigned to all other entries,

$$C^{\prime }=\left[\begin{array}{ccccc}{c}_0& c& \cdots & c& c\\ c& c_0& \cdots & c& c\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ c& c& \cdots & c_0& c\\ c& c& \cdots & c& c_0\end{array}\right],$$

(22)

can be easily reduced to the one in Equation (13) by means of the rescaling:

$$C_n^{\prime }=c^n{e}^{\frac{c_0}{c}-1}\Gamma (n+1,\frac{c_0}{c}-1).$$

(23)

This formula and its analogs for the uniform circulant matrices with a band of $k>1$ diagonals are useful for analyzing an overall scaling of the permanents. Yet, thereinafter we will skip such a straightforward generalization and set $c=1$.

Remark 4.

Another derivation of Equation (23) is based on the combinatorics of the permanent in the Definition (1) and the rencontres numbers in Equation (20):

$$C_n^{\prime }=\sum _{j=0}^n{D}_{n,j}{c}_0^j{c}^{n-j}={\int }_0^{\infty }\frac{{(c_0-c+ct)}^n}{e^t}dt=c^n{e}^{\frac{c_0}{c}-1}\Gamma (n+1,\frac{c_0}{c}-1).$$

(24)

Remark 5.

In the case $k=0$ of the matrix which has all unity entries without a band of any-value diagonals, $C=J$, it is easy to find the permanent directly from the definition in Equation (1) by means of a trivial combinatorics: $perJ=n!$. Of course, the same result follows from the general analytic formula in Equation (13) in the corresponding particular case $c_0=1$.

5. The Permanent of a Uniform Circulant Matrix with a Band of Two Any-Value Diagonals ($\mathbf{k}=\mathbf{2}$) and the Ménage Numbers

Here we consider a more envolved, but still simple case of a uniform circulant $n\times n$ matrix with a band of two $(k=2)$ diagonals (with the entry values $c_0$ and $c_1$) inside the matrix J of all 1s:

$$C=\mathrm{Circ}(c_0,c_1,1,\dots ,1)=\left[\begin{array}{ccccccc}{c}_0& c_1& 1& \cdots & 1& 1& 1\\ 1& c_0& c_1& \cdots & 1& 1& 1\\ 1& 1& c_0& \cdots & 1& 1& 1\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 1& 1& 1& \cdots & c_0& c_1& 1\\ 1& 1& 1& \cdots & 1& c_0& c_1\\ c_1& 1& 1& \cdots & 1& 1& c_0\end{array}\right].$$

(25)

Proposition 2.

The permanent of this circulant with a band of two diagonals,

$$C_n\equiv perCirc(c_0,c_1,1,\dots ,1)=A_n+(c_1-1)[A_{n-1}+(c_1-c_0)A_{n-1}^{\left(1\right)}+A_{\left(n\right)}-A{(\ast )}_{\left(n\right)}],$$

(26)

is given by a solution of the following system of recurrence relations

$$\begin{array}{cc}\hfill & A_n=c_0{A}_{n-1}+(n-2+c_1)A_{n-1}^{\left(1\right)}+(1-c_1)A{(\ast )}_{(n-1)},\hfill \\ \hfill & A_n^{\left(1\right)}=A_{n-1}+(n-2+c_1)A_{n-1}^{\left(1\right)}+(1-c_1)A{(\ast )}_{(n-1)},\hfill \\ \hfill & A_{\left(n\right)}=(n-1)A_{n-1}^{\left(1\right)}+(1-c_1)A{(\ast )}_{(n-1)},\hfill \\ \hfill & A{(\ast )}_{\left(n\right)}=(n-1)A_{n-1}^{\left(1\right)}+(1-c_0)A_{(n-1)}\hfill \end{array}$$

(27)

with the initial conditions set at the starting recursive order $n=1$ as follows

$$A_1=c_0,A_1^{\left(1\right)}=1,A_{\left(1\right)}=A{(\ast )}_{\left(1\right)}=0.$$

(28)

Proof. 

The permanent $C_n$ is given by Lemma 1 applied to the matrix A, Equation (4), which differs from the circulant C by one defect in the lower left corner:

$$C_n=A_n+(c_1-1)A{(\ast )}_{n-1}.$$

(29)

Here the star $(\ast )$-conjugation means renaming $c_0\to c_1,c_1\to c_0$ as per Definition 8. The permanent $A_n$ is given by the Laplace expansion over the first row,

$$A_n=c_0{A}_{n-1}+(c_1-1)A_{n-1}^{\left(1\right)}+A_{\left(n\right)},$$

(30)

via the sum $A_{\left(n\right)}$, Equation (8), which we find via summation of the analogs of Equation (29) written for the circulant with a 1’s-column defect at the position $q=l$,

$$C_n^{\left(l\right)}=A_n^{\left(l\right)}+(c_1-1)(1-{\delta }_{l,1})A^{(n+1-l)}{(\ast )}_{n-1},l=1,2,\dots ,n.$$

(31)

Taking into account that the permanent of the circulant matrix with a 1’s-column defect does not depend on the position l of the 1’s-column defect, and hence, equals to $C_n^{\left(l\right)}=A_n^{\left(1\right)}\forall l$, we immediately get the third equation of the system (27). The forth equation is just its $(\ast )$-conjugated counterpart. Plugging the third equation into Equation (30), we get the first equation of the system (27). At last, the second equation of the system (27) follows from the first equation and the representation of the permanent of the matrix $A^{\left(1\right)}$ with a 1’s-column defect at the position of the first column obtained by means of Lemma 1:

$$A_n^{\left(1\right)}=A_n+(1-c_0)A_{n-1}.$$

(32)

Equation (26) for the circulant permanent $C_n$ itself follows from Equation (29) after plugging the equation for the $(\ast )$-conjugated permanent of the matrix A:

$$A{(\ast )}_{n-1}=A_{n-1}+(c_1-c_0)A_{n-1}^{\left(1\right)}+A_{\left(n\right)}-A{(\ast )}_{\left(n\right)}.$$

(33)

The latter equation is a consequence of the identity $A_n^{\left(1\right)}=A^{\left(1\right)}{(\ast )}_n$ with both sides substituted with an explicit expression

$$A_n^{\left(1\right)}=A_{n-1}+(c_1-1)A_{n-1}^{\left(1\right)}+A_{\left(n\right)}$$

(34)

which follows from Equations (32) and (30). The initial conditions (28) provide the correct values for all permanents at the recursive order $n=2$, namely,

$$A_2=c_0^2+c_1,A_2^{\left(1\right)}=c_0+c_1,A_{\left(2\right)}=A{(\ast )}_{\left(2\right)}=1,A{(\ast )}_2=c_1^2+c_0.$$

(35)

This completes the proof of the Proposition 2. □

Remark 6.

The permanent of the uniform circulant matrix C with a band of two diagonals ($k=2$), Equation (25), is given by the system of linear homogeneous recurrence relations with variable coefficients of the fourth order, Equation (27), whereas in the case of a band of one diagonal ($k=1$) the system of recurrence relations is of the second order, Equation (12). The system in Equation (27) allows one to compute the entire permanental polynomial,

$$perC=\sum _{j_0,j_1=0}^n{P}_{j_0,j_1}{c}_0^{j_0}{c}_1^{j_1},$$

(36)

as a function of two valiables ($c_0,c_1$) for any large matrix size n and to find its asymptotics analytically. The relevant results will be presented elsewhere.

Remark 7.

Famous ménage numbers [52,53,55,56,57,59,60,61] $U_n$ counting the number of different ways to seat n husbands at a circular table of $2n$ places so that men and women alternate and no adjacent couples are allowed, that is, the number of 2-discordant permutations σ of $\{1,\dots ,n\}$ such that $\sigma \left(j\right)$ is not congruent to any $j,j+1\left(modn\right)$, are equal to the permanent of the uniform circulant matrix C with a band of two zero diagonals. That is, they are equal to a particular value of the permanent when both variables are zero, $c_0=c_1=0$, which is the constant term of the permanental polynomial in Equation (36):

$$U_n=C_n{|}_{c_0=c_1=0}=P_{0,0}.$$

(37)

A well-known fourth-order recurrence equation for the ménage numbers [53,59]:

$$U_n=n{U}_{n-1}+2U_{n-2}-(n-4)U_{n-3}-U_{n-4},$$

(38)

immediately follows from the recurrence relations for the permanent $C_n$, Equation (27), as its particular case. Namely, for $c_0=c_1=0$ the permanent, and hence, the ménage numbers (the sequence A000179 in [56]) are given by a simple formula

$$U_n=C_n=A_n-A_{n-1}$$

(39)

via the permanent $A_n$ of the matrix with the defect A, Equation (4), which coincides with the straight ménage number $V_n$, counting the number of permutations $\sigma$ of $\{1,\dots ,n\}$ such that $\sigma \left(j\right)$ is not congruent to any $j,\min \{j+1,n\}\left(\mathrm{mod}n\right)$ (that corresponds to an analogous problem of seating n husbands at a straight-line table), and satisfies the third-order recurrence (the sequence A000271 in [56]):

$$A_n=(n-1)(A_{n-1}+A_{n-2})+A_{n-3}.$$

(40)

The latter immediately follows from Equation (27) since

$$A_n^{\left(1\right)}=A_n+A_{n-1}\&A_{\left(n\right)}=A{(\ast )}_{\left(n\right)}=A_n+A_{n-1}+A_{n-2}\mathrm{for}{c}_0=c_1=0.$$

(41)

Thus, the method of the recursion of permanents with defects provides a simple derivation of the recurrence (40) for the straight ménage numbers $V_n=A_n{|}_{c_0=c_1=0}$, which is different from a long combinatorial derivation (see Theorem 1 in [53]).

6. The Permanent of a Uniform Circulant Matrix with a Band of Three Any-Value Diagonals ($\mathbf{k}=\mathbf{3}$) and the 3-Ménage Numbers

Finally, we consider a quite complicated case of a uniform circulant $n\times n$ matrix with a band of three $(k=3)$ diagonals (with the entry values $c_0,c_1$, $c_2$) inside the matrix J of all 1s. It is depicted as C in Equation (3) and $\tilde{C}$ in Equation (5) below.

$$\tilde{C}=\mathrm{Circ}(c_1,c_2,1,\dots ,1,c_0)=\left[\begin{array}{ccccccc}{c}_1& c_2& 1& \cdots & 1& 1& c_0\\ c_0& c_1& c_2& \cdots & 1& 1& 1\\ 1& c_0& c_1& \cdots & 1& 1& 1\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 1& 1& 1& \cdots & c_1& c_2& 1\\ 1& 1& 1& \cdots & c_0& c_1& c_2\\ c_2& 1& 1& \cdots & 1& c_0& c_1\end{array}\right].$$

(42)

Theorem 1.

The permanent of this circulant with a band of three diagonals is

$$C_n\equiv perCirc(c_0,c_1,c_2,1,\dots ,1)=B_n+(c_0-1)A_{n-1}+(c_2-1)A{(\ast )}_{n-1}+(c_0-1)(c_2-1)B_{n-2}$$

(43)

and is determined by a solution of the following system of recurrence relations:

$$A_n=A_{\left(n\right)}-(1-c_2)A_{n-1}^{\left(2\right)}+(c_0+c_1-1)A_{n-1}-(1-c_0)(1-c_1)A_{n-2},$$

(44)

$$\begin{array}{cc}{B}_n=B_{\left(n\right)}\hfill & +c_1{B}_{n-1}-(1-c_0)A_{n-1}-(1-c_2)A{(\ast )}_{n-1}\hfill \\ \hfill & -{(1-c_0)}^2{A}_{n-2}-{(1-c_2)}^{2}A{(\ast )}_{n-2}+(1-c_0)(1-c_2)B_{n-2},\hfill \end{array}$$

(45)

$$\begin{array}{cc}{A}_{\left(n\right)}=\hfill & (n-3)C_{n-1}^{\left(1\right)}+A_{n-1}^{\left(2\right)}+A_{n-1}+2(1-c_2)A{(\ast )}_{(n-1)}+(1-c_1)B_{(n-1)}\hfill \\ \hfill & +(1-c_0)A_{n-2}+(c_1+c_2-2)A{(\ast )}_{n-2}-c_2(1-c_2)A{(\ast )}_{(n-2)}-2(1-c_0)(1-c_2)B_{(n-2)}\hfill \\ \hfill & -(2+c_0-c_1-c_2)(1-c_2)A{(\ast )}_{n-3}+(1-c_0){(1-c_2)}^{2}A{(\ast )}_{n-4},\hfill \end{array}$$

(46)

$$\begin{array}{cc}{B}_{\left(n\right)}=\hfill & (n-3)C_{n-1}^{\left(1\right)}+A_{n-1}+A{(\ast )}_{n-1}+(1-c_0)A_{(n-1)}+(1-c_2)A{(\ast )}_{(n-1)}\hfill \\ \hfill & -(1-c_0)(1-c_2)B_{(n-2)}-{(1-c_0)}^2{A}_{n-3}-{(1-c_2)}^{2}A{(\ast )}_{n-3},\hfill \end{array}$$

(47)

$$\begin{array}{cc}{C}_n^{\left(1\right)}=\hfill & (n-3)C_{n-1}^{\left(1\right)}+A_{n-1}+A{(\ast )}_{n-1}+B_{n-1}\hfill \\ \hfill & +(1-c_0)[A_{(n-1)}-A_{n-1}]+(1-c_2)[A{(\ast )}_{(n-1)}-A{(\ast )}_{n-1}]-(1-c_0)(1-c_2)B_{(n-2)}\hfill \\ \hfill & -{(1-c_0)}^2[A_{n-2}+A_{n-3}]-{(1-c_2)}^2[A{(\ast )}_{n-2}+A{(\ast )}_{n-3}].\hfill \end{array}$$

(48)

The symbols $A_{\left(n\right)}$, $B_{\left(n\right)}$ in Equations (44) and (45) stand for the right-hand sides of Equations (46) and (47), respectively. In Equations (44) and (46), the symbol $A_{n-1}^{\left(2\right)}$ stands for

$$\begin{array}{cc}{A}_{n-1}^{\left(2\right)}=\hfill & C_{n-1}^{\left(1\right)}+(1-c_1)A{(\ast )}_{n-2}+(1-c_2)A{(\ast )}_{(n-2)}\hfill \\ \hfill & +(1+c_0-c_1)(1-c_2)A{(\ast )}_{n-3}-(1-c_0){(1-c_2)}^{2}A{(\ast )}_{n-4}.\hfill \end{array}$$

(49)

Remark 8.

The recurrence system includes the star $(\ast )$-conjugated counterparts of Equations (44) and (46) for $A{(\ast )}_n$ and $A{(\ast )}_{\left(n\right)}$. Their explicit form is given in the Appendix A. Obviously, $B{(\ast )}_n\equiv B_n$, $B{(\ast )}_{\left(n\right)}\equiv B_{\left(n\right)}$ and $C{(\ast )}_n^{\left(1\right)}\equiv C_n^{\left(1\right)}$. Hence, the star $(\ast )$-conjugated counterparts of Equations (45), (47) and (48) are not needed. Note that in the present case of $k=3$ the star $(\ast )$-conjugation means just renaming $c_0\to c_2,c_2\to c_0$ and leaves $c_1$ untouched as per Definition 8.

Remark 9.

The system consists of the three blocks of different origin:

(i)

Block 1—the basis permanents (44) and (45) of the matrices with entry defects;

(ii)

Block 2—the sums of permanents (46) and (47) with a 1’s column defect;

(iii)

Block 3—the special permanent (48) of the matrix C with all 1s in the first column.

Proof of the Theorem 1. 

While applying Lemmas 1 and 2 below, we employ the auxiliary matrices $A^{\prime }$ and R defined in Equation (7). They differ from the basis matrices A and B by one and two defects, so that their permanents are given by Lemma 1 and Lemma 2, respectively, as follows:

$$A_n^{\prime }=A_n+(c_2-1)B_{n-1},$$

(50)

$$R_n=B_n-(1-c_0)(1-c_2)B_{n-2}.$$

(51)

Equation (43) follows from Lemma 2 applied to the B, which differs from the $\tilde{C}$ by two defects.

Equations (44) and (45) follow from the Laplace expansions over the first row:

$$A_n=c_0{A}_{n-1}+(c_1-1)A_{n-1}^{\left(1\right)}+(c_2-1)A_{n-1}^{\left(2\right)}+A_{\left(n\right)},$$

(52)

$$R_n=c_1{B}_{n-1}+(c_2-1)B_{n-1}^{\left(1\right)}+(c_0-1)B_{n-1}^{(n-1)}+B_{\left(n\right)}.$$

(53)

Equation (46) is based on Lemma 2 applied to the A viewed as the C with three defects:

$$A_n=C_n+(1-c_1)B_{n-1}+2(1-c_2)A^{\prime }{(\ast )}_{n-1}+{(1-c_2)}^{2}A{(\ast )}_{n-2}.$$

(54)

Namely, we use an analog of Equation (54) for a matrix $A^{\left(q\right)}$ with a 1’s-column defect:

$$\begin{array}{cc}{A}_n^{\left(q\right)}=\hfill & C_n^{\left(q\right)}+(1-c_1)B_{n-1}^{(q-1)}(1-{\delta }_{q,1})+{(1-c_2)}^2{A}^{(n+1-q)}{(\ast )}_{n-2}(1-{\delta }_{q,1})(1-{\delta }_{q,2})\hfill \\ & +(1-c_2)[A^{(n+1-q)}{(\ast )}_{n-1}(1-{\delta }_{q,1})+A^{(n(1-{\delta }_{q,1})+2-q)}{(\ast )}_{n-1}(1-{\delta }_{q,2})]\hfill \\ & -(1-c_0)(1-c_2)[B_{n-2}^{(q-1)}(1-{\delta }_{q,n})+B_{n-2}^{(q-2)}(1-{\delta }_{q,2})](1-{\delta }_{q,1}),q=1,\dots ,n.\hfill \end{array}$$

(55)

Equation (46) is the sum of Equations (55) over $q=1,2,\dots ,n$ with a renamed $n\to n-1$.

Equation (47) is based on Lemma 2 applied to the B viewed as the $\tilde{C}$ with two defects:

$$B_n={\tilde{C}}_n+(1-c_0)A_{n-1}+(1-c_2)A{(\ast )}_{n-1}-(1-c_0)(1-c_2)B_{n-2}.$$

(56)

Namely, we use an analog of Equation (56) for a matrix $B^{\left(q\right)}$ with a 1’s-column defect:

$$\begin{array}{cc}{B}_n^{\left(q\right)}=\hfill & {\tilde{C}}_n^{\left(q\right)}+(1-c_0)A_{n-1}^{\left(q\right)}(1-{\delta }_{q,n})+(1-c_2)A^{(n+1-q)}{(\ast )}_{n-1}(1-{\delta }_{q,1})\hfill \\ \hfill & -(1-c_0)(1-c_2)B_{n-2}^{(q-1)}(1-{\delta }_{q,1})(1-{\delta }_{q,n}),q=1,\dots ,n.\hfill \end{array}$$

(57)

Equation (47) is the sum of Equations (57) over $q=1,2,\dots ,n$ with a renamed $n\to n-1$.

Equation (48) follows from Lemma 2 applied to the $C^{\left(1\right)}$ viewed as the R with one defect:

$$C_n^{\left(1\right)}=R_n+(1-c_1)B_{n-1}=B_n+(1-c_1)B_{n-1}-(1-c_0)(1-c_2)B_{n-2}.$$

(58)

Equation (49) is Equation (55) in the case $q=2$. When deriving the equations above, we plugged in some special permanents with a 1’s column defect as follows:

$$A_n^{\left(1\right)}=B_n^{\left(n\right)}=B^{\left(1\right)}{(\ast )}_n=A_n+(1-c_0)A_{n-1},A_n^{\left(n\right)}=A_{n-1}+A_{\left(n\right)}.$$

(59)

This completes the proof of the Theorem. □

Remark 10.

By means of changing the unknown variables or reducing or increasing their number, it is possible to rewrite the system of recurrence relations in other, more or less symmetric forms. For instance, it is straightforward to solve Equation (47) for the variable $B_{\left(n\right)}$ in terms of the basis permanents and exclude it from the system by plugging it into the Equations (46)–(48) which, together with Equation (44) and the $(\ast )$-conjugated Equations (A1) and (A2), constitute the six recurrence equations, each of the fourth order, for the six unknown variables $A_n,A{(\ast )}_n,A_{\left(n\right)},A{(\ast )}_{\left(n\right)},B_n,C_n^{\left(1\right)}$. Overall, this system of linear homogeneous recurrence relations with variable coefficients is of the 24-th order. One can go further on, and similarly, exclude the variable $C_n^{\left(1\right)}$ by solving Equation (46) for $C_{n-1}^{\left(1\right)}$ and plugging it into the remaining equations. A related analysis will be done elsewhere. Note that the actual overall order of this recurrence could be less than 24 only for some special cases or if there is some hidden symmetry or identity within this system of recurrence relations. In particular, for the problem of the 3-ménage numbers (3-discordant permutations) corresponding to the case $c_0=c_1=c_2=0$, the system of recurrence relations can be reduced to just one recurrence Equation (67) of the 8-th order for $A_n$ (see Remark 12 below).

Remark 11.

The system of recurrence relations (44)–(48) is valid for $n\ge 7$ since the matrix size in the lowest-order permanent $A{(\ast )}_{n-4}$ entering Equations (44) and (46) should be equal or larger than the size of the diagonal band, $k=3$. The permanents of the order 6 and lower in the right-hand side of the recurrence equations (that is, $A_3,A{(\ast )}_3,B_4,B_5$, etc.) should be computed directly via the definition of the permanent in Equation (1). Direct numerical calculations, such as in Figure 1, confirm that the recurrence (44)–(48) gives easy and fast access to the correct result for the permanent of the circulant (3) with arbitrary, even complex values of the entries $c_0,c_1,c_2$ for any, arbitrarily large matrix size n in linear time. In fact, there are no other means to compute the permanents such as in Figure 1 for a matrix size $n\sim 100$ or larger. The point is that the known deterministic algorithms [19,36,37] are not capable of computing the permanent of a matrix with a size n larger than 50 even on a supercomputer [38]. (A standard PC with Wolfram Mathematica fails already at $n\sim 25$.) A fully polynomial randomized approximation scheme [21,22] does not work for matrices with sign indefinite or complex entries and requires a rather long polynomial computing time that scales as ∼$n^{11}$ for a general matrix with nonnegative entries or ∼$n^4(logn)$ in a special case of a very dense matrix. Figure 1 illustrates a strong dependence of the permanent on the entries $c_0,c_1,c_2$. It is not just strongly different from the permanent of the all-1s matrix, $perJ=n!$, but changes its asymptotic value by two orders of magnitude due to flipping a sign of a single entry $c_1$.

Remark 12.

The famous 3-ménage numbers [51,52,53,56,57,62,63] $U_n^3$ counting the number of the 3-discordant permutations σ of $\{1,\dots ,n\}$ such that $\sigma \left(j\right)$ is not congruent to any $j,j+1,j+2\left(modn\right)$, are equal to the permanent of the uniform circulant matrix C with a band of three zero diagonals. Hence, they are given by a particular value, $U_n^3=C_n{|}_{c_0=c_1=c_2=0}$, of the permanent

$$C_n=B_n-2A_{n-1}+B_{n-2}$$

(60)

by means of the solution of the system of recurrence relations

$$A_n=A_{\left(n\right)}-C_{n-1}^{\left(1\right)}-A_{n-1}-A_{(n-2)}-2A_{n-2}-A_{n-3}+A_{n-4},$$

(61)

$$B_n=B_{\left(n\right)}-2A_{n-1}-2A_{n-2}+B_{n-2},$$

(62)

$$A_{\left(n\right)}=(n-2)C_{n-1}^{\left(1\right)}+A_{n-1}+2A_{(n-1)}+B_{(n-1)}+A_{(n-2)}-2B_{(n-2)}-A_{n-3},$$

(63)

$$B_{\left(n\right)}=(n-3)C_{n-1}^{\left(1\right)}+2A_{n-1}+2A_{(n-1)}-B_{(n-2)}-2A_{n-3},$$

(64)

$$C_n^{\left(1\right)}=(n-3)C_{n-1}^{\left(1\right)}+B_{n-1}+2A_{(n-1)}-B_{(n-2)}-2A_{n-2}-2A_{n-3}$$

(65)

which are Equations (44)–(48) in the particular case $c_0=c_1=c_2=0$ when the star $(\ast )$-conjugated counterparts are not needed since $A_n=A{(\ast )}_n$, $A_{\left(n\right)}=A{(\ast )}_{\left(n\right)}$.

We checked that the correct values (see the integer sequences A000183 and A001887 in [56]) and the known recurrence relations for the 3-ménage numbers, or 3-discordant permutations [53,56,57,62,63]:

$$\begin{array}{cc}{U}_n^3=\hfill & {(-1)}^n(4n+f_n)+{\displaystyle \frac{n}{n-1}}[(n+1)U_{n-1}^3+2{(-1)}^n{f}_{n-1}]-{\displaystyle \frac{2n}{n-2}}[(n-3)U_{n-2}^3\hfill \\ & +{(-1)}^n{f}_{n-2}]+{\displaystyle \frac{n}{n-3}}[(n-5)U_{n-3}^3-2{(-1)}^n{f}_{n-3}]+{\displaystyle \frac{n}{n-4}}[U_{n-4}^3-{(-1)}^n{f}_{n-4}],\hfill \end{array}$$

(66)

(which is also valid for $n\ge 7$, see Example 4.7.17 in [17]) and for the straight 3-ménage numbers [53,55] $V_n^3=A_n$ (which is valid for $n\ge 11$)

$$\begin{array}{cc}{A}_n=\hfill & (n-1)A_{n-1}+(n+2)A_{n-2}-(3n-13)A_{n-3}-(2n-8)A_{n-4}\hfill \\ \hfill & +(3n-15)A_{n-5}+(n-4)A_{n-6}-(n-7)A_{n-7}-A_{n-8}\hfill \end{array}$$

(67)

follow from Equations (60)–(65) derived above. (Equation (66) includes the n-th Fibonacci number $F_n=F_{n-1}+F_{n-2},F_0=0,F_1=1$, via a function $f_n=F_{n+1}+F_{n-1}+2$.) In particular, in order to derive Equation (67), one can, first, exclude the $B_{\left(n\right)}$ by solving for it Equation (62) and plugging it into the remaining equations; then excluding the $C_n^{\left(1\right)}$ by solving for it Equation (63) and plugging it into the remaining equations; then, in a similar way, excluding the $A_{\left(n\right)}$; and finally, excluding the $B_n$.

7. Conclusions

We present the exact solution for the circulant permanent via the finite system of the linear recurrence relations which provides a full access to a highly nontrivial analytic dependence of the permanent (whose entries are all nonzero) on $k=1,2$ or 3 independent parameters. This is especially interesting since computing the permanent in the case of 0-1 matrices with just three arbitrarily placed nonzero entries per row and column is as hard as in the general case [64]. Exactly solvable models, like the ones discussed above, could play as important role in the understanding and theory of the matrix permanent and similar $♯P$-hard problems as the famous Onsager’s and other exactly solvable models play in the theory of critical phenomena in phase transitions [9]. In other words, an attitude to the matrix permanent should be shifted from considering it just as a symbol of incomputability to employing it as a powerful tool for understanding and studying the $♯P$- and NP-hard problems and processes.

The circulant permanent studied above is a multivariate polynomial of k indeterminates $(c_0,\dots ,c_{k-1})$ and has (say, in the case $k=3$) the following form

$$\mathrm{per}C=\sum _{j_0,j_1,j_2=0}^n{P}_{j_0,j_1,j_2}{c}_0^{j_0}{c}_1^{j_1}{c}_2^{j_2},$$

(68)

where summation over the indexes is subject to the constraint ${\sum }_{i=0}^{k-1}{j}_i\le n$. The degree of such a permanental polynomial is equal to the matrix size n. The permanental polynomials constitute a key concept of the universal polynomials in the algebraic complexity theory [28] and their understanding is paramount.

The constant term of the permanental polynomial, $P_{j_0=0,\dots ,j_{k-1}=0}$, considered as a function of the matrix size n forms a famous integer sequence of the k-ménage numbers, or k-discordant permutations [51,52,53,56,57,58]. The recurrence relations for the k-ménage numbers are known in an explicit form only for the cases $k=1$ (derangements, or 1-ménage numbers), $k=2$ (classical 2-ménage numbers), and $k=3$ (3-ménage numbers). The recurrence relations (44)–(48) for the circulant permanent in the case $k=3$ provide a compact and explicit recurrence for the 3-ménage numbers, Equations (60)–(65) or (67), if one simply sets all three circulant parameters to be zero, $c_0=c_1=c_2=0$. Finding the recurrence for the k-ménage numbers in the case $k\ge 4$ remains an open problem.

The finite recursion for the circulant permanents (presented above for the particular cases $k=1,2,3$) is the solution to a much more complex problem. It provides a powerful analytic and numerical tool for a detailed analysis of the entire permanental multivariate polynomial, not just its constant term that is the sequence of the k-ménage numbers. The details of such an analysis will be given elsewhere. It would be interesting to generalize this approach to the case $k\ge 4$ which is challenging. As the next step, we plan to work out the aforementioned recursion in the case of the uniform circulant permanent with a band of $k=4$ any-value diagonals.

For calculating the permanents, the method of recurrence relations for the permanents of matrices with defects, presented here, is superior to the rook and hit polynomial approach which dominated an extensive literature on the ménage numbers (discordant permutations) in recent years [17,51,52,53,54,57]. The point is that the rook and hit polynomials are somewhat artificial univariate polynomials associated with the permanents of just 0-1 matrices while the actual permanental polynomials, as in Equation (68), are multivariate ones and contain much more involved combinatorial and analytic information on permanents. Compared to the rook and hit polynomial approach, the permanent-based method is more algebraic rather than combinatorial in nature.

The most important further step would be finding the asymptotics of the permanent for some classes of the circulant constraint matrices of large size $n\gg 1$. The recurrence relations like the ones presented above allow one to apply well-developed asymptotic methods (see, for instance, [55,65,66,67,68] and references therein). A solution to this fundamental open problem on the permanent’s asymptotics would be incredibly important for a unified analysis of a wide range of the nature’s #P-hard problems, including problems in the physics of many-body systems, critical phenomena, quantum computing, quantum field theory, theory of chaos, fractals, number theory, cryptography, dynamical systems, generalized harmonic and wavelet analysis, etc.

Finally, it is worth noting that the outlined above possibility to compute the permanent of the uniform circulant matrices with a band of k diagonals in polynomial time does not contradict to the belief of an impossibility to compute the permanents in the general case of arbitrary matrices which is a #P-hard problem according to the well-known Valiant’s theorem [20] in the computational complexity theory. Although the permanents calculated above via the recurrence relations are very complex multivariant functions of the parameters $c_0,\dots ,c_{k-1}$, the polynomial-time computability of such exactly solvable models is consistent with the principle of supremacy of quantum computing [6,7,69]. In fact, our ability to understand, describe and compute various complex processes of nature is increasing every time we bite off new computable or exactly solvable special cases from a general-case land of NP- and #P-hard problems.