An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality

Aditi Laddha; Madhusudhan Reddy Pittu

REVIEW 3 major objections 7 minor 23 references

An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality

T0 review · 3 major / 7 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For any nonnegative or positive-semidefinite matrix, the permanent is upper-bounded by the product of diagonal entries produced by a Gaussian-elimination-style 'permanent process' that runs in O(n³) operations.

desk verdict The permanent process is a genuinely new algorithmic idea, but the paper as written overclaims: the main theorem is false without a nonzero-pivot hypothesis, and the PSD proof and the Section 4.2 recurrence both have indexing mistakes that are fixable but load-bearing. read the letter →

arxiv 2509.08121 v1 pith:RY6O7TI7 submitted 2025-09-09 cs.DM math.CO

Aditi Laddha , Madhusudhan Reddy Pittu This is my paper · ORCID

classification cs.DMmath.CO MSC 15A1568Q25

keywords permanentpermanentalinverseSchurformulaprocessupperboundsnonnegativematricespositivesemidefinitealgorithmicmethod

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper sets out to show that the permanent of any nonnegative or positive-semidefinite matrix can be bounded from above by a deterministic, O(n³)-time procedure that mirrors Gaussian elimination. The engine is a newly defined 'permanental inverse', built from permanents of deleted submatrices, together with a permanental version of Schur's determinant formula in which exact determinant identities become inequalities. Iterating this inequality yields the 'permanent process', whose final diagonal product provably dominates the permanent (Theorem 1.3); for matrices with an approximate diagonal-dominance property the same machinery gives per(A) ≤ (1+ε)^n times the product of the original diagonal entries. This matters because exact permanent computation is #P-complete, so cheap provable upper bounds are scarce tools for combinatorics, statistical physics, and quantum-optics estimates. The statement as written hides one domain condition: the process divides by each diagonal pivot, so it only runs when every pivot is nonzero, silently excluding matrices such as [[0,1],[1,0]].

What carries the argument

The load-bearing object is the permanental inverse B*, whose (i,j) entry is the ratio per(B_{j,i})/per(B); it plays the role the matrix inverse plays in determinant theory. Its defining consequence is the permanental Schur inequality per(A) ≤ per(B) · per(W + X^T B* Y) for block matrices, proved via a row-uncrossing lemma, which turns the exact Schur-complement identity into a one-sided permanent bound. The permanent process (Algorithm 1) is the algorithmic face of the same inequality: at step t it updates every trailing entry by a_{i,j} ← a_{i,j} + a_{i,t}a_{t,j}/a_{t,t} — Gaussian elimination with the minus sign turned into a plus — and the product of the diagonal entries of the final matr

What would settle it

Run Algorithm 1 on any nonnegative matrix with a strictly positive diagonal, say a random 4×4 matrix, and compare the product of the final diagonal entries with the permanent computed by brute force; if the product ever falls below the permanent, Theorem 1.3 is false. Separately, the 2×2 matrix [[0,1],[1,0]] has permanent 1 and a zero first pivot, so the theorem as worded — 'any nonnegative matrix' — cannot hold without a nonzero-pivot condition.

Watch

Extended reading notes

Core claim

On the paper's own terms: define the permanental inverse B* of a nonnegative matrix B by (B*)_{i,j} = per(B_{j,i})/per(B). Then the block inequality per([[B, Y],[X^T, W]]) ≤ per(B) · per(W + X^T B* Y) holds — a Schur formula for permanents, but an inequality where determinant theory has an equality. Iterating this inequality through the 'permanent process' (Algorithm 1), whose update a_{i,j} ← a_{i,j} + a_{i,t}a_{t,j}/a_{t,t} is Gaussian elimination with the sign flipped, yields Theorem 1.3: for every nonnegative or real positive-semidefinite matrix on which the process runs, per(A) ≤ ∏ a^{(i)}_{i,i}, the product of the final diagonal entries. Under an approximate diagonal-dominance hypothes

Load-bearing premise

The algorithm divides by each diagonal pivot at every step, yet the main theorem is stated for all nonnegative or positive-semidefinite matrices — including matrices whose pivots can be zero — so the bound is actually proven only for matrices on which the process can run to completion.

Editorial extensions

If this is right

A deterministic O(n³) procedure now produces provable upper bounds on permanents of nonnegative and PSD matrices, a task whose exact version is #P-complete.
For matrices obeying the approximate diagonal-dominance condition of Theorem 1.6, the bound is per(A) ≤ (1+ε)^n · ∏ a_{i,i}: the diagonal product inflated by a factor whose base can be made arbitrarily close to 1.
On structured families like c^{-|i-j|} Toeplitz-type matrices, the process keeps the bound at e when c_n = Ω(√n), a regime where the product-of-row-sums bound grows without bound.
Theorem 5.2 keeps the representation size of every matrix entry polynomially bounded in the input size, so the iterative process can be executed without exponential blow-up in the stored numbers.
The paper notes the bound is not an O(1)^n approximation scheme in general: for the all-ones matrix the final diagonal product is 2^{O(n²)} while per(A) = n!, marking where the method is loose.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A free parameter the paper leaves untouched is the ordering of rows and columns: permuting the matrix before running the process changes the pivots and hence the bound, so minimizing the final diagonal product over orderings is a natural follow-up that could sharpen Theorem 1.3.
Because B*B ≥ I entrywise, the permanental inverse sits close to the theory of inverse-nonnegative matrices; characterizing matrices whose permanental inverse is itself nonnegative could reveal when the bound is nearly tight.
The PSD case rests entirely on nonnegativity of the coefficients of per(aB + xx^T), established via the tensor-product identity cited as Theorem 2.5; any matrix class whose permanent expansion keeps nonnegative coefficients would inherit the same algorithmic bound, a testable extension beyond PSD.
The paper never compares its deterministic bound with randomized capacity-based approximation guarantees on the same PSD instances; such a comparison would show where the permanent process is competitive and where the (1+ε)^n-style guarantees are sharper.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the permanent process is a new idea worth knowing about, but the central guarantee is false as stated, and two other proofs have indexing mistakes that need fixing.

The permanental inverse and the permanental Schur inequality are genuinely new relative to what I know; the rank-one update formula (Observation 3.4) is exact and elegant. The algorithmic template is natural—Gaussian elimination with a plus instead of a minus—and the claim that it gives strong bounds for the approximate-diagonal-dominance class would be interesting if the proof held up.

Soft spots, in order of severity. First, Theorem 1.3 asserts the bound for every nonnegative or PSD matrix, but Algorithm 1 divides by a(t)_{t,t}; for the 2x2 matrix [[0,1],[1,0]] the first pivot is 0, the algorithm cannot run, and the statement is false as written. The missing nonzero-pivot condition is not cosmetic—the proof of Theorem 4.1 divides by pivots at every step. Second, the PSD half of the proof relies on Lemma 4.2, and the proof there misindexes the coefficients of per(aB+xx^T). With B (n-1)x(n-1), that polynomial has degree n-1, not n; the identity they write, a^2 α0 + a α1 = per([[B,x],[x^T,a]]), does not hold. The correct identity is per(A) = a per(B) + Σ x_i x_j per(B_{j,i}). The inequality may still be true—the missing terms are nonnegative for nonnegative matrices and plausibly for PSD—but the proof as written does not show it. Third, the recurrence in Section 4.2 sums to min(i,j) instead of min(i,j)-1. That makes (12) self-referential and the base case of Theorem 4.3 inconsistent, so the condition in Theorem 1.6 is also off by one.

Credit where due: the definitions are clean, the worked example in Section 4.4 is concrete, and Section 5.2 honestly admits the bound is 2^{O(n^2)} for the all-ones matrix, so the authors are not overselling the general case. The representation-size analysis is a serious attempt at numerical stability.

Who this is for: anyone working on deterministic upper bounds for permanents. The framework is novel enough that I would send it to a referee, not desk reject, but the errors mean the current statements should not be trusted. A careful revision that fixes the pivot condition, the PSD coefficient expansion, and the off-by-one recurrence could make this a solid contribution.

Referee Report

3 major / 7 minor

Summary. The paper introduces a permanental analogue of the matrix inverse and a permanental Schur inequality (Theorem 1.2), and defines an iterative 'permanent process' (Algorithm 1) that is claimed to upper-bound the permanent of any real nonnegative or PSD matrix (Theorem 1.3). It also derives a structured-matrix bound (Theorem 1.6) and a numerical-stability result (Theorem 5.2). The approach is deterministic and runs in O(n^3) operations.

Significance. The central idea is attractive: it gives a deterministic, linear-algebraic method for upper-bounding permanents, with an explicit algorithm and falsifiable bounds. The permanental inverse is a new object, and the structured-matrix bound (Theorem 1.6) is explicit. If the main theorem were established, the paper would add a useful tool for regimes where product-of-row-sums is weak, as illustrated by the exponential-kernel example in Section 4.4. However, the current manuscript contains several load-bearing proof errors and an unstated domain condition, so the main theorem is not proven as stated.

major comments (3)

[Theorem 1.3 / Algorithm 1] The theorem claims a bound for every real nonnegative or PSD matrix, but Algorithm 1 divides by a^{(t)}_{t,t} at every step, and the proof of Theorem 4.1 divides by a_{1,1} and recursively by later pivots. No nonzero-pivot hypothesis is stated. For A=[[0,1],[1,0]], per(A)=1 but a^{(1)}_{1,1}=0, so the first update is undefined. This makes the main claim false as written. A correct statement must either assume a^{(t)}_{t,t} != 0 throughout, or add a preprocessing step (for nonnegative matrices with positive permanent, a column permutation makes the diagonal positive; for PSD, a zero diagonal entry forces the permanent to be zero). The proof and abstract must be revised accordingly.
[Section 4.2, Eqs. (10)-(12)] The recurrence sums from s=1 to min(i,j), but entry (i,j) is last updated at step min(i,j)-1. Consequently, the term s=min(i,j) in (12) is self-referential: for i<=j, s=i gives u_{i,j} on both sides. The claim that 's < min(i,j)' for all terms is false for the final term. The induction in Theorem 4.3 cannot apply the inductive hypothesis to the s=t term. The upper limit should be min(i,j)-1 throughout; with that correction the induction goes through.
[Lemma 4.2, proof] The expansion per(aB+xx^T)=sum_{l=0}^n a^l alpha_{n-l} makes alpha_0 the coefficient of a^n, which is zero for n>1, not per(B); alpha_1 is the coefficient of a^{n-1}, equal to per(B) if the intended indexing is degree n-1. The displayed identity 'a^2 alpha_0 + a alpha_1 = a(...) = per([[B,x],[x^T,a]])' is therefore algebraically incorrect (it also uses [n] instead of [n-1] in the summation). The intended argument should compare a^{n-2} per(A) with the leading terms of per(aB+xx^T). Since the PSD case of Theorem 1.3 rests on this lemma, the proof must be rewritten.

minor comments (7)

[Theorem 1.3 proof] The proof says 'from Theorem 1.3' but should say 'from Theorem 4.1', and 'lower bound' should be 'upper bound'.
[Section 4.1 title] Title has typos: 'Postitive Semidefinite Matirces' should be 'Positive Semidefinite Matrices'.
[Section 3.2] Typo 'qquation' should be 'equation'.
[Definition 3.1] The permanental inverse is defined for a d x d matrix B, but the text says 'B* is an n x n matrix'; should be d x d.
[Theorem 4.1] The statement says 'for 1<=t<=n' but A^{(t+1)} is undefined for t=n. Either define A^{(n+1)} or restrict to 1<=t<=n-1 and handle t=n separately.
[Lemma 4.2 proof] The reference 'Lemma 2.4' should be 'Theorem 2.5' (the Marcus-Newman formula is Theorem 2.5).
[Section 5.2] Typo: 'all1's matrix' should be 'all-ones matrix'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the permanent process bound is derived from an explicit inequality chain and telescoping product, not from its own conclusion.

full rationale

The derivation is self-contained. The permanental inverse (Def. 3.1) is defined via normalized permanents of submatrices, but it is used only to express the exact rank-one expansion (Observation 3.4), which is an identity. Theorem 1.2 is obtained from the row-uncrossing Lemma 3.5, whose proof is an explicit expansion and induction argument and does not assume the target inequality. The permanent process update (Eq. 8) is then shown to satisfy the diagonal lower bound of Theorem 4.1; the key inequality (9), per(A^(2)(-{1})) >= per(A)/a_{1,1}, is a direct application of Lemma 3.7 for nonnegative matrices and Lemma 4.2 for PSD matrices, both proved from elementary expansions (and, for PSD, the external Marcus--Newman tensor formula). Multiplying these lower bounds telescopes exactly to per(A) <= prod_i a_{i,i}^{(i)}, giving Theorem 1.3 without any fitted parameter or circular dependency. Theorem 1.6 and the Section 4.4 example are further genuine consequences of the same recurrence; Claim 4.5 is proved by direct induction in Appendix A. There are no self-citations carrying any load. One non-circular correctness issue should be noted: Theorem 1.3 and the abstract assert the bound for every nonnegative/PSD matrix, but Algorithm 1 and the proof of Theorem 4.1 divide by each pivot a_{t,t}^{(t)}; matrices with a zero first pivot, e.g. [[0,1],[1,0]], have per(A)=1 yet no A^(n) is produced. This is an unstated domain restriction (nonzero pivots), not a circularity, and does not affect the derivation for matrices where the process is defined.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces the mathematical construction 'permanental inverse', but this is a definition, not an empirically postulated entity. No free parameters are fitted to data. The main unstated assumption is the nonzero-pivot requirement.

assumptions (3)

standard math Permanent is super-multiplicative for nonnegative matrices: per(CD) ≥ per(C) per(D).
Used in Section 3.1.3 to compare per(B*)·per(B) with per(B*B).
standard math Marcus and Newman representation of the permanent of a PSD matrix as a norm of a sum of tensor products.
Used in Lemma 4.2's proof to argue α_ℓ ≥ 0.
ad hoc to paper All pivots a^{(t)}_{t,t} remain nonzero throughout the permanent process.
The update rule divides by a^{(t)}_{t,t}; Theorem 1.3 states 'nonnegative or PSD' without this condition, and matrices such as [[0,1],[1,0]] violate it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality." pith.science (2026). https://pith.science/paper/RY6O7TI7

@misc{pith2026250908121,
  author       = {Pith},
  title        = {Pith review of: An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RY6O7TI7}},
  note         = {Machine review of arXiv:2509.08121}
}

read the original abstract

Computing the permanent of a non-negative matrix is a computationally challenging, \#P-complete problem with wide-ranging applications. We introduce a novel permanental analogue of Schur's determinant formula, leveraging a newly defined \emph{permanental inverse}. Building on this, we introduce an iterative, deterministic procedure called the \emph{permanent process}, analogous to Gaussian elimination, which yields constructive and algorithmically computable upper bounds on the permanent. Our framework provides particularly strong guarantees for matrices exhibiting approximate diagonal dominance-like properties, thereby offering new theoretical and computational tools for analyzing and bounding permanents.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

[1]

The computational complexity of linear optics

Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , STOC '11, page 333–342, New York, NY, USA, 2011. Association for Computing Machinery

work page 2011
[2]

The computational complexity of linear optics

Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 333--342, 2011

work page 2011
[3]

Simply exponential approximation of the permanent of positive semidefinite matrices

Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, and Amin Saberi. Simply exponential approximation of the permanent of positive semidefinite matrices. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 914--925. IEEE, 2017

work page 2017
[4]

L. M. Bregman. Some properties of nonnegative matrices and their permanents. Sov. Math., Dokl. , 14:945--949, 1973

work page 1973
[5]

On approximability of the permanent of psd matrices

Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan. On approximability of the permanent of psd matrices. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 625--630, 2025

work page 2025
[6]

Bounds on the permanent and some applications

Leonid Gurvits and Alex Samorodnitsky. Bounds on the permanent and some applications. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages 90--99, 2014

work page 2014
[7]

Kräuter, and T.S

Suk-Geun Hwang, Arnold R. Kräuter, and T.S. Michael. An upper bound for the permanent of a nonnegative matrix. Linear Algebra and its Applications , 281(1):259--263, 1998

work page 1998
[8]

Computing monomer-dimer systems through matrix permanent

Yan Huo, Heng Liang, Si-Qi Liu, and Fengshan Bai. Computing monomer-dimer systems through matrix permanent. Phys. Rev. E , 77:016706, Jan 2008

work page 2008

Show all 23 references

[9]

An upper bound for the permanent of (0,1)-matrices

Heng Liang and Fengshan Bai. An upper bound for the permanent of (0,1)-matrices. Linear Algebra and its Applications , 377:291--295, 2004

2004
[10]

Inapproximability of positive semidefinite permanents and quantum state tomography

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

2023
[11]

Upper bounds for permanents of ( \ 0,\,1\ ) -matrices

Henryk Minc. Upper bounds for permanents of ( \ 0,\,1\ ) -matrices. Bulletin of the American Mathematical Society , 69:789--791, 1963

1963
[12]

Permanents

Henryk Minc. Permanents . Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1984

1984
[13]

Permanents

Marvin Marcus and Henryk Minc. Permanents. The American Mathematical Monthly , 72(6):577--591, 1965

1965
[14]

Inequalities for the permanent function

Marvin Marcus and Morris Newman. Inequalities for the permanent function. Annals of Mathematics , 75(1):47--62, 1962

1962
[15]

An upper bound for permanents of nonnegative matrices

Alex Samorodnitsky. An upper bound for permanents of nonnegative matrices. Journal of Combinatorial Theory, Series A , 115(2):279--292, 2008

2008
[16]

A short proof of minc's conjecture

Alexander Schrijver. A short proof of minc's conjecture. J. Comb. Theory A , 25:80--83, 1978

1978
[17]

Counting 1-factors in regular bipartite graphs

Alexander Schrijver. Counting 1-factors in regular bipartite graphs. J. Comb. Theory Ser. B , 72(1):122–135, January 1998

1998
[18]

Permanents in linear optical networks

Stefan Scheel. Permanents in linear optical networks. arXiv preprint quant-ph/0406127 , 2004

2004 arXiv
[19]

George W. Solues. Extending the minc-brègman upper bound for the permanent. Linear and Multilinear Algebra , 47(1):77--91, 2000

2000
[20]

George W. Soules. New permanental upper bounds for nonnegative matrices. Linear and Multilinear Algebra , 51(4):319--337, 2003

2003
[21]

Random point fields associated with certain fredholm determinants i: fermion, poisson and boson point processes

Tomoyuki Shirai and Yoichiro Takahashi. Random point fields associated with certain fredholm determinants i: fermion, poisson and boson point processes. Journal of Functional Analysis , 205(2):414--463, 2003

2003
[22]

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

1979
[23]

Maximizing products of linear forms, and the permanent of positive semidefinite matrices

Chenyang Yuan and Pablo A Parrilo. Maximizing products of linear forms, and the permanent of positive semidefinite matrices. Mathematical Programming , 193(1):499--510, 2022

2022

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

The computational complexity of linear optics

Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , STOC '11, page 333–342, New York, NY, USA, 2011. Association for Computing Machinery

work page 2011

[2] [2]

The computational complexity of linear optics

Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 333--342, 2011

work page 2011

[3] [3]

Simply exponential approximation of the permanent of positive semidefinite matrices

Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, and Amin Saberi. Simply exponential approximation of the permanent of positive semidefinite matrices. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 914--925. IEEE, 2017

work page 2017

[4] [4]

L. M. Bregman. Some properties of nonnegative matrices and their permanents. Sov. Math., Dokl. , 14:945--949, 1973

work page 1973

[5] [5]

On approximability of the permanent of psd matrices

Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan. On approximability of the permanent of psd matrices. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 625--630, 2025

work page 2025

[6] [6]

Bounds on the permanent and some applications

Leonid Gurvits and Alex Samorodnitsky. Bounds on the permanent and some applications. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages 90--99, 2014

work page 2014

[7] [7]

Kräuter, and T.S

Suk-Geun Hwang, Arnold R. Kräuter, and T.S. Michael. An upper bound for the permanent of a nonnegative matrix. Linear Algebra and its Applications , 281(1):259--263, 1998

work page 1998

[8] [8]

Computing monomer-dimer systems through matrix permanent

Yan Huo, Heng Liang, Si-Qi Liu, and Fengshan Bai. Computing monomer-dimer systems through matrix permanent. Phys. Rev. E , 77:016706, Jan 2008

work page 2008