betaFeedback

WorksMathematics

Closed formulas for the permanents of structured matrices

Abstract

We give finite formulas for permanents of structured matrices and prove polynomial bounds for their evaluation. Over any field, the permanent of a matrix of bounded rank-width can be computed from the matrix alone, answering a question of Lyaudet. In characteristic p>0p>0, the bound is pO(k)nO(1)p^{O(k)}n^{O(1)}, where kk is the rank-width. In characteristic zero, a determinant formula treats Cauchy matrices with an added polynomial of fixed degrees in the row and column nodes. This includes polynomial perturbations of Hilbert matrices and dense Toeplitz and Hankel families. For ordered cuts we give a single determinant; in positive characteristic, rational diagonal sequences give a fixed rational generating function for the Toeplitz permanents. We also give formulas for cycle weights and hook immanants. For translation matrices we obtain signed determinant formulas and classify the supports for which the permanent is the coefficientwise absolute value of the determinant. Further formulas cover cyclic block matrices, residue supports, and bands bounded on one side.

Introduction

Let F\mathbb{F} be a field. We assume characteristic zero except where otherwise stated. For an n×nn \times n matrix A=(aij)A = (a_{ij}) over F\mathbb{F}, the permanent of AA is

per⁡A=∑σ∈Sn∏i=1nai,σ(i),\operatorname{per} A = \sum_{\sigma\in S_n} \prod_{i=1}^{n} a_{i,\sigma(i)},

where SnS_n is the symmetric group on {1,…,n}\{1,\ldots,n\}. The permanent of the empty matrix is one.

Barvinok [1] proved that the permanent of a matrix of fixed rank can be computed in polynomial time. Flarup and Lyaudet [2] treated matrices of bounded weighted clique-width.

A cut I∣IcI \mid I^c is one partition of the indices applied to both rows and columns. Its width is the sum of the ranks of A[I,Ic]A[I,I^c] and A[Ic,I]A[I^c,I]. The rank-width is the smallest possible maximum cut width over binary trees on the indices. In [3 § 4], Lyaudet asked whether the permanent of a matrix of bounded rank-width be computed in polynomial time?

Theorem 3.1 gives an affirmative answer over any field. For each fixed bound on the rank-width, it computes the permanent from the entries of the matrix alone. The proof finds a tree of bounded width from the cut ranks and evaluates a finite sum by combining coefficient vectors at the nodes. For rational entries the algorithm has polynomial bit complexity. In characteristic p>0p > 0, Theorem 3.2 gives the bound pO(k)nO(1)p^{O(k)}n^{O(1)}, including the construction of a suitable tree. Thus, for fixed pp, rank-width O(log⁡(n+1))O(\log(n + 1)) is also allowed.

Cancellation in prime characteristic has been studied in terms of the rank of the whole matrix. Yu [4] proved the bound that per⁡A=0\operatorname{per} A = 0 if n>(p−1)rank⁡An > (p - 1)\operatorname{rank} A. Glynn [5] gave another proof and a factorization at the boundary rank. Arvind, Chatterjee, Datta and Mukhopadhyay [6 Corollary 4.7] gave a parameterized algorithm over finite fields for matrices of bounded rank. Here the rank bounds concern submatrices across a tree, and the field may be infinite. The proof reduces the endpoint polynomials modulo the ppth powers of their variables. For rational Toeplitz diagonal sequences this gives a fixed rational generating function for the permanents.

The ranks of the off-diagonal submatrices at successive cuts are used in the theory of quasiseparable matrices [7, 8]. Bounding these two ranks allows the total rank to grow with the order of the matrix. For example, the matrix (2−∣i−j∣)i,j=1n(2^{-|i-j|})_{i,j=1}^{n} has full rank, and both ranks at each nontrivial cut in the natural ordering are one.

Borchardt’s identity [9] expresses the permanent of a Cauchy matrix as a quotient of two determinants. Han and Krattenthaler [10] treated rectangular Cauchy permanents, and Khare and Sahi [11] obtained permanent and immanant identities for entrywise power series. These formulas do not directly give the evaluation bound considered here for

Aij=1xi−yj+P(xi,yj),A_{ij} = \frac{1}{x_i-y_j}+P(x_i,y_j),

where the two degrees of PP are fixed and its coefficients and the nodes may vary with nn. Theorem 3.3 gives a finite formula with polynomially many determinants, each of order at most 2n2n. Its proof expands a bordered Cauchy permanent according to the blocks and then uses polynomial interpolation. The resulting families need not have bounded rank-width.

For circulants with fixed jumps, Minc [12, 13] gave recurrences for the permanent. Golin, Leung and Wang [14] gave a transfer matrix proof and treated jumps that vary linearly with the order. Codenotti and Resta [15] expressed the permanent of a three-shift circulant as a linear combination of four determinants and treated a class with four shifts. For further formulas for sparse Toeplitz and banded matrices, see [16, 17, 18]. Alekseyev and Khomovsky [19, 20] give fixed-band recurrences and their symmetry reductions. The coefficient signs for three-shift circulants were studied in [21, 22]. Rodtes and Anwar [23] gave a formula for the permanent of a block matrix in terms of submatrices of its blocks. For a circulant with four arbitrary shifts and one weight per shift, the question of a closed formula that can be evaluated in polynomial time uniformly in the shifts remains open.

Our main results are the following. Theorems 3.1 and 3.2 give the tree formula and its refinement in positive characteristic. Theorem 3.3 treats polynomial perturbations of Cauchy matrices in characteristic zero. These are the two general constructions used for the permanent. For cuts along an ordering, Theorem 3.4 and Corollary 3.5 give a single determinant. The subsequent results treat prescribed cycle weights and hook immanants. Theorems 4.4, 4.7, 4.9 and 4.11 collect the formulas for the corresponding matrix classes. Their corollaries give the specializations. In each polynomial-time assertion, the parameters that must be fixed are stated explicitly.

Preliminaries

Write [n]={1,…,n}[n]=\{1,\ldots,n\} and N={0,1,2,…}\mathbb{N}=\{0,1,2,\ldots\}. For sets of row and column indices I,JI,J, A[I,J]A[I,J] is the submatrix in the given order. We use IcI^{c} for the complement in the relevant index set, and [w]f[w]f for the coefficient of the monomial ww in ff. The determinant of the empty matrix is one. Permuting rows or columns preserves the permanent.

For I⊆[n]I\subseteq[n], use the partition I∣IcI\mid I^{c} for the row labels and for the column labels. The two crossing blocks are A[I,Ic]A[I,I^{c}] and A[Ic,I]A[I^{c},I]. In an ordering, we use Ii={1,…,i}I_i=\{1,\ldots,i\}. In a rooted binary tree on the indices, each leaf is an index and each node II is the set of leaves below it. Write

wA(I)=rank⁡A[I,Ic]+rank⁡A[Ic,I],rw⁡F(A)=min⁡Tmax⁡I∈TwA(I).(1)w_A(I)=\operatorname{rank} A[I,I^{c}]+\operatorname{rank} A[I^{c},I],\qquad \operatorname{rw}_{\mathbb{F}}(A)=\min_{T}\max_{I\in T}w_A(I). \tag*{(1)}

The minimum is over all such trees on [n][n]. The ranks are taken over the field F\mathbb{F} of the entries of AA. In the terminology of Kanté and Rao [24 Definitions 4.1 and 4.3], wA(I)w_A(I) is the bi-cut-rank and rw⁡F(A)\operatorname{rw}_{\mathbb{F}}(A) is the F\mathbb{F}-bi-rank-width of the directed graph with an arc i→ji\to j of weight aija_{ij} whenever i≠ji\ne j and aij≠0a_{ij}\ne0. For a symmetric matrix the crossing blocks are transposes, so this rank-width is twice the width defined using one cut block. In formulas involving cut coordinates, r,sr,s denote upper bounds on the two ranks. A cut block of rank zero has empty coordinates. In the Cauchy formulas, the locally specified r,sr,s instead bound the two polynomial degrees.

For each node choose rank factorizations

A[I,Ic]=RIFI,A[Ic,I]T=CIGI.(2)A[I,I^c] = R_I F_I,\qquad A[I^c,I]^{\mathsf{T}} = C_I G_I. \tag*{(2)}

Here RI,CIR_I,C_I have full column rank and rows indexed by II. The matrices FI,GIF_I,G_I have full row rank and columns indexed by IcI^c. Put rI=rank⁡RIr_I = \operatorname{rank} R_I and sI=rank⁡CIs_I = \operatorname{rank} C_I. Let xIx_I and yIy_I be columns of rIr_I and sIs_I indeterminates, respectively. The row and column coordinates at i,j∈Ii,j \in I are the linear forms

RI(i,:)xI,CI(j,:)yI.R_I(i,:)x_I,\qquad C_I(j,:)y_I.

The variables at the root are empty. Suppose U,VU,V are the two children of II. Choose matrices BUVB_{UV} and BVUB_{VU} satisfying

A[U,V]=RUBUVCVT,A[V,U]=RVBVUCUT.(3)A[U,V] = R_U B_{UV} C_V^{\mathsf{T}},\qquad A[V,U] = R_V B_{VU} C_U^{\mathsf{T}}. \tag*{(3)}

They exist because the columns and rows of each cross block lie in the respective spaces of the two factors. They are obtained using left inverses of the two coordinate matrices. For J=U,VJ=U,V define SJ,I,TJ,IS_{J,I},T_{J,I} by

FJ[:,Ic]=SJ,IFI,GJ[:,Ic]=TJ,IGI.F_J[:,I^c] = S_{J,I}F_I,\qquad G_J[:,I^c] = T_{J,I}G_I.

The rows of each child factor span the corresponding cut row space. Restriction to the parent complement puts them in the row spaces of FI,GIF_I,G_I. Write ρI\rho_I for the substitution xJ↦SJ,IxIx_J \mapsto S_{J,I}x_I, yJ↦TJ,IyIy_J \mapsto T_{J,I}y_I, for both children.

The coordinate changes satisfy RJSJ,I=RI[J,:]R_JS_{J,I} = R_I[J,:] and CJTJ,I=CI[J,:]C_JT_{J,I} = C_I[J,:]. Indeed, factor the corresponding submatrix with columns in IcI^c in the two ways and use the full row rank of FIF_I or GIG_I.

2.1.

For this subsection let char⁡F=p>0\operatorname{char}\mathbb{F}=p>0. For nonnegative integers r,sr,s, put

Bp,r,s={xαyβ:0≤αi,βj<p, ∣α∣=∣β∣},Dp,r,s=∣Bp,r,s∣.(4)\mathcal{B}_{p,r,s}=\{x^\alpha y^\beta:0\leq\alpha_i,\beta_j<p,\ |\alpha|=|\beta|\},\qquad D_{p,r,s}=|\mathcal{B}_{p,r,s}|. \tag*{(4)}

Empty lists of variables are allowed. Replacing βj\beta_j by p−1−βjp-1-\beta_j in the equality of the two degrees gives

Dp,r,s=[ts(p−1)](1+t+⋯+tp−1)r+s≤pr+s.(5)D_{p,r,s}=[t^{s(p-1)}](1+t+\cdots+t^{p-1})^{r+s}\leq p^{r+s}. \tag*{(5)}

At a tree node II, calculations will take place in

RI=F[xI,yI]/(xI,1p,…,xI,rIp,yI,1p,…,yI,sIp).(6)R_I=\mathbb{F}[x_I,y_I]/(x_{I,1}^p,\ldots,x_{I,r_I}^p,y_{I,1}^p,\ldots,y_{I,s_I}^p). \tag*{(6)}

Each class has a unique representative with every exponent less than pp. The monomials in Bp,rI,sI\mathcal{B}_{p,r_I,s_I} are its balanced monomials. For a scalar bb and two variables define

Eb;x,y=∑m=0p−1bmm!∂xm∂ym.(7)E_{b;x,y}=\sum_{m=0}^{p-1}\frac{b^m}{m!}\partial_x^m\partial_y^m. \tag*{(7)}

All denominators in this formula are nonzero in F\mathbb{F}. Lemma 5.1 proves that these operations and the coordinate substitutions are well defined in the quotients.

2.2.

References

  1. [1]A. I. Barvinok, Two algorithmic results for the traveling salesman problem, Math. Oper. Res. 21 (1996), 65–84.DOI
  2. [2]U. Flarup and L. Lyaudet, On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth, Theory Comput. Syst. 46 (2010), 761–791.arxiv.org/abs/0801.3408
  3. [3]L. Lyaudet, First difference principle applied to modular/questionable-width, clique-width, and rank-width of binary structures, preprint, 2020.
  4. [4]Y. Yu, The permanent rank of a matrix, J. Combin. Theory Ser. A 85 (1999), 237–242.DOI
  5. [5]D. G. Glynn, The factorization of the permanent of a matrix with minimal rank in prime characteristic, Des. Codes Cryptogr. 62 (2012), 175–177. doi:10.1007/s10623-011-9501-5DOI
  6. [6]V. Arvind, A. Chattopadhyay, R. Datta and P. Mukhopadhyay, Universal ideal membership parameterized by rank, degree, and number of generators, Theory Comput. Syst. 66 (2022), 56–88. doi:10.1007/s00224-021-10053-w.DOI
  7. [7]C. Pernet and A. Storjohann, Time and space efficient generators for quasiseparable matrices, J. Symbolic Comput. 85 (2018), 224–246.arxiv.org/abs/1701.00396
  8. [8]C. Pernet, H. Signargout and G. Villard, Exact computations with quasiseparable matrices, Proc. 2023 Internat. Symp. Symbolic and Algebraic Computation, ACM, New York, 2023, 480–489.arxiv.org/abs/2302.04515
  9. [9]C. W. Borchardt, Bestimmung der symmetrischen Verbindungen vermittelst ihrer erzeugenden Funktion, J. reine angew. Math. 53 (1855), 193–198.
  10. [10]G.-N. Han and C. Krattenthaler, Rectangular Scott-type permanents, Sém. Lothar. Combin. 43 (2000), Art. B43g, 25 pp.DOI
  11. [11]A. Khare and S. Sahi, From Cauchy’s determinant formula to bosonic and fermionic immanant identities, European J. Combin. 110 (2023), 103683. doi:10.1016/j.ejc.2022.103683.DOI
  12. [12]H. Minc, Recurrence formulas for permanents of (0, 1)-circulants, Linear Algebra Appl. 71 (1985), 241–265.DOI
  13. [13]H. Minc, Permanent compounds and permanents of (0, 1)-circulants, Linear Algebra Appl. 86 (1987), 11–42.DOI
  14. [14]M. J. Golin, Y. C. Leung and Y. Wang, Permanents of circulants: a transfer matrix approach, expanded version, arXiv:0708.0907 (2007).arxiv.org/abs/0708.0907
  15. [15]B. Codenotti and G. Resta, Computation of sparse circulant permanents via determinants, Linear Algebra Appl. 355 (2002), 15–34.DOI
  16. [16]B. Codenotti, V. Crespi and G. Resta, On the permanent of certain (0, 1) Toeplitz matrices, Linear Algebra Appl. 267 (1997), 65–100.DOI
  17. [17]G. Resta and G. Sburlati, Computing permanents via determinants for some classes of sparse matrices, Linear Algebra Appl. 418 (2006), 33–43.DOI
  18. [18]M. Schwartz, Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices, Linear Algebra Appl. 430 (2009), 1364–1374.DOI
  19. [19]M. A. Alekseyev and D. I. Khomovsky, Constructive recurrences for determinants and permanents of banded Toeplitz matrices, arXiv:2609.13674 (2026).arxiv.org/abs/2609.13674
  20. [20]M. A. Alekseyev and D. I. Khomovsky, Symmetry reductions and recurrence degrees for banded Toeplitz determinants and permanents, arXiv:2609.23224 (2026).arxiv.org/abs/2609.23224
  21. [21]N. A. Loehr, G. S. Warrington and H. S. Wilf, The combinatorics of a three-line circulant determinant, Israel J. Math. 143 (2004), 141–156.DOI
  22. [22]P. De Poi, E. Mezzetti, M. Michalek, R. M. Miró-Roig and E. Nevo, Circulant matrices and Galois–Toeplitz systems, J. Pure Appl. Algebra 224 (2020), 106404.arxiv.org/abs/1808.08387
  23. [23]K. Rodtes and M. Fazeel Anwar, Permanents of block matrices, Linear Algebra Appl. 698 (2024), 94–101. doi:10.1016/j.laa.2024.05.024.DOI
  24. [24]M. M. Kanté and M. Rao, The rank-width of edge-coloured graphs, Theory Comput. Syst. 52 (2013), 599–644. doi:10.1007/s00224-012-9399-y.DOI
  25. [25]D. Vere-Jones, Alpha-permanents and their applications to multivariate gamma, negative binomial and ordinary binomial distributions, New Zealand J. Math. 26 (1997), 125–149.
  26. [26]G. S. Staples, Graph-induced operators: Hamiltonian cycle enumeration via fermion-zeon convolution, arXiv:1408.1036 (2014).DOI
  27. [27]H. L. Bodlaender, M. Cygan, S. Kratsch and J. Nederlof, Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time, arXiv:1211.505 (2012).arxiv.org/abs/1211.1505
  28. [28]R. Curticapean, N. Lindzey and J. Nederlof, A tight lower bound for counting Hamiltonian cycles via matrix rank, Proc. 29th ACM-SIAM Symp. Discrete Algorithms, SIAM, 2018, 1080–1099. doi:10.1137/1.9781611975031.70.
  29. [29]B. Deb, Continued fractions using a Laugere digraph interpretation of the Fauta–Zeilberger bijection and its variants, Combinatorial Theory 5 (2025), no. 1, Art. 9, 73 pp. doi:10.5070/C65165020.DOI
  30. [30]T. Korhonen and S. Oum, Branch-width of connectivity functions is fixed-parameter tractable, arXiv:2601.04756v2 (2026).arxiv.org/abs/2601.04756
  31. [31]S. Oum and P. Seymour, Approximating clique-width and branch-width, J. Combin. Theory Ser. B 96 (2006), 514–528. doi:10.1016/j.jctb.2005.10.006.DOI
  32. [32]A. Berele and A. Regev, Hook Young diagrams with applications to combinatorics and to representations of Lie superalgebras, Adv. Math. 64 (1987), 118–175.DOI
  33. [33]G. Strang and T. Nguyen, The interplay of ranks of submatrices, SIAM Rev. 46 (2004), 637–646.DOI
  34. [34]R. A. Usmani, Inversion of a tridiagonal Jacobi matrix, Linear Algebra Appl. 212/213 (1994), 413–414.DOI
  35. [35]R. Kenyon, Lectures on dimers, arXiv:0910.3129 (2009).arxiv.org/abs/0910.3129
  36. [36]R. P. Stanley, Enumerative Combinatorics, vol. 1, second ed., Cambridge University Press, Cambridge, 2012.
  37. [37]N. Robertson, P. Seymour and R. Thomas, Permanents, Pfaffian orientations, and even directed circuits, Ann. of Math. 150 (1999), 929–975.
  38. [38]S. Norine, Drawing 4-Pfaffian graphs on the torus, Combinatorica 29 (2009), 109–119.DOI
  39. [39]P. Pant and R. Singh, Exponential lower bounds for the Pfaffian number of graphs, arXiv:2605.21077v3 (2026).arxiv.org/abs/2605.21077
  40. [40]J. H. B. Kemperman, On small subsets in an abelian group, Acta Math. 103 (1960), 63–88.DOI
  41. [41]V. F. Lev, Critical pairs in abelian groups and Kemperman’s structure theorem, Int. J. Number Theory 2 (2006), 379–396.DOI

Paper details

vlnc:W_th34qt2g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents