pith. sign in

arxiv: 2101.09722 · v1 · submitted 2021-01-24 · 🧮 math.CO

Hafnian of two-parameter matrices

Dmitry Efimov This is my paper

Pith reviewed 2026-05-24 14:08 UTC · model grok-4.3

classification 🧮 math.CO
keywords hafniantwo-parameter matrixperfect matchingToeplitz matrixlinear chord diagramk-edge matchinginteger sequence
0
0 comments X

The pith

The hafnian of two-parameter matrices reduces exactly to a product of submatrix hafnians via a sum formula.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper gives a method to compute the hafnian exactly when matrix entries take only two values. It rests on a general identity that writes the hafnian of a sum of two matrices as a product of hafnians of certain submatrices. Applied to the adjacency matrices of graphs whose edges carry one of two possible weights, the identity converts the perfect-matching sum into a sum over the numbers of k-edge matchings of each type. The method is worked out in detail for Toeplitz two-parameter matrices and produces closed formulas for the total weight of perfect matchings in the corresponding graphs.

Core claim

We present an efficient method for the exact calculation of the hafnian of two-parameter matrices based on the formula expressing the hafnian of a sum of two matrices through the product of the hafnians of their submatrices. The necessary condition for the application of this method is the possibility to count the number of k-edge matchings in some graphs. We consider two special cases in detail using a Toeplitz matrix as the two-parameter matrix and obtain new analytical formulas to count the number of certain linear chord diagrams.

What carries the argument

The identity that expresses the hafnian of a sum of two matrices as a product of hafnians of submatrices, which converts a two-weight matching problem into enumeration of k-edge matchings.

If this is right

  • Exact hafnian values become available for any graph family in which the number of k-edge matchings admits a closed form.
  • Certain integer sequences receive new combinatorial interpretations as weighted perfect-matchings sums.
  • New closed-form expressions appear for the number of linear chord diagrams with restricted crossing patterns.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction may apply to other sparse-entry matrices whose support graphs allow matching enumeration.
  • If the two-parameter case extends to three or four distinct weights, the method could supply exact results for a wider class of weighted matching problems.

Load-bearing premise

It must be possible to count the number of k-edge matchings in the graphs that arise from the submatrices.

What would settle it

Compute the hafnian of a concrete 4-by-4 or 6-by-6 two-parameter Toeplitz matrix by direct expansion and compare it with the value obtained by enumerating the relevant k-edge matchings; any mismatch disproves the reduction formula.

Figures

Figures reproduced from arXiv: 2101.09722 by Dmitry Efimov.

Figure 1
Figure 1. Figure 1: A binary tree and its corresponding arc diagram [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The arc diagram Γ(Cn) Proposition 3. Let k and n be a pair of nonnegative integers. Suppose n 6= 2k when k is odd. Then, the inequality  3k − n 2  ≤  k 2  (6) 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Possible cases of matchings in the arc diagram Γ( [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The arc diagram Γ(C6(0, 1)) and all its perfect matchings 8 [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The arc diagram Γ(Dn) Theorem 2. Let k and n be nonnegative integers such that k ≤  n 2  . Then, the number of k-edge matchings in the arc diagram Γ(Dn) is equal to the following: µk(Γ(Dn)) = min(k,⌊ n−k X2 ⌋) i=0 min( X i,k−i) p=max(0,i+2k−n)  n − k − i k − p k − p i i p  . (13) Proof. For convenience, we use the abbreviated notation wn,k for µk(Γ(Dn)). Consider a k-edge matching in Γ(Dn). If n ≥ … view at source ↗
Figure 6
Figure 6. Figure 6: Possible cases of matchings in the arc diagram Γ( [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The triangular lattice Γ(Dn): (a) n is even; (b) n is odd Remark 4. Several initial values µk(Γ(Dn)) are presented in [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The arc diagram Γ(D6(0, 1)) and its only perfect matching References [1] Bj¨orklund A., Gupt B., Quesada N. A faster hafnian formula for complex matrices and its benchmarking on a supercomputer // ACM Journal of Experimental Algorithmics. 2019. V. 24. 1.11. [2] Grimson R.C. Enumeration of Dimer (Domino) Configurations // Discrete Mathematics. 1977. V. 18. pp. 167–178. [3] Krasko E., Omelchenko A. Enumerati… view at source ↗
read the original abstract

The concept of the hafnian first appeared in the works on quantum field theory by E. R. Caianiello. However, it also has an important combinatorial property: the hafnian of the adjacency matrix of an undirected weighted graph is equal to the total sum of the weights of perfect matchings in this graph. In general, the use of the hafnian is limited by the complexity of its computation. In this paper, we present an efficient method for the exact calculation of the hafnian of two-parameter matrices. In terms of graphs, we count the total sum of the weights of perfect matchings in graphs whose edge weights take only two values. This method is based on the formula expressing the hafnian of a sum of two matrices through the product of the hafnians of their submatrices. The necessary condition for the application of this method is the possibility to count the number of k-edge matchings in some graphs. We consider two special cases in detail using a Toeplitz matrix as the two-parameter matrix. As an example, we propose a new interpretation of some of the sequences from the On-Line Encyclopedia of Integer Sequences and then provide new analytical formulas to count the number of certain linear chord diagrams.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims an efficient exact method for computing the hafnian of two-parameter matrices (equivalently, the weighted perfect matchings in graphs with only two distinct edge weights) by invoking the expansion of hafnian(A+B) as a sum over products of hafnians of submatrices; the resulting expression is then evaluated by enumerating k-edge matchings in auxiliary graphs. Two special cases are worked out in detail for Toeplitz two-parameter matrices, yielding new closed-form interpretations of certain OEIS sequences and new formulas for the number of linear chord diagrams.

Significance. If the auxiliary matching counts are both independent of the target hafnian and admit closed forms or polynomial-time algorithms for the graphs that arise, the reduction would supply a genuinely efficient exact algorithm for a nontrivial subclass of hafnian instances that are #P-hard in general. The combinatorial reinterpretations of OEIS entries and chord-diagram counts would also be of independent interest to enumerative combinatorics.

major comments (2)
  1. [Abstract, §1] Abstract and §1: the efficiency claim is predicated on the 'necessary condition' that k-edge matchings in the auxiliary graphs can be counted efficiently, yet no complexity analysis, recurrence, or closed-form argument is supplied showing that the specific auxiliary graphs induced by the two-parameter (or Toeplitz) structure admit such counts; general matching enumeration remains #P-hard.
  2. [§2 (method)] The manuscript states a general reduction but does not exhibit the explicit product formula for hafnian(A+B) nor verify that the auxiliary matching multiplicities are independent of the numerical values inside the target hafnian; without these steps the reduction cannot be confirmed to be non-circular.
minor comments (2)
  1. [§2] Notation for the two-parameter matrix and the auxiliary graphs should be introduced with a single running example before the general expansion is stated.
  2. [§3, §4] The two worked Toeplitz cases should include a small explicit matrix together with the resulting matching-count formula so that the reader can verify the reduction by hand.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the detailed comments. We address each major point below and will revise the manuscript to improve the presentation of the reduction and to clarify the scope of the efficiency claims.

read point-by-point responses

  1. Referee: [Abstract, §1] Abstract and §1: the efficiency claim is predicated on the 'necessary condition' that k-edge matchings in the auxiliary graphs can be counted efficiently, yet no complexity analysis, recurrence, or closed-form argument is supplied showing that the specific auxiliary graphs induced by the two-parameter (or Toeplitz) structure admit such counts; general matching enumeration remains #P-hard.

    Authors: The manuscript derives explicit closed-form expressions for the hafnian in the two Toeplitz special cases, which necessarily means that the relevant k-edge matching counts on the auxiliary graphs admit closed forms in those instances. We agree that no general complexity analysis is supplied for arbitrary two-parameter matrices, since the method's practicality is structure-dependent. We will revise the abstract and §1 to state explicitly that efficiency is established via the closed forms obtained in the specific cases considered, rather than claimed for the general two-parameter setting. revision: yes

  2. Referee: [§2 (method)] The manuscript states a general reduction but does not exhibit the explicit product formula for hafnian(A+B) nor verify that the auxiliary matching multiplicities are independent of the numerical values inside the target hafnian; without these steps the reduction cannot be confirmed to be non-circular.

    Authors: We will add the explicit product formula for hafnian(A + B) to the revised §2. The multiplicities count the combinatorial ways of assigning the edges of a perfect matching to the two summands and are therefore independent of the numerical entries; we will include a short verification of this independence to confirm that the reduction is non-circular. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation reduces to independent matching enumeration

full rationale

The paper presents a method based on the hafnian(A+B) expansion into submatrix products, then reduces the result to counting k-edge matchings in auxiliary graphs arising from the two-parameter structure. This reduction is stated as an explicit necessary condition rather than derived by fitting parameters to the hafnian or by self-definition. No load-bearing step equates a claimed prediction or formula to its own inputs by construction, and no self-citation chain is invoked to force uniqueness or an ansatz. The special-case analytical formulas for Toeplitz matrices and chord diagrams are presented as new derivations from the matching counts, without evidence of circular renaming or smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, ad-hoc axioms, or invented entities are stated. The work rests on standard properties of the hafnian and the (unstated) product formula for hafnians of matrix sums.

axioms (1)
  • domain assumption Hafnian of a sum of two matrices equals a product of hafnians of submatrices (invoked as the basis of the method)
    Abstract presents this as the key identity without derivation or citation in the provided text.

pith-pipeline@v0.9.0 · 5731 in / 1272 out tokens · 36197 ms · 2026-05-24T14:08:50.095957+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Complexity phase transition for continuous-variable cluster state

    quant-ph 2026-04 unverdicted novelty 6.0

    Squeezing levels in CV cluster states mark a phase transition between classically tractable and intractable regimes for measurement-based linear optics.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages · cited by 1 Pith paper

  1. [1]

    A faster hafnian formula for complex matrices and its benchmarking on a supercomputer // ACM Journal of Experimental Algorithmics

    Bj¨ orklund A., Gupt B., Quesada N. A faster hafnian formula for complex matrices and its benchmarking on a supercomputer // ACM Journal of Experimental Algorithmics. 2019. V. 24. 1.11

    work page 2019

  2. [2]

    Enumeration of Dimer (Domino) Configurations // Discrete Mathematics

    Grimson R.C. Enumeration of Dimer (Domino) Configurations // Discrete Mathematics. 1977. V. 18. pp. 167–178

    work page 1977

  3. [3]

    Enumeration of chord diagrams without loops and parallel chords // The Electronic Journal of Combinatorics

    Krasko E., Omelchenko A. Enumeration of chord diagrams without loops and parallel chords // The Electronic Journal of Combinatorics. 20 17. 24(3). #3.43

    work page

  4. [4]

    Linear chord diagrams with long chords // The Electronic Jour- nal of Combinatorics

    Sullivan E. Linear chord diagrams with long chords // The Electronic Jour- nal of Combinatorics. 2017. V. 24(4). pp. 1–8

    work page 2017

  5. [5]

    The hafnian and a commutative analogue of the Grassmann algebra // Electronic Journal of Linear Algebra

    Efimov D.B. The hafnian and a commutative analogue of the Grassmann algebra // Electronic Journal of Linear Algebra. 2018. V. 34. pp. 5 4-60

    work page 2018

  6. [6]

    Complementary Matching Vectors and the Uniform Matching Extension Property // European Journal of Combinatorics

    Zaslavsky T. Complementary Matching Vectors and the Uniform Matching Extension Property // European Journal of Combinatorics. 1981 . V. 2. pp. 91–103

    work page 1981

  7. [7]

    The Number of Domino Matchings in the Game of Memory // Journal of Integer Sequences

    Young D. The Number of Domino Matchings in the Game of Memory // Journal of Integer Sequences. 2018. V. 21(8). pp. 1–14

    work page 2018

  8. [8]

    The hafnian of Toeplitz matrices of special type, perfect matchings and Bessel polynomials // Bulletin of Syktyvkar University

    Efimov D.B. The hafnian of Toeplitz matrices of special type, perfect matchings and Bessel polynomials // Bulletin of Syktyvkar University . Se- ries 1: Mathematics. Mechanics. Informatics. 2018. V. 3(28). pp . 56–64. (in Russian)

    work page 2018

  9. [9]

    Sloane, editor The On-Line Encyclopedia of Integer Sequences, pub- lished electronically at https://oeis.org

    N.J.A. Sloane, editor The On-Line Encyclopedia of Integer Sequences, pub- lished electronically at https://oeis.org

    work page

  10. [10]

    Statistics on Linear Chord Diagrams // Dis- crete Mathematics and Theoretical Computer Science

    Cameron N.T., Killpatrick K. Statistics on Linear Chord Diagrams // Dis- crete Mathematics and Theoretical Computer Science. 2019. V. 2 1(2). pp. 1–10. 12

    work page 2019