Pith. sign in

REVIEW 2 major objections 4 minor 14 references

On universal quadratic inequalities for minors of TNN matrices

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves that a quadratic inequality on minors holds for every totally nonnegative matrix exactly when, for each feasible planar matching attached to the right-hand side, the left-hand side contains at least as many occurrences…

desk verdict Strong matching-based characterization of universal quadratic inequalities for TNN matrices, but the converse direction leans on a key network-existence proposition quoted from the authors' earlier paper rather than proved here. read the letter →

arxiv 2506.03754 v2 pith:QUFPVSUC submitted 2025-06-04 math.CO

Vladimir I. Danilov , Alexander V. Karzanov , Gleb A. Koshevoy This is my paper
classification math.CO MSC 05C7505E99
keywords totallynonnegativematricesquadraticinequalitiesonminorsplanarmatchingsflow-generatedLindströmconstructionDodgsoncondensationtotalpositivityminor
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

Totally nonnegative (TNN) matrices are real matrices whose square subdeterminants, or minors, are all nonnegative; they appear throughout analysis, combinatorics, and probability. The paper asks which quadratic inequalities of the form 'sum of products of two minors ≥ sum of products of two minors' hold for every such matrix, and it answers the question completely. The answer is combinatorial: encode each product of minors by a set of noncrossing 'feasible matchings' on a circle, and an inequality is universal precisely when every matching that occurs in the right-hand family occurs at least as often in the left-hand family. This gives a recognition algorithm for universal inequalities and recovers classical examples such as submodularity and Dodgson-type relations as immediate corollaries.

What carries the argument

Feasible planar matchings. Place the elements of $Y$ on the lower half and the elements of $Y'$ on the upper half of a circle. A proper pair $(C,C')$ colors an element white if it belongs to $C\cup C'$ and black if it belongs to $\bar C\cup\bar C'$. A perfect matching of $Y\sqcup Y'$ is feasible for $(C,C')$ when couples of equal color join the two halves, couples of different colors stay inside one half, and the chords do not cross. The matching carries the argument because of Lindström's construction: a product of two minors, say $\Delta_Q(XC|X'C')\Delta_Q(X\bar C|X'\bar C')$, expands as a sum over double flows in a planar network, and the symmetric difference of the two flows in a double flow splits into vertex-disjoint paths whose endpoint pairs form exactly a feasible matching. The exchange lemma (Lemma 3.2) shows that swapping the pieces of these paths turns a double flow for one proper pair into a double flow for another proper pair while preserving the matching and the product of the flow weights, which is what lets a matching-counting inequality be transferred into an inequality of matrix minors.

What would settle it

A concrete falsifier is to take a candidate inequality whose matching counts violate condition (ii) of Theorem 2.1, such as the pair $A=\{1,4\}$, $B=\{2,3\}$ in Proposition 5.1, and numerically evaluate both sides on a broad sample of TNN matrices. The theorem predicts a violation is always possible through the unit-weight planar network of Proposition 4.1; finding instead a TNN matrix on which the predicted failing inequality holds, or any inequality where the count condition holds yet some TNN matrix violates it, would refute the characterization.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 2.1. Fix disjoint row sets $X,Y$ and disjoint column sets $X',Y'$, and let $\mathcal A,\mathcal B$ be finite families of proper pairs $(C,C')$ with multiplicities allowed, where proper means $|X\cup C|=|X'\cup C'|$ and $|X\cup(Y-C)|=|X'\cup(Y'-C')|$. The inequality $$\sum_{(C,C')\in\mathcal A}\Delta_Q(XC|X'C')\Delta_Q(X(Y-C)|X'(Y'-C'))\ \ge\ \sum_{(C,C')\in\mathcal B}\Delta_Q(XC|X'C')\Delta_Q(X(Y-C)|X'(Y'-C'))$$ is valid for every $n\times n'$ totally nonnegative matrix $Q$ if and only if, for every planar matching $M$ on $Y\sqcup Y'$ that is feasible for some pair in $\mathcal B$, the number $\#_M(\mathcal A)$ of occurrences of $M$ among the feasible matchings of pairs in $\mathcal A$ is at least $\#_M(\mathcal B)$. This replaces an infinite family of matrix constraints by a finite combinatorial condition. The proof of sufficiency expresses each product of minors as a sum of double flows in a planar network and then uses an exchange lemma to pair contributions from $\mathcal B$ with equal-weight contributions from $\mathcal A$; necessity constructs, for any failing matching, a specific planar network whose unit-weight flow-generated matrix violates the inequality.

Load-bearing premise

The converse direction of Theorem 2.1 relies on a construction, taken from the authors' earlier paper, that for each feasible matching produces a planar network whose double-flow counts are exactly one when that matching is feasible and zero otherwise; if no such network existed, the proof would not produce a TNN matrix violating the inequality.

Editorial extensions

If this is right

  • Testing whether a quadratic inequality is universal now reduces to enumerating feasible planar matchings and comparing occurrence counts on the two sides.
  • The classical submodular inequality $\Delta(A)\Delta(B)\ge \Delta(A\cup B)\Delta(A\cap B)$ for equal-size sets is certified by a single feasible matching, so it holds for all TNN matrices.
  • The generalized Dodgson inequality (5.4) is TNN-universal for weakly separated equal-size sets exactly when the sets are strongly separated, and fails otherwise.
  • If the matching families of the two sides are incomparable under inclusion, then neither the inequality nor its reverse is universal.
  • Because every TNN matrix is flow-generated, the characterization implies that universal quadratic inequalities are exactly the inequalities forced by planar path counts.

Reading between the lines

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

  • The same matching-count argument should extend to inequalities with arbitrary nonnegative integer coefficients on both sides, since the families already carry multiplicities.
  • Randomized numerical testing over small planar networks with unit weights would provide a practical check of the characterization, since such flow-generated matrices are dense among TNN matrices.
  • The criterion is likely to transport to other semirings: over the tropical semiring, the same noncrossing-matching counts would describe universal inequalities for flow-generated matrices, potentially recovering tropical Plücker-type relations.
  • The counts $\#_M(\mathcal A)$ and $\#_M(\mathcal B)$ could be computed by interval dynamic programming over noncrossing matchings, avoiding explicit enumeration when the families are large.
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.

Referee Report

2 major / 4 minor

Summary. The paper gives a combinatorial characterization of universal quadratic inequalities on minors of totally nonnegative (TNN) matrices, stated as Theorem 2.1: a pair of families (A,B) of proper pairs is TNN-universal if and only if, for every feasible planar matching M occurring in B, the number of occurrences of M in A is at least that in B. The proof of the 'if' direction proceeds by representing TNN matrices via planar networks and rearranging double flows using Lemmas 3.1 and 3.2 from the authors' earlier paper [3]. The 'only if' direction rests on Proposition 4.1, also quoted from [3, pp. 461-66], which postulates a planar network whose flow counts indicate exactly the feasibility of a given matching. The paper closes with two illustrative applications: a submodular inequality and a generalized Dodgson-type inequality.

Significance. If the main theorem is correct, it is a substantial contribution: it reduces the validity of all quadratic inequalities on minors of TNN matrices, for arbitrary rectangle sizes, to a purely combinatorial counting condition on planar matchings. The statement is clean and the examples, especially the Dodgson-type generalization in Proposition 5.1, are appealing. The paper also credits its foundations explicitly and provides a concrete algorithmic recognition procedure, although the complexity of that procedure is not analyzed. However, the proof as written is not self-contained and contains a load-bearing gap in the double-flow expansion, so the significance can only be assessed after those issues are resolved.

major comments (2)
  1. [§4, Prop. 4.1] The expansion of the product of two minors as a sum over 'double flows' is not justified as stated. The definition in §3.2 does not require the two flows of a double flow to be vertex-disjoint from each other, yet Lemma 3.1 asserts that the symmetric difference of their edge sets splits into vertex-disjoint paths connecting boundary terminals. This is false for pairs of flows that share a split edge: for example, in a network with sources s1,s2, sinks t1,t2, and a single internal vertex v with edges s1->v, s2->v, v->t1, v->t2, the flows s1->v->t1 and s2->v->t2 share the split edge at v, and their symmetric difference consists of four paths ending at the internal split vertices, not at boundary terminals. If, on the other hand, 'double flow' is intended to mean a vertex-disjoint pair, then Eq. (4.1) is false: for the same network with unit weights, f({1}|{1'})f({2}|{2'})=1 while there is no vertex-disjoint pair of flows from s1 to t1 and from s2 to t2. The proof therefore needs either a precise definition of the double-flow set D(B,B') and a proof that Lemma 3.1 applies to every term in the product, or an explicit argument handling the non-vertex-disjoint pairs.
  2. [§4, Proposition 4.1] The converse implication (i)->(ii) of Theorem 2.1 rests entirely on Proposition 4.1, which asserts the existence of a planar network whose flow sets have the indicator behavior (P1)-(P2). This proposition is quoted from the authors' earlier paper [3, pp. 461-66] and is not proved or derived in the present text. It is also not a consequence of Lemmas 3.1 and 3.2, which only rearrange double flows inside a fixed network. Since a failure of (P1) or (P2) would invalidate the counterexample construction and hence the characterization, the paper should either include a complete proof of Proposition 4.1 or give a precise statement with a detailed reference and a verification that the construction in [3] indeed satisfies (P1) and (P2). Without this, the main theorem is not established by the manuscript as written.
minor comments (4)
  1. [§1 and §4] The definition of a double flow should explicitly state whether the two flows are required to be vertex-disjoint from each other; the current wording leaves this ambiguous, which is directly related to the gap in Eq. (4.1).
  2. [§4, Eq. (4.1)] The introduction promises an 'efficient' algorithm for recognizing TNN-universal inequalities, but the final paragraph of Section 4 only says that computing the feasible matchings is routine and that their number may be exponentially large. The complexity claim should be stated precisely, or the word 'efficient' should be qualified.
  3. [§5.2, Proof of Prop. 5.1] In the displayed equation preceding (4.1), the second factor on each side is written as ∆_Q(XB|X'B') and f(XB|X'B'), but it should be ∆_Q(X\bar{B}|X'\bar{B}') and f(X\bar{B}|X'\bar{B}') to match the definition of the proper pair. The missing overlines are confusing.
  4. [§5.2] In the induction step for k≥3, the base case and the inductive hypothesis are not stated explicitly, and the claim that A\hat{} and B\hat{} are again weakly but not strongly separated deserves a short justification.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorem is a genuine combinatorial characterization; reliance on the authors' prior Proposition 4.1 is transparent citation of independent earlier work, not a definitional or fitted circular step.

full rationale

Theorem 2.1 is not obtained by redefining the target notion. The forward implication (ii)->(i) is derived in Section 4 by expanding each minor product as a sum over double flows and using Lemmas 3.1 and 3.2 from [3] to transport each B-double-flow to an A-double-flow with equal weight; this is a real argument, not an identity by construction. The converse (i)->(ii) invokes Proposition 4.1, quoted from the authors' earlier paper [3, pp. 461-66], to build a planar network with prescribed flow uniqueness/emptiness properties that converts a matching-count violation into a TNN matrix violating (2.2). Although this proposition is load-bearing and self-cited, it is a separate published existence result with an explicit construction, not a restatement of the TNN-universality criterion, nor a parameter fitted to the data of the theorem. The paper does not define TNN-universality in terms of the matching counts; it proves their equivalence. No fitted input is renamed as a prediction, no known inequality is merely relabeled, and the cited prior work is independent support rather than an unverified premise smuggled in through self-citation. The reader's concern about Proposition 4.1 is a legitimate correctness/dependency risk, but not circularity.

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

No free parameters or invented entities. The central claim rests on four external theorems: Lindstrom's lemma, Brenti's converse, and two structural lemmas plus an existence proposition from the authors' earlier work [3]. The last is the least independently verifiable in the present paper.

assumptions (5)
  • standard math Lindstrom's lemma: minors of flow-generated matrices equal sums of weights of vertex-disjoint path systems.
    Used throughout, equations (3.1) and (3.2), to express minors as flow-generated functions.
  • domain assumption Any n x n' TNN matrix can be represented by Lindstrom's construction as a flow-generated matrix with nonnegative vertex weights.
    Invoked in Section 4 proof of (ii)->(i) via (3.3), due to Brenti [1]; replaces an arbitrary TNN matrix with a flow-generated function.
  • domain assumption Lemma 3.1 and Lemma 3.2 from [3]: structure of symmetric difference of double flow edge sets and existence/uniqueness of rearranged double flows.
    Restated with explanations in Section 3; proofs cited to [3]. These are load-bearing for the forward direction of Theorem 2.1.
  • domain assumption Proposition 4.1 from [3]: for each feasible matching there exists a planar network with unique flows for that matching and empty flow sets otherwise.
    Used to prove the converse (i)->(ii); proof cited to [3, pp. 461-66].
  • standard math Convention that the empty minor has value 1 and empty flow has weight 1.
    Stated at the start of Section 2 and used in Section 4's special case when X=X'=emptyset and C=C'=emptyset.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On universal quadratic inequalities for minors of TNN matrices." pith.science (2026). https://pith.science/paper/QUFPVSUC

@misc{pith2026250603754,
  author       = {Pith},
  title        = {Pith review of: On universal quadratic inequalities for minors of TNN matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QUFPVSUC}},
  note         = {Machine review of arXiv:2506.03754}
}
abstract

For positive integers $n,n'$, we give a combinatorial characterization for the set of quadratic inequalities on minors that are valid for all $n\times n'$ totally nonnegative matrices. This is obtained as a consequence from our earlier results on stable quadratic identities on minors of matrices generated by flows in planar graphs via Lindstr\"om's construction.

Figures

Figures reproduced from arXiv: 2506.03754 by the authors.

Figure 1
Figure 1. (a) Gb; (b) φ; (c) φ ′ ; (d) Eφ ⊔ Eφ′; (e) Eφ△Eφ′ 3.3 Rearranging double flows. Next we explain how to rearrange a double flow (φ, φ′ ) for (C, C′ ) so as to obtain a double flow for another proper pair (D, D′ ) in CX,Y,X′ ,Y ′. Let P(φ, φ′ ) denote the set of paths P1, . . . , Pp as in Lemma 3.1, where p = (m + m′ )/2. For P ∈ P(φ, φ′ ), let π(P) denote the pair of elements in Y ⊔ Y ′ corresponding to the end verti… view at source ↗
Figure 2
Figure 2. Creating (ψ, ψ′ ) from (φ, φ′ ) in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. left: graph G; middle: (24|2 ′3 ′ )-flow; right: (13|1 ′4 ′ )-flow To finish this section, note that, due to the criterion in Theorem 2.1, the task of recognizing whether a given pair (A, B) provides a universal inequality or not looks rather straightforward, as it reduces to computing the set MC,C′ of feasible matchings for each (C, C) ∈ A ∪ B (which is routine, though |MC,C′| may be exponentially large in |Y | + |… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

  1. [3]

    Danilov, A

    V. Danilov, A. Karzanov, and G. Koshevoy, Planar flows and quadratic relations over semirings, J. Algebraic Combin. 36 (3) (2012) 441–474

    work page 2012

  2. [1]

    Brenti, Combinatorics and total positivity, J

    F. Brenti, Combinatorics and total positivity, J. Combin. Theory , Ser. A, 71 (1995) 175–218

    work page 1995

  3. [2]

    Danilov and A.V Karzanov, On universal quadratic id entities for minors of quantum matrices, J

    V.I. Danilov and A.V Karzanov, On universal quadratic id entities for minors of quantum matrices, J. Algebra 488 (2017) 145–200

    work page 2017

  4. [4]

    Dodgson, Condensation of determinants, Proc

    C.L. Dodgson, Condensation of determinants, Proc. of the Royal Soc. of London 15 (1866) 150–155

    work page

  5. [5]

    Gantmacher and M.G

    F.R. Gantmacher and M.G. Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, Revised Edition , AMS Chelsea Publishing, Amer. Math. Soc., Providence, RI, 2002

    work page 2002

  6. [6]

    Bijective proofs for Schur function identities

    M. Fulmek, Bijective proofs for Schur function identiti es, arXiv:0909.5334v1[math.CO], 2009

    work page Pith review arXiv 2009

  7. [7]

    Fulmek and M

    M. Fulmek and M. Kleber, Bijective proofs for Schur funct ion identities which imply Dodgson’s condensation formula and Pl¨ ucker relations,Electron. J. Combin. 8 (1): Re- search Paper 16, 2001, 22 pp

    work page 2001

  8. [8]

    Inequalities for totally nonnegative matrices: Gantmacher--Krein, Karlin, and Laplace

    S.M. Fallat and P.K. Vishwakarma, Inequalities for tota lly nonnegative matrices: Gantmacher–Krein, Karlin, and Laplace, arXiv:2305.16485 (2023)

    work page Pith review arXiv 2023

Show all 14 references
  1. [9]

    M¨ uhlbach, On extending determinantal identities, Linear Algebra Appl

    G. M¨ uhlbach, On extending determinantal identities, Linear Algebra Appl. 132 (1990) 145–162

    1990

  2. [10]

    Gessel and X

    I.M. Gessel and X. Viennot, Binomial determinants, pat hs, and hook length formulae, Adv. Math. 58 (1985) 300–321

    1985

  3. [11]

    Lindstr¨ om, On the vector representation of induced matroids, Bull

    B. Lindstr¨ om, On the vector representation of induced matroids, Bull. London Math. Soc. 5 (1973) 85–90

    1973

  4. [12]

    Postnikov, Total positivity, Grassmannians, and ne tworks, arXiv:math.CO/0609764, 2006

    A. Postnikov, Total positivity, Grassmannians, and ne tworks, arXiv:math.CO/0609764, 2006

    2006

  5. [13]

    Skandera, Inequalities in products of minors of tota lly nonnegative matrices, J

    M. Skandera, Inequalities in products of minors of tota lly nonnegative matrices, J. Algebraic Comb. 20 (2004) 195–211

    2004

  6. [14]

    Soskin and P.K

    D. Soskin and P.K. Vishwakarma, Pl¨ ucker inequalities for weakly separated coordinates in totally nonnegative Grassmannian, arXiv:2310.12916v3[math.CO], 2024. 14

    2024 arXiv

Pith tools

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