pith. sign in

arxiv: 2604.24192 · v1 · submitted 2026-04-27 · 🧮 math.CO · cs.DM

On Chollet's Permanent Conjecture for Graph Laplacians

Priyanshu Pant , Ranveer Singh This is my paper

Pith reviewed 2026-05-08 02:42 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords Chollet's conjecturepermanent inequalityHadamard productZ-matricesgraph Laplaciansbipartite graphsvertex coalescence
0
0 comments X

The pith

Chollet's inequality holds for symmetric Z-matrices with bipartite support graphs.

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

The paper proves that per(A ∘ A) ≤ per(A)^2 for symmetric Z-matrices with nonnegative diagonal entries when the support graph is bipartite. This provides a verified case of Chollet's conjecture. The authors develop a compositional framework showing that the inequality for graph Laplacians is preserved under vertex coalescence, allowing extension to larger families of graphs from basic ones. Readers might care as this gives structural control over a hard-to-compute function in graph theory and matrix analysis.

Core claim

We prove per(A∘A)≤per(A)^2 for symmetric Z-matrices with nonnegative diagonal whose support graph is bipartite. Motivated by this, we study the Laplacian inequality per(L_G ∘ L_G)≤per(L_G)^2. We introduce a compositional framework for permanental inequalities on graph Laplacians, showing that Chollet's inequality is preserved under vertex coalescence. This enables the extension of the inequality from basic graph classes to large structured families.

What carries the argument

The compositional framework for permanental inequalities using vertex coalescence on graph Laplacians.

If this is right

  • The inequality holds for Laplacians of graphs built by coalescing from bipartite graphs.
  • New tractable regimes for the permanent of Laplacians are identified.
  • Chollet's conjecture is settled for these matrix classes.

Where Pith is reading between the lines

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

  • The framework could be applied to prove the conjecture for all graphs if coalescence generates sufficiently many graphs.
  • Analogous methods might work for other permanental or combinatorial inequalities.
  • Verification on small graphs outside the bipartite case could show if the inequality is more general.

Load-bearing premise

The support graph of the matrix is bipartite.

What would settle it

A symmetric Z-matrix with nonnegative diagonal, bipartite support graph, and per(A∘A) > per(A)^2 would falsify the main claim.

read the original abstract

In 1982, Chollet conjectured that $\mathrm{per}(A\circ B)\le \mathrm{per}(A)\mathrm{per}(B)$ for Hermitian positive semidefinite matrices $A,B$, where $\circ$ denotes the Hadamard product, and observed that in the real symmetric case it suffices to prove $\mathrm{per}(A\circ A)\le \mathrm{per}(A)^2$. We prove $\mathrm{per}(A\circ A)\le \mathrm{per}(A)^2$ for symmetric $Z$-matrices with nonnegative diagonal whose support graph is bipartite. Motivated by this, we study the Laplacian inequality $\mathrm{per}(L_G\circ L_G)\le \mathrm{per}(L_G)^2$ for the graph Laplacian $L_G$. We introduce a compositional framework for permanental inequalities on graph Laplacians, showing that Chollet's inequality is preserved under vertex coalescence. This enables the extension of the inequality from basic graph classes to large structured families, revealing new tractable regimes for a fundamentally $\#P$-hard quantity.

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

0 major / 4 minor

Summary. The paper proves per(A ∘ A) ≤ per(A)^2 for symmetric Z-matrices with nonnegative diagonal whose support graph is bipartite. It then introduces a compositional framework for graph Laplacians showing that the inequality is preserved under vertex coalescence, allowing the result to extend from basic graphs to larger structured families.

Significance. If the derivations hold, the work supplies a verifiable regime for Chollet's conjecture and a constructive preservation lemma under coalescence. This is useful because permanent evaluation is #P-hard in general; identifying explicit classes and closure properties for graph Laplacians adds concrete tractable cases. The direct proof for the bipartite-support Z-matrix setting and the compositional argument are the main technical contributions.

minor comments (4)
  1. Abstract: the conjecture is stated for Hermitian PSD matrices, yet the theorem is proved only for real symmetric Z-matrices; a one-sentence remark on the relationship between these classes would help orient readers.
  2. Introduction or §2: the support graph (edges for nonzero off-diagonal entries) is central to the hypothesis; a brief formal definition and a small illustrative matrix would improve clarity.
  3. The coalescence section: the preservation lemma is stated at a high level; adding a short worked example (e.g., coalescing two vertices in K_{2,2}) would make the inductive step easier to verify.
  4. Notation: the symbol L_G for the Laplacian and the precise definition of the Hadamard product in the permanental context should be recalled once in the main text before the first theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary of our work and the recommendation for minor revision. The report accurately captures the main contributions but raises no specific major comments or points requiring clarification.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes per(A∘A) ≤ per(A)^2 via direct proof for symmetric Z-matrices with nonnegative diagonal and bipartite support graph, then extends to graph Laplacians by proving preservation under vertex coalescence. Neither the core inequality nor the compositional framework reduces by the paper's own equations to a fitted parameter, self-referential definition, or load-bearing self-citation. The bipartiteness restriction is explicitly stated as the domain of validity, and the coalescence argument is a standard constructive technique whose verification is independent of the target inequality. No step matches any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard properties of the permanent and the definition of graph Laplacians; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • standard math The permanent is a multilinear function of the rows (or columns) of a matrix.
    Invoked implicitly when manipulating per(A∘A) and per(L_G).
  • domain assumption Graph Laplacians are symmetric Z-matrices with nonnegative diagonal entries.
    Used to motivate the study of L_G and to place it inside the proved class.

pith-pipeline@v0.9.0 · 5488 in / 1267 out tokens · 48493 ms · 2026-05-08T02:42:48.189379+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    The computational complexity of linear optics.Theory of Computing, 9(4):143–252, 2013

    Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics.Theory of Computing, 9(4):143–252, 2013

    work page 2013

  2. [2]

    LeRoy B. Beasley. Maximal groups on which the permanent is multiplicative.Canadian Journal of Mathematics, 21:495–497, 1969

    work page 1969

  3. [3]

    Brualdi and Herbert J

    Richard A. Brualdi and Herbert J. Ryser.Combinatorial Matrix Theory. Cambridge University Press, 1991

    work page 1991

  4. [4]

    Quantum-inspired permanent identities.Quantum, 6:877, 2022

    Ulysse Chabaud, Abhinav Deshpande, and Saeed Mehraban. Quantum-inspired permanent identities.Quantum, 6:877, 2022

    work page 2022

  5. [5]

    Cerf, and Raul Garcia-Patron

    Levon Chakhmakhchyan, Nicolas J. Cerf, and Raul Garcia-Patron. Quantum-inspired algo- rithm for estimating the permanent of positive semidefinite matrices.Physical Review A, 96(2):022329, 2017

    work page 2017

  6. [6]

    Permanental inequalities for positive semidefinite matrices.Linear Algebra and Its Applications, 45:187–195, 1982

    John Chollet. Permanental inequalities for positive semidefinite matrices.Linear Algebra and Its Applications, 45:187–195, 1982

    work page 1982

  7. [7]

    R. J. Gregorac and I. R. Hentzel. On chollet’s inequality for permanents.Linear Algebra and Its Applications, 93:227–241, 1987

    work page 1987

  8. [8]

    Permanental inequalities for correlation matrices.SIAM Journal on Matrix Analysis and Applications, 9(2):194–201, 1988

    Robert Grone and Stephen Pierce. Permanental inequalities for correlation matrices.SIAM Journal on Matrix Analysis and Applications, 9(2):194–201, 1988

    work page 1988

  9. [9]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson.Matrix Analysis. Cambridge University Press, Cam- bridge, 2 edition, 2012

    work page 2012

  10. [10]

    The Chollet permanental conjecture for4 times4matrices.Linear and Multilinear Algebra, 69(6):1094–1110, 2021

    George Hutchinson. The Chollet permanental conjecture for4 times4matrices.Linear and Multilinear Algebra, 69(6):1094–1110, 2021

    work page 2021

  11. [11]

    On the complexity of computing determinants.Computa- tional Complexity, 13(3–4):91–130, 2005

    Erich Kaltofen and Gilles Villard. On the complexity of computing determinants.Computa- tional Complexity, 13(3–4):91–130, 2005

    work page 2005

  12. [12]

    Elliott H. Lieb. Proofs of some conjectures on permanents.Journal of Mathematics and Mechanics, 16(2):127–134, 1966

    work page 1966

  13. [13]

    Plummer.Matching Theory

    László Lovász and Michael D. Plummer.Matching Theory. North-Holland, 1986

    work page 1986

  14. [14]

    Inapproximability of positive semidefinite permanents and quantum state tomography.Algorithmica, 85(12):3828–3854, 2023

    Alexander Meiburg. Inapproximability of positive semidefinite permanents and quantum state tomography.Algorithmica, 85(12):3828–3854, 2023

    work page 2023

  15. [15]

    Addison–Wesley, 1978

    Henryk Minc.Permanents. Addison–Wesley, 1978

    work page 1978

  16. [16]

    Oppenheim

    A. Oppenheim. Inequalities connected with definite hermitian forms.Journal of the London Mathematical Society, 5(2):114–119, 1930

    work page 1930

  17. [17]

    Vehbi E. Paksoy. A permanent inequality for positive semidefinite matrices.Electronic Journal of Linear Algebra, 39:71–77, February 2023

    work page 2023

  18. [18]

    Chollet’s permanent conjecture for4 times4matrices.Linear and Multilinear Algebra, 72(16):2633–2638, 2024

    Kijti Rodtes. Chollet’s permanent conjecture for4 times4matrices.Linear and Multilinear Algebra, 72(16):2633–2638, 2024. 12

    work page 2024

  19. [19]

    Permanents of correlation matrices and the Chollet permanental conjecture.Linear and Multilinear Algebra, 73(18):4084–4096, 2025

    Suchittra Sa-nguansin and Kijti Rodtes. Permanents of correlation matrices and the Chollet permanental conjecture.Linear and Multilinear Algebra, 73(18):4084–4096, 2025

    work page 2025

  20. [20]

    Publish or Perish, Houston, TX, 3 edition, 1994

    Michael Spivak.Calculus. Publish or Perish, Houston, TX, 3 edition, 1994. See p. 383

    work page 1994

  21. [21]

    Leslie G. Valiant. The complexity of computing the permanent.Theoretical Computer Science, 8(2):189–201, 1979

    work page 1979

  22. [22]

    Notes on Hadamard products of matrices.Linear and Multilinear Algebra, 25(3):237–242, 1989

    Fuzhen Zhang. Notes on Hadamard products of matrices.Linear and Multilinear Algebra, 25(3):237–242, 1989

    work page 1989

  23. [23]

    An analytic approach to a permanent conjecture.Linear Algebra and Its Applications, 438(4):1570–1579, 2013

    Fuzhen Zhang. An analytic approach to a permanent conjecture.Linear Algebra and Its Applications, 438(4):1570–1579, 2013

    work page 2013

  24. [24]

    An update on a few permanent conjectures.Special Matrices, 4:305–322, 2016

    Fuzhen Zhang. An update on a few permanent conjectures.Special Matrices, 4:305–322, 2016. A Cycles For the cycleCn onn≥3vertices we denote the number of matchings of sizetbym n,t. We will use the classical recurrence; see [13]. Lemma A.1.Forn≥4andt≥1, mn,t =m n−1,t +m n−2,t−1, with conventionsm k,ℓ = 0forℓ <0orℓ >⌊k/2⌋, andm n,0 = 1for alln. Proof of Theo...

    work page 2016