pith. sign in

arxiv: 1906.12312 · v1 · pith:GCLSJ7SAnew · submitted 2019-06-28 · 🧮 math.CO

Two nondeterministic positive definiteness tests for unidiagonal integral matrices

Andrzej Mr\'oz This is my paper

Pith reviewed 2026-05-25 13:27 UTC · model grok-4.3

classification 🧮 math.CO
keywords positive definitenessunidiagonal integral matrixedge-bipartite graphinflation transformationquadratic formnondeterministic algorithmLas Vegas algorithm
0
0 comments X

The pith

Inflation operations on the bigraph of a unidiagonal integral matrix decide its positive definiteness.

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

The paper introduces two algorithms that test whether a unidiagonal integral matrix is positive definite by working on its associated edge-bipartite graph. The methods apply sequences of edge transformations called inflations, making the positive definite case the optimistic one with lower average effort. Worst-case running times are O(n^3) and O(n^4), and randomized Las Vegas versions come with explicit step bounds. The same process also extracts extra structural information about the quadratic form attached to the matrix. These procedures are presented as practical alternatives that often run faster than classical tests based on Sylvester's criterion.

Core claim

Two algorithms are presented that associate an unidiagonal integral matrix A with its edge-bipartite graph Δ(A) and apply inflation transformations to Δ(A). The transformations preserve positive definiteness in both directions, so the process either reaches a configuration that certifies positive definiteness or encounters an obstruction that rules it out. Variants include deterministic procedures of complexities O(n^3) and O(n^4) together with Las Vegas randomized versions whose maximum step counts are stated explicitly.

What carries the argument

Inflation transformations performed on the edge-bipartite graph Δ(A) associated with the unidiagonal integral matrix A.

If this is right

  • Positive definiteness verification becomes the optimistic case rather than the pessimistic one.
  • The testing procedure simultaneously yields information about the quadratic form q_A beyond a yes-or-no answer.
  • Las Vegas randomized variants terminate after a precisely bounded number of steps.
  • The methods illustrate an application of symbolic graph techniques to matrix problems with scope for further matrix-theoretic uses.

Where Pith is reading between the lines

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

  • The same bigraph-inflation framework could be adapted to test negative definiteness or semidefiniteness by changing the target configurations.
  • Extending the construction beyond unidiagonal matrices would require only local adjustments to the initial bigraph definition.
  • Practical implementations may yield speed advantages for quadratic-form computations in integer programming or lattice problems.

Load-bearing premise

The inflation operations on the bigraph preserve the positive definiteness property of the matrix in both directions without false positives or negatives.

What would settle it

An explicit unidiagonal integral matrix A for which the inflation process either accepts a matrix that is not positive definite or rejects one that is.

read the original abstract

For standard algorithms verifying positive definiteness of a matrix $A\in\mathbb{M}_n(\mathbb{R})$ based on Sylvester's criterion, the computationally pessimistic case is this when $A$ is positive definite. We present two algorithms realizing the same task for $A\in\mathbb{M}_n(\mathbb{Z})$, for which the case when $A$ is positive definite is the optimistic one. The algorithms have pessimistic computational complexities $\mathcal{O}(n^3)$ and $\mathcal{O}(n^4)$ and they rely on performing certain edge transformations, called inflations, on the edge-bipartite graph (=bigraph) $\Delta=\Delta(A)$ associated with $A$. We provide few variants of the algorithms, including Las Vegas type randomized ones with precisely described maximal number of steps. The algorithms work very well in practice, in many cases with a better speed than the standard tests. Moreover, the algorithms yield some additional information on the properties on the quadratic form $q_A:\mathbb{Z}^n\to\mathbb{Z}$ associated with a matrix $A$. On the other hand, our results provide an interesting example of an application of symbolic computing methods originally developed for different purposes, with a big potential for further generalizations in matrix problems. This is an extended version of the article [A. Mr\'oz, Effective nondeterministic positive definiteness test for unidiagonal integral matrices, Proceedings SYNASC 2016, IEEE Computer Society CPS (2016), 65-71] in which we discussed the algorithm of the complexity $\mathcal{O}(n^4)$.

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 / 2 minor

Summary. The manuscript presents two algorithms for testing positive definiteness of unidiagonal integral matrices A in M_n(Z). The algorithms rely on performing inflation transformations on the associated edge-bipartite graph Δ(A), with pessimistic complexities O(n^3) and O(n^4). Variants include Las Vegas randomized algorithms with explicitly bounded steps. The methods are claimed to outperform standard Sylvester-based tests in practice for the positive definite case (treated as optimistic) and to yield additional information on the quadratic form q_A. The work is positioned as an application of symbolic computing techniques.

Significance. If the core preservation property under the matrix-to-bigraph association and inflations holds, the paper supplies practical, graph-based alternatives to classical definiteness tests for this matrix class, with the positive definite case being computationally favorable. The explicit bounds on randomized variants and the extraction of quadratic form data are strengths. It illustrates a cross-domain transfer of symbolic methods with potential for further matrix problems.

minor comments (2)
  1. Abstract: 'few variants' should read 'a few variants' for grammatical precision.
  2. The extended version note references the 2016 SYNASC paper; ensure the current manuscript explicitly states which new results (e.g., the O(n^3) algorithm) are original to this version.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper describes two algorithms for positive definiteness testing of unidiagonal integral matrices via inflations on the associated edge-bipartite graph Δ(A). The core correctness claim rests on the matrix-bigraph association and the bidirectional preservation of definiteness under inflations, which the text presents as an application of independently developed symbolic-computing techniques rather than a derivation from fitted parameters or prior self-citations. The single self-citation is to the author's own 2016 conference version of the O(n^4) algorithm and functions only as an extension note, not as load-bearing justification for the method or its complexity claims. No equations, uniqueness theorems, or ansatzes are shown to reduce the result to its own inputs by construction. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the unstated but load-bearing assumption that the bigraph model plus inflation operations decide positive definiteness for unidiagonal integral matrices; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption The edge-bipartite graph Δ(A) associated with a unidiagonal integral matrix A encodes positive definiteness such that a finite sequence of inflations decides the property.
    This modeling assumption is invoked to justify both the correctness and the complexity claims.

pith-pipeline@v0.9.0 · 5809 in / 1251 out tokens · 35083 ms · 2026-05-25T13:27:53.128353+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

32 extracted references · 32 canonical work pages

  1. [1]

    Barot and J

    M. Barot and J. A. de la Pe ˜ na, The Dynkin type of a non-nega tive unit form, Expo. Math. , 17 (1999), 339–348

    work page 1999

  2. [2]

    Dowbor, H

    P . Dowbor, H. Meltzer and A. Mr´ oz, Parametrizations for integral slope homogeneous modules over tubular canonical algebras , Algebr . Represent. Theory (2014) 17:321–356

    work page 2014

  3. [3]

    Dowbor, H

    P . Dowbor, H. Meltzer and A. Mr´ oz, An algorithm for the co nstruction of parametrizing bimodules for homogeneous modules over tu bular canonical algebras, Algebr . Represent. Theory (2014), 17:357–405

    work page 2014

  4. [4]

    Dowbor, A

    P . Dowbor, A. Mr´ oz, The multiplicity problem for indeco mposable decompositions of modules over domestic canonical algebra s, Collo- quium Mathematicum 111 (2008), 221–282

    work page 2008

  5. [5]

    Dowbor, A

    P . Dowbor, A. Mr´ oz, On a separation of orbits in the module variety for domestic canonical algebras, Colloquium Mathematicum 111 (2008), 283–295

    work page 2008

  6. [6]

    Dowbor and A

    P . Dowbor and A. Mr´ oz, On the normal forms of modules with respect to parametrizing bimodules, J. Algebra 402 (2014) 219–257

    work page 2014

  7. [7]

    Dr¨ axler, Y u

    P . Dr¨ axler, Y u. A. Drozd, N. S. Golovachtchuk, S. A. Ovsi enko, M. Zeldych, Towards the classification of sincere weakly posit ive unit forms, Europ. J. Combinat. 16 (1995), 1–16

    work page 1995

  8. [8]

    Ga ¸siorek, D

    M. Ga ¸siorek, D. Simson and K. Zaja ¸c, A Gram classificati on of non- negative corank-two loop-free edge-bipartite graphs, Linear Algebra Appl. 500 (2016), 88–118

    work page 2016

  9. [9]

    Grzecza, S

    M. Grzecza, S. Kasjan, A. Mr´ oz, Tree matrices and a matri x reduction algorithm of Belitskii, Fund. Inform. 118 (2012), 253–279

    work page 2012

  10. [10]

    Kasjan and A

    S. Kasjan and A. Mr´ oz, Experiences in symbolic computa tions for matrix problems, 14th International Symposium on Symbolic and Nu- meric Algorithms for Scientic Computing (SYNASC 2012), Proceedings SYNASC 2012, IEEE Computer Society (2012), 39–44

    work page 2012

  11. [11]

    Kasjan and D

    S. Kasjan and D. Simson, Mesh algorithms for Coxeter spe ctral classification of Cox-regular edge-bipartite graphs with l oops, I. Mesh root systems, Fund. Inform. 139 (2015), 153–184

    work page 2015

  12. [12]

    Kasjan and D

    S. Kasjan and D. Simson, Mesh algorithms for Coxeter spe ctral classi- fication of Cox-regular edge-bipartite graphs with loops, I I. Application to Coxeter spectral analysis, Fund. Inform. 139 (2015), 185–209

    work page 2015

  13. [13]

    Kasjan and D

    S. Kasjan and D. Simson, Algorithms for isotropy groups of Cox- regular edge-bipartite graphs, Fund. Inform. 139 (2015), 249–275

    work page 2015

  14. [14]

    Kosakowska, Inflation algorithms for positive and pr incipal edge- bipartite graphs and unit quadratic forms, Fund

    J. Kosakowska, Inflation algorithms for positive and pr incipal edge- bipartite graphs and unit quadratic forms, Fund. Inform. 119 (2012), 149–162

    work page 2012

  15. [15]

    Makuracki, A

    B. Makuracki, A. Mr´ oz, Root systems and inflations of no n-negative quasi-Cartan matrices, Linear Algebra Appl. 580 (2019), 128–165 https://doi.org/10.1016/j.laa.2019.06.006

    work page doi:10.1016/j.laa.2019.06.006 2019

  16. [16]

    Makuracki, A

    B. Makuracki, A. Mr´ oz, Quadratic algorithms to comput e the Dynkin type of positive and principal quasi-Cartan matrices, (201 9), to appear

    work page

  17. [17]

    C. D. Meyer, Matrix Analysis and Applied Linear Algebra , Philadel- phia, SIAM (2000)

    work page 2000

  18. [18]

    Mr´ oz, Coxeter energy of graphs, Linear Algebra Appl

    A. Mr´ oz, Coxeter energy of graphs, Linear Algebra Appl. 506 (2016), 279–307

    work page 2016

  19. [19]

    Mr´ oz, Congruences of edge-bipartite graphs with ap plications to Grothendieck group recognition I

    A. Mr´ oz, Congruences of edge-bipartite graphs with ap plications to Grothendieck group recognition I. Inflation algorithm revi sited, Fund. Inform. 146 (2016), 121–144

    work page 2016

  20. [20]

    Mr´ oz, Congruences of edge-bipartite graphs with ap plications to Grothendieck group recognition II

    A. Mr´ oz, Congruences of edge-bipartite graphs with ap plications to Grothendieck group recognition II. Coxeter type study, Fund. Inform. 146 (2016), 145–177

    work page 2016

  21. [21]

    A. Mr´ oz, Effective nondeterministic positive definit eness test for unidiagonal integral matrices, 18th International Symposium on Sym- bolic and Numeric Algorithms for Scientific Computing (Timisoara, Romania, 24-27 September 2016 ), Proceedings SYNASC 2016, IEEE Computer Society CPS (2016), 65–71

    work page 2016

  22. [22]

    Mr´ oz and J

    A. Mr´ oz and J. A. de la Pe ˜ na, Tubes in derived categorie s and cyclotomic factors of the Coxeter polynomial of an algebra, J. Algebra 420 (2014) 242–260

    work page 2014

  23. [23]

    Mr´ oz and J

    A. Mr´ oz and J. A. de la Pe ˜ na, Periodicity in bilinear la ttices and the Coxeter formalism, Linear Algebra Appl. 493 (2016), 227–260

    work page 2016

  24. [24]

    S. A. Ovsienko, Integral weakly positive forms, in Schu r matrix problems and quadratic forms, preprint 78.25, Inst. Mat. Ak ad. Nauk USSR, Kiev 1978, 3–17 (in Russian)

    work page 1978

  25. [25]

    P´ erez, M

    C. P´ erez, M. Abarca, D. Rivera, Cubic algorithm to comp ute the Dynkin type of a positive definite quasi-Cartan matrix, Fund. Inform. 158 (2018), 369-384

    work page 2018

  26. [26]

    C. M. Ringel, Tame algebras and integral quadratic forms , Lecture Notes in Math., 1099, Springer, Berlin, 1984

    work page 1984

  27. [27]

    Simson, A Coxeter-Gram classification of positive si mply laced edge-bipartite graphs, SIAM J

    D. Simson, A Coxeter-Gram classification of positive si mply laced edge-bipartite graphs, SIAM J. Discrete Math. , 27 (2013), 827–854

    work page 2013

  28. [28]

    Simson, Symbolic algorithms computing Gram congrue nces in the Coxeter spectral classification of edge-bipartite grap hs, I

    D. Simson, Symbolic algorithms computing Gram congrue nces in the Coxeter spectral classification of edge-bipartite grap hs, I. A Gram classification, Fund. Inform. 145 (2016), 19–48

    work page 2016

  29. [29]

    Simson, Symbolic algorithms computing Gram congrue nces in the Coxeter spectral classification of edge-bipartite grap hs, II

    D. Simson, Symbolic algorithms computing Gram congrue nces in the Coxeter spectral classification of edge-bipartite grap hs, II. Isotropy mini-groups, Fund. Inform. 145 (2016), 49–80

    work page 2016

  30. [30]

    Zaja ¸c, Numeric algorithms for corank-two edge-bip artite graphs and their mesh geometries of roots, Fund

    K. Zaja ¸c, Numeric algorithms for corank-two edge-bip artite graphs and their mesh geometries of roots, Fund. Inform. 152 (2017), 185– 222

    work page 2017

  31. [31]

    Mr´ oz, Bigraph Congruences , Maple packages (2015-2019), http://www.mat.umk.pl/∼amroz/projects/BigraphCongruences.zip

    A. Mr´ oz, Bigraph Congruences , Maple packages (2015-2019), http://www.mat.umk.pl/∼amroz/projects/BigraphCongruences.zip

    work page 2015

  32. [32]

    Mr´ oz, homepage, http://www.mat.umk.pl/ ∼amroz/projen.html

    A. Mr´ oz, homepage, http://www.mat.umk.pl/ ∼amroz/projen.html

    work page