Pith. sign in

REVIEW 4 minor 37 references

Polynomial Matrices in Integer Programming With Restricted Subdeterminants

T0 review · 0 major / 4 minor · reviewed 2026-07-13 · grok-4.5

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

Pith's one-line read Integer programs whose constraint matrices have subdeterminants from nine linear polynomials can be recognized and solved in polynomial time.

desk verdict Clean, self-contained poly-time recognition and optimization for a natural parametric family that sits strictly between TU and bimodular matrices. read the letter →

arxiv 2607.08935 v1 pith:YLP6YHRT submitted 2026-07-09 math.OC math.CO

Marcel Celaya , Stefan Kuhlmann , Robert Weismantel This is my paper · ORCID
classification math.OCmath.CO MSC 90C1015A1505B3590C2715B36
keywords integerprogrammingsubdeterminantstotallyunimodularmatricesbimodularpolynomialmatroidsrecognitionproblemoptimization
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 develops a framework for integer linear programs whose constraint matrices have polynomial entries in one variable and whose subdeterminants are restricted to a fixed finite set S of polynomials. For the concrete choice S consisting of the nine linear forms ±{0,1,x,x+1,2x+1}, it proves that total S-modularity can be decided in polynomial time and that the associated integer programs, after evaluation at almost every integer, can likewise be solved in polynomial time. The same matrices arise naturally as projections of bimodular matrices that admit two distinct unimodular projections, giving a clean structural description that sits between ordinary unimodular matrices and general bimodular matrices. The results therefore enlarge the short list of families of integer programs known to be tractable while remaining beyond total unimodularity, and they supply a systematic route for studying other restricted-subdeterminant families by working over the polynomial ring.

What carries the argument

The modified matrix-determinant lemma for rank-1 updates: any candidate matrix decomposes as M=M(0)+xuv⊤, so every subdeterminant is completely determined by the two evaluations M(0) and M(-1); total S-modularity therefore reduces to ordinary total unimodularity of those two matrices.

What would settle it

Produce an explicit matrix M=M(0)+xuv⊤ over Z[x] for which both M(0) and M(-1) are totally unimodular, yet some square submatrix of M has a determinant outside ±{0,1,x,x+1,2x+1}; or exhibit a full-column-rank evaluation M(a) whose integer program cannot be solved by the bimodular algorithm after the reduction of Section 7.

Watch

Extended reading notes

Core claim

For the set S=±{0,1,x,x+1,2x+1}, a matrix M over Z[x] is totally S-modular if and only if the two integer matrices obtained by evaluating M at 0 and at -1 are both totally unimodular. Consequently both the recognition of total S-modularity and the solution of the integer program with constraint matrix M(a) (a any integer that preserves full column rank) can be performed in polynomial time.

Load-bearing premise

The final reduction of the optimization problem to a bimodular integer program relies on an existing black-box polynomial-time algorithm for bimodular IPs; if that algorithm fails for the particular bimodular matrices produced by the rank-1 update, the claimed poly-time bound collapses.

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

0 major / 4 minor

Summary. The paper develops a framework for integer programs whose constraint matrices have polynomial entries in one variable and whose subdeterminants lie in a prescribed finite set S of polynomials. For the concrete set S = ±{0,1,x,x+1,2x+1} it proves that total S-modularity can be recognized in polynomial time (Theorem 1) by reducing the question to total unimodularity of the two evaluations M(0) and M(-1) (Lemma 15). It further shows that the associated integer programs ILP(M(a),b,c) can be solved in polynomial time for every integer a at which M(a) has full column rank (Theorem 2), by a rank-1 reduction that produces only ordinary bimodular matrices. Supporting results include an explicit description of the finite exceptional set I(S) of evaluation points at which the map M o M(a) fails to be bijective (Theorem 3 and Section 5.3), analogous recognition statements for the smaller sets ±{0,1,x} and ±{0,1,x,x+1}, and a structural characterization of S-modular matrices as projections of bimodular matrices that admit two distinct unimodular projections (Theorem 4).

Significance. The work supplies the first systematic polynomial-time recognition and optimization results for a non-constant family of restricted-subdeterminant matrices that properly contains the totally unimodular and bimodular cases. The characterizations rest only on classical determinant identities (Desnanot–Jacobi, matrix-determinant lemma, Grassmann–Plücker) together with the already-available strongly polynomial oracles for total unimodularity and bimodular IP; the reduction therefore inherits the same complexity guarantees without additional assumptions. The explicit computation of the exceptional set I(S) and the projection representation of Theorem 4 give concrete structural insight that can be reused for larger sets of linear forms. The paper is a natural and carefully executed extension of the authors’ IPCO 2024 abstract, adding the full recognition theory, the enlarged set S, and the bimodular-projection correspondence.

minor comments (4)
  1. Section 5.3 and the proof of Lemma 14 rely on a computer enumeration of low-degree solutions of the Desnanot–Jacobi identity. A short appendix listing the feasible polynomials (or a reproducible SageMath snippet) would make the claim fully self-contained.
  2. In the proof of Lemma 20 the proximity interval (6) is written with Δ_n(M(0)v); a one-line reminder that this quantity is at most 2 (by Lemma 19) would clarify why only O(n) candidate values of y need be examined.
  3. Figure 1 is referenced in Section 9 but never appears in the manuscript; either insert the figure or remove the reference.
  4. A few typographical slips remain (e.g., “stuying” on p. 13, “Desnanont” for Desnanot, “dimen-sion”). A final proof-reading pass would eliminate them.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: characterizations and reductions rest on elementary identities and external oracles

full rationale

The paper's central claims (Theorems 1–2, Corollaries 1–2, Theorem 4) are derived from classical determinant identities (Desnanot–Jacobi / Lemma 1, matrix-determinant lemma / Lemma 5, 3-term Grassmann–Plücker / Lemma 3) together with two external, published oracles: polynomial-time recognition of totally unimodular matrices and the Artmann–Weismantel–Zenklusen strongly polynomial algorithm for bimodular IPs. Lemma 15 characterises total S-modularity exactly by the total unimodularity of the two evaluations M(0) and M(−1); the subsequent reduction of ILP(M(a),b,c) produces ordinary bimodular matrices to which the known oracle applies without restriction. No quantity is defined in terms of a fitted parameter later recovered as a prediction, no uniqueness theorem is imported from the authors’ own prior work as an external fact, and the self-citations to the IPCO extended abstract merely record which statements are new versus which already appeared. The derivation chain is therefore self-contained once the classical oracles are granted.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper rests entirely on standard linear-algebra identities over Z[x] and on two classical algorithmic black boxes (TU recognition and bimodular IP). No free parameters are fitted; the set S is chosen by a transparent geometric maximality argument rather than by data. The only invented notions are the technical sets F(S) and I(S), which are defined by explicit finite enumeration and therefore carry independent evidence.

assumptions (4)
  • standard math Total unimodularity of an integer matrix can be decided in polynomial time (Seymour’s decomposition / Schrijver’s algorithm).
    Invoked throughout Section 6 to obtain the recognition algorithms.
  • standard math Integer linear programs whose constraint matrix is bimodular (all subdeterminants in {0,±1,±2}) can be solved in strongly polynomial time.
    Cited as [7] and used as a black box in the proof of Theorem 2 (Section 7).
  • standard math The Desnanot–Jacobi identity and the 3-term Grassmann–Plücker relations hold over any commutative ring.
    Lemmas 1 and 3; used to bound forbidden determinants and to prove the projection inequalities.
  • domain assumption S consists only of linear forms, is closed under negation, and contains no element twice another element.
    Stated at the beginning of Section 2; restricts the class of sets for which the framework is developed.
invented entities (1)
  • Forbidden-submatrix set F(S) and exceptional evaluation set I(S) independent evidence
    purpose: To characterize precisely those integers a for which evaluation fails to be bijective between totally S-modular and totally S(a)-modular matrices.
    Defined by finite enumeration via the Desnanot–Jacobi identity; the sets are computable and therefore possess independent evidence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polynomial Matrices in Integer Programming With Restricted Subdeterminants." pith.science (2026). https://pith.science/paper/YLP6YHRT

@misc{pith2026260708935,
  author       = {Pith},
  title        = {Pith review of: Polynomial Matrices in Integer Programming With Restricted Subdeterminants},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YLP6YHRT}},
  note         = {Machine review of arXiv:2607.08935}
}
abstract

We introduce a framework for tackling questions in discrete optimization associated with parametric constraint matrices. More precisely, the constraint matrices have entries that are polynomials in one variable and all subdeterminants of these matrices are polynomials in a given prescribed set $S$. Two key problems arise in this context. The first is the recognition problem: can a matrix of this form be recognized in polynomial time? The second is the optimization problem: given an integer program whose constraint matrix is of this form, can it be solved in polynomial time? We answer both questions affirmatively for a particular set $S$ consisting of nine linear forms. The matrices we consider are of themselves independent interest; they arise as matrix projections of certain bimodular matrices that admit two distinct unimodular projections.

Figures

Figures reproduced from arXiv: 2607.08935 by the authors.

Figure 1
Figure 1. The blue boxes depict the value x and the green boxes x + 1 or vice-versa. The first row of matrices corresponds to the first five elements of an infinite sequence of matrices that can be obtained by generalizing the diamond pattern with dimen￾sion congruent to 3 and 5 modulo 8. It can be shown that those infinitely many matrices are forbidden submatrices for ±{0, 1, x, x + 1, 2x + 1}.The matrices in the last row co… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 1 linked inside Pith

  1. [1]

    Aliev, G

    I. Aliev, G. Averkov, J. A. De Loera, and T. Oertel. Sparse representation of vectorsinlatticesandsemigroups.MathematicalProgrammingSeriesB,192:519– 546, 2022

    2022

  2. [2]

    Aliev, J

    I. Aliev, J. A. De Loera, F. Eisenbrand, T. Oertel, and R. Weismantel. The sup- port of integer optimal solutions.SIAM Journal on Optimization, 28(3):2152– 2157, 2018

    2018

  3. [3]

    Aliev, M

    I. Aliev, M. Henk, and T. Oertel. Distances to lattice points in knapsack poly- hedra.Mathematical Programming, 182:175–198, 2020. 26

    2020

  4. [4]

    Aliev, J

    I. Aliev, J. A. De Loera, T. Oertel, and C. O’Neill. Sparse solutions of linear diophantine equations.SIAM Journal on Applied Algebra and Geometry, 1:239– 253, 2017

    2017

  5. [5]

    Integerprogramswithnearlytotallyunimodularmatrices: thecographic case

    M.Aprile,S.Fiorini,G.Joret,S.Kober,M.T.Seweryn,S.Weltge,andY.Yudit- sky. Integerprogramswithnearlytotallyunimodularmatrices: thecographic case. InProceedingsoftheAnnualACM-SIAMSymposiumonDiscreteAlgorithms (SODA), pages 2301–2312, 2025

    2025

  6. [6]

    Anoteonnon-degenerateintegerprogramswithsmallsub-determinants

    S.Artmann,F.Eisenbrand,C.Glanzer,T.Oertel,S.Vempala,andR.Weisman- tel. Anoteonnon-degenerateintegerprogramswithsmallsub-determinants. Operations Research Letters, 44(5):635–639, 2016

    2016

  7. [7]

    Artmann, R

    S. Artmann, R. Weismantel, and R. Zenklusen. A strongly polynomial algo- rithmforbimodularintegerlinearprogramming. InProceedingsofthe49thAn- nual ACM SIGACT Symposium on Theory of Computing, pages 1206–1219, 2017

    2017

  8. [8]

    Averkov and M

    G. Averkov and M. Schymura. On the maximal number of columns of a∆- modularintegermatrix: boundsandcomputations.MathematicalProgramming Series B, 206:61–89, 2024

    2024

Show all 37 references
  1. [9]

    Cam- bridge University Press, Cambridge, 2nd edition, 1999

    A.Björner,M.LasVergnas,B.Sturmfels,N.White,andG.M.Ziegler.Oriented Matroids, volume 46 ofEncyclopedia of Mathematics and its Applications. Cam- bridge University Press, Cambridge, 2nd edition, 1999

    1999

  2. [10]

    Bonifas, M

    N. Bonifas, M. Di Summa, F. Eisenbrand, N. Hähnle, and M. Niemeier. On sub-determinants and the diameter of polyhedra.Discrete and Computational Geometry, 52:102–115, 2014

    2014

  3. [11]

    Celaya, S

    M. Celaya, S. Kuhlmann, J. Paat, and R. Weismantel. Proximity and flatness bounds for linear integer optimization.Mathematics of Operations Research, 49(4):2446–2467, 2023

    2023

  4. [12]

    Celaya, S

    M. Celaya, S. Kuhlmann, and R. Weismantel. On matrices over a polynomial ring with restricted subdeterminants. In Jens Vygen and Jarosław Byrka, ed- itors,Integer Programming and Combinatorial Optimization, pages 43–56, Cham,

  5. [13]

    Springer Nature Switzerland

  6. [14]

    W. Cook, A. M. H. Gerards, A. Schrijver, and É. Tardos. Sensitivity theorems in integer linear programming.Mathematical Programming, 34:251–264, 1986

    1986

  7. [15]

    Onpadberg’sconjectureaboutalmosttotally unimodular matrices.Operations Research Letters, 27(3):97–99, 2000

    G.CornuéjolsandL.F.Zuluaga. Onpadberg’sconjectureaboutalmosttotally unimodular matrices.Operations Research Letters, 27(3):97–99, 2000

    2000

  8. [16]

    Dadush and N

    D. Dadush and N. Hähnle. On the shadow simplex method for curved poly- hedra.Discrete & Computational Geometry, 56(4):882–909, 2016. 27

    2016

  9. [17]

    Integerprogramswithbounded subdeterminants and two nonzeros per row.Journal of the ACM, 72(1), 2025

    S.Fiorini,G.Joret,S.Weltge,andY.Yuditsky. Integerprogramswithbounded subdeterminants and two nonzeros per row.Journal of the ACM, 72(1), 2025

    2025

  10. [18]

    Geelen, P

    J. Geelen, P. Nelson, and Z. Walsh. Excluding a line from complex- representable matroids.Memoirs of the American Mathematical Society, 303(1523), 2024

    2024

  11. [19]

    Glanzer, I

    C. Glanzer, I. Stallknecht, and R. Weismantel. Notes on{a, b, c}-modular ma- trices.Vietnam Journal of Mathematics, 50(2):469–485, 2022

    2022

  12. [20]

    Gribanov, I

    D. Gribanov, I. Shumilov, D. Malyshev, and P. Pardalos. On∆-modular inte- ger linear problems in the canonical form and equivalent problems.Journal of Global Optimization, 88(3):591–651, 2024

    2024

  13. [21]

    Integralboundarypointsofconvexpolyhedra

    A.J.HoffmanandJ.B.Kruskal. Integralboundarypointsofconvexpolyhedra. Linear Inequalities and Related Systems (H.W. Kuhn and A.J. Tucker, eds.), pages 223–246, 1956

    1956

  14. [22]

    S. Kober. Totally∆-modular IPs with two non-zeros in most rows. In N. Megow and A. Basu, editors,Integer Programming and Combinatorial Opti- mization, pages 355–370. Springer Nature Switzerland, 2025

    2025

  15. [23]

    InSantanuS.Dey,MarcoDiSumma, and Domenico Salvagnin, editors,Integer Programming and Combinatorial Opti- mization, pages 188–203

    S.KuhlmannandR.Weismantel.Athresholdphenomenonfortheshortestlat- ticevectorproblemintheinfinitynorm. InSantanuS.Dey,MarcoDiSumma, and Domenico Salvagnin, editors,Integer Programming and Combinatorial Opti- mization, pages 188–203. Springer Nature Switzerland, 2026

    2026

  16. [24]

    Lang.Algebra

    S. Lang.Algebra. Graduate Texts in Mathematics. Springer New York, 2005

    2005

  17. [25]

    J. Lee, J. Paat, I. Stallknecht, and L. Xu. Improving proximity bounds us- ing sparsity. InCombinatorial Optimization: 6th International Symposium ISCO, pages 115–127, 2020

    2020

  18. [26]

    Nägele, C

    M. Nägele, C. Nöbel, R. Santiago, and R. Zenklusen. Advances on strictly∆- Modular IPs.Mathematical Programming Series B, 210:731–760, 2025

    2025

  19. [27]

    Nägele, R

    M. Nägele, R. Santiago, and R. Zenklusen. Congruency-constrained TU problems beyond the bimodular case.Mathematics of Operations Research, 49(3):1303–1348, 2023

    2023

  20. [28]

    Narayanan, R

    H. Narayanan, R. Shah, and N. Srivastava. A spectral approach to polytope diameter.Discrete & Computational Geometry, 72(4):1647–1674, 2024

    2024

  21. [29]

    Oxley.Matroid Theory

    J. Oxley.Matroid Theory. Oxford Graduate Texts in Mathematics. Oxford Uni- versity Press, Oxford, 2nd edition, 2011

    2011

  22. [30]

    Oxley and Z

    J. Oxley and Z. Walsh. 2-modular matrices.SIAM Journal on Discrete Mathe- matics, 36(2):1231–1248, 2022. 28

    2022

  23. [31]

    Onthecolumnnumberandforbid- den submatrices for∆-modular matrices.SIAM Journal on Discrete Mathemat- ics, 38(1):1–18, 2024

    J.Paat,I.Stallknecht,L.Xu,andZ.Walsh. Onthecolumnnumberandforbid- den submatrices for∆-modular matrices.SIAM Journal on Discrete Mathemat- ics, 38(1):1–18, 2024

    2024

  24. [32]

    Totalpositivity,Grassmannians,andnetworks.https://arxiv

    A.Postnikov. Totalpositivity,Grassmannians,andnetworks.https://arxiv. org/abs/math/0609764, 2006

    2006 arXiv

  25. [33]

    Graphminors.XX.Wagner’sconjecture.Jour- nal of Combinatorial Theory, Series B, 92(2):325–357, 2004

    N.RobertsonandP.D.Seymour. Graphminors.XX.Wagner’sconjecture.Jour- nal of Combinatorial Theory, Series B, 92(2):325–357, 2004. Special Issue Dedi- cated to Professor W.T. Tutte

    2004

  26. [34]

    Schrijver.Theory of Linear and Integer Programming

    A. Schrijver.Theory of Linear and Integer Programming. Wiley, 1986

    1986

  27. [35]

    Decomposition of regular matroids.Journal of Combinatorial Theory, Series B, 28(3):305–359, 1980

    P.D Seymour. Decomposition of regular matroids.Journal of Combinatorial Theory, Series B, 28(3):305–359, 1980

    1980

  28. [36]

    J.J.Sylvester.Ontherelationbetweentheminordeterminantsoflinearlyequiv- alentquadraticfunctions.TheLondon,Edinburgh,andDublinPhilosophicalMag- azine and Journal of Science, 1(4):295–305, 1851

  29. [37]

    S. I. Veselov and A. J. Chirkov. Integer program with bimodular matrix.Dis- crete Optimization, 6:220–222, 2009. 29

    2009

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.