arxiv: 2605.02314 · v1 · submitted 2026-05-04 · 🧮 math.CO · math.SP

Recognition: 2 theorem links

· Lean Theorem

A characterization for positive semi-definite matrix products

Frederik Garbe , Fan Wei

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:16 UTC · model grok-4.3

classification 🧮 math.CO math.SP

keywords matrix productspositive semi-definiteeigenvaluesgraph theorydecidabilitysymbolic productstransposes

0 comments

The pith

A symbolic product of matrices and transposes has only non-negative eigenvalues for every assignment exactly when its associated graph satisfies the positive condition.

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

The paper investigates when a product of matrices and their transposes, given symbolically, will always result in a matrix with non-negative real eigenvalues no matter how the matrices are chosen. It proves that this property is decidable by reducing the question to a condition on an associated graph from the positive graph conjecture. This matters to a reader because it provides a concrete way to check the property for any given product pattern without needing to search over all possible matrix sizes and entries. The characterization turns an apparently analytic question into a combinatorial one.

Core claim

For any symbolic product of fixed length consisting of matrix variables and their transposes, the product matrix always has only non-negative real eigenvalues under every real matrix assignment if and only if the corresponding graph in the positive graph conjecture sense has the positive property.

What carries the argument

The reduction that associates each symbolic matrix product to a graph such that the eigenvalue property holds for all matrix assignments precisely when the graph is positive, and this equivalence is both sound and complete.

If this is right

The decision problem of whether a given symbolic product always yields non-negative eigenvalues is algorithmically solvable.
The property depends only on the pattern of variables and transposes, independent of the specific matrix dimensions or values.
This provides a matrix version of the positive graph conjecture through the established equivalence.
Products that satisfy the condition, like A transpose A, are guaranteed to be positive semi-definite in the eigenvalue sense for any choice of A.

Where Pith is reading between the lines

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

If the positive graph conjecture turns out to be true in graph theory, the matrix version would inherit a simple explicit characterization.
The approach might apply to other questions about eigenvalues of matrix products or similar algebraic identities.
Testing the condition on small graphs could yield new examples of matrix products with the desired property or counterexamples.

Load-bearing premise

The equivalence between the matrix eigenvalue condition and the graph positivity condition holds for products of any fixed length.

What would settle it

A counterexample would be a symbolic product where the associated graph is positive but some matrix assignment produces a product with a negative eigenvalue, or the reverse.

Figures

Figures reproduced from arXiv: 2605.02314 by Fan Wei, Frederik Garbe.

**Figure 1.** Figure 1: The symmetry of our auxiliary graph for a positive semi-definite symbolic matrix product. view at source ↗

**Figure 2.** Figure 2: The construction of G2 (F1, F2, F3, F4). Proof. Let H be an edge-weighted graph with vertex set [n]. For every i ∈ [ℓ] we define matrices Si , ST i ∈ R n×n by setting for every x, y ∈ [n] Si(x, y) := X φ∈Hom(Fi,H) φ(ai)=x,φ(bi)=y wφ and S T i (x, y) := X φ∈Hom(Fi,H) φ(ai)=y,φ(bi)=x wφ . Similarly, define S sym i (x, y) := X φ∈Hom(F sym i ,H) φ(ai)=x,φ(bi)=y wφ and note that S sym i (x, y) = S sym i (y, x) … view at source ↗

**Figure 3.** Figure 3: The sun graph G(F, 2k, ℓ) with k = 2, ℓ = 2, and rigid F. Since M is a rotation matrix with angle θ the eigenvalues are e ±iπ/(2k) and therefore tr(M2k ) = (e iπ/(2k) ) 2k + (e −iπ/(2k) ) 2k = −2 . (4) Let D be the edge-weighted digraph with loops whose adjacency matrix is M. In particular D has two vertices and has two (weighted) self-loops. Furthermore, we denote by F(a,b),ℓ = (F,(a, b)) + Pℓ the graph w… view at source ↗

**Figure 4.** Figure 4: The graph H after the edges of D are replaced by copies of F + Pℓ and F is possibly symmetric in a and b. It contains 4 copies of F, denoted by F x,y and each followed by a path of length ℓ denoted by P x,y . Suppose that φ(V (F)) ∩ V (F x,1 ) \ {x} ̸= ∅ and φ(V (F)) ∩ V (F x,2 ) \ {x} ̸= ∅. Then φ −1 (x) is a vertex cut of F, but, since F is connected and has no cut vertex, it follows that |φ −1 (x)| ≥ 2.… view at source ↗

read the original abstract

A well-known fact in linear algebra is that $A^T A$ is always positive semi-definite for any real matrix $A$. We consider a generalization of this fact via the following decision problem. Given a symbolic product of length $k$, consisting of $\ell$ variables and their transposes, such as $ABB^TCA^T$, does there exist an $n\in\mathbb N$ and an assignment of matrices from $\mathbb R^{n\times n}$ such that the resulting matrix product has a negative eigenvalue? We show that this problem is decidable and provide a simple characterization of those symbolic products that have only non-negative real eigenvalues for any assignment of matrices. This characterization can also be understood as a matrix analogue of the positive graph conjecture by Camarena, Cs\'oka, Hubai, Lippner, and Lov\'asz, and the proof relies on this surprising connection to graph theory.

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.

Desk Editor's Note private letter to a colleague

The paper reduces whether a symbolic matrix product always has non-negative eigenvalues to a graph condition from the positive graph conjecture, yielding decidability.

read the letter

The main point to know is that the authors reduce the problem of deciding if a symbolic matrix product always has only non-negative real eigenvalues to checking a condition on an associated graph drawn from the positive graph conjecture. This gives both decidability and a characterization. What is new is the specific translation from the matrix product to the graph. Prior work on the positive graph conjecture is cited, but this application to matrix eigenvalues via symbolic products with transposes is fresh. The paper does well in laying out how the product structure maps to graph vertices and edges, and in arguing that the eigenvalue property corresponds exactly to the graph satisfying the conjecture's condition. This avoids brute force search over matrix dimensions and entries. The soft spot is the completeness of that correspondence. For products involving several different variables and mixed transposes, one has to be sure that the graph captures every possible negative eigenvalue scenario. The paper claims to prove both directions, but any gap in constructing a bad matrix assignment from a bad graph would undermine the result. The abstract is too high level to see the details, but the full text presumably fills them in. There are no other major issues; the argument is not circular and the conjecture is used appropriately as an external result. This is for people working on matrix positivity questions or on the positive graph conjecture itself. A reader who needs to decide the property for concrete products or who wants to see how graph theory can decide algebraic questions will find it worthwhile. It deserves a serious referee to go over the reduction proof. I recommend sending it to peer review.

Referee Report

2 major / 2 minor

Summary. The paper considers the decision problem of whether a symbolic product of length k (involving ℓ variables and their transposes, e.g., ABB^T C A^T) always yields a matrix with only non-negative real eigenvalues for every dimension n and every real matrix assignment. It claims this problem is decidable and supplies a characterization of the products that satisfy the property, expressed as a graph-theoretic condition drawn from the positive graph conjecture of Camarena et al.; the argument proceeds by reducing the eigenvalue question to this combinatorial condition.

Significance. If the reduction is sound and complete, the result supplies a decidable combinatorial criterion for a natural generalization of the fact that A^T A is always positive semi-definite. The explicit link to the positive graph conjecture is a genuine strength, converting an algebraic question into a graph-theoretic one and thereby making the property checkable in principle without searching over matrices.

major comments (2)

[§4] §4 (reduction from symbolic product to graph): the claimed if-and-only-if equivalence between “the product has only non-negative eigenvalues for all assignments” and “the associated graph satisfies the positive-graph-conjecture condition” is the sole bridge between the linear-algebra statement and the decision procedure. The manuscript must exhibit the precise graph-construction map (vertices, edges, and labeling induced by the sequence of variables and transposes) and verify both directions for products containing at least two distinct variables or interleaved transposes; any gap here renders the decidability claim unsupported.
[Theorem 3.1] Theorem 3.1 (main characterization): the statement that the eigenvalue property holds for every n and every assignment if and only if the graph meets the conjecture condition is load-bearing. The proof sketch in the abstract does not indicate how the “only if” direction is obtained when the product length k is arbitrary; an explicit counter-example search or inductive argument on k must be supplied to confirm completeness.

minor comments (2)

[Abstract] The abstract asserts “a simple characterization” yet does not state the graph condition explicitly; while acceptable in an abstract, the introduction or §2 should display the precise combinatorial criterion so that readers can immediately apply it to small examples.
[§2] Notation for the symbolic product (e.g., how variables are indexed and how transposes are placed) should be fixed once in §2 and used uniformly; minor inconsistencies in the running example ABB^TCA^T appear in the abstract versus later text.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below, clarifying the existing arguments and indicating the revisions that will be incorporated to improve explicitness and completeness.

read point-by-point responses

Referee: [§4] §4 (reduction from symbolic product to graph): the claimed if-and-only-if equivalence between “the product has only non-negative eigenvalues for all assignments” and “the associated graph satisfies the positive-graph-conjecture condition” is the sole bridge between the linear-algebra statement and the decision procedure. The manuscript must exhibit the precise graph-construction map (vertices, edges, and labeling induced by the sequence of variables and transposes) and verify both directions for products containing at least two distinct variables or interleaved transposes; any gap here renders the decidability claim unsupported.

Authors: The graph-construction map is defined in §4 by associating each factor in the symbolic product with a vertex, with directed edges and labels determined by the variable identities and transpose operations in exact accordance with the positive-graph-conjecture framework of Camarena et al. Both directions of the equivalence are established by reducing eigenvalue negativity to the existence of a violating cycle or labeling in the graph. To address the request for greater explicitness, we will add a formal definition of the map together with a complete verification for the running example ABB^T C A^T (two distinct variables, interleaved transposes), including explicit matrix assignments that realize negative eigenvalues precisely when the graph condition fails. This revision will make the reduction fully self-contained. revision: yes
Referee: [Theorem 3.1] Theorem 3.1 (main characterization): the statement that the eigenvalue property holds for every n and every assignment if and only if the graph meets the conjecture condition is load-bearing. The proof sketch in the abstract does not indicate how the “only if” direction is obtained when the product length k is arbitrary; an explicit counter-example search or inductive argument on k must be supplied to confirm completeness.

Authors: The full proof of Theorem 3.1 proceeds by induction on product length k. The base cases (small k) are verified by direct computation, while the inductive step constructs a counter-example matrix assignment from a graph violation when the positive-graph condition fails. Although the abstract contains only a high-level sketch, the inductive argument and the associated counter-example procedure are already present in the body of the proof. We will expand the write-up of the induction to include an explicit algorithmic description of the counter-example search for arbitrary k, thereby confirming completeness without altering the logical structure. revision: partial

Circularity Check

0 steps flagged

No circularity: characterization via external graph-theoretic reduction

full rationale

The paper derives decidability and a combinatorial characterization for symbolic matrix products with non-negative real eigenvalues by establishing a sound and complete reduction to a condition drawn from the external positive graph conjecture of Camarena et al. No self-definitional loops, fitted parameters renamed as predictions, or load-bearing self-citations appear; the connection to graph theory is presented as an independent translation rather than a re-expression of the input. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard facts about matrix transposition, multiplication, and the spectral theorem for real matrices together with an unproven combinatorial conjecture; no free parameters or new entities are introduced in the abstract.

axioms (2)

standard math Eigenvalues of real matrices are either real or come in conjugate pairs; transposition satisfies (AB)^T = B^T A^T.
Invoked implicitly when discussing eigenvalues of the product and the effect of transposes.
domain assumption The positive graph conjecture supplies a decidable characterization of the relevant graphs.
The paper states that its matrix characterization is the matrix analogue of this conjecture.

pith-pipeline@v0.9.0 · 5442 in / 1327 out tokens · 52283 ms · 2026-05-08T18:16:54.265002+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[1]

L´ aszl´ o Babai, Paul Erd˝ os, and Stanley M. Selkow. Random graph isomorphism.SIAM Journal on Computing, 9(3):628–635, 1980

1980
[2]

Positive graphs.European Journal of Combinatorics, 52:290–301, 2016

Omar Antol´ ın Camarena, Endre Cs´ oka, Tam´ as Hubai, G´ abor Lippner, and L´ aszl´ o Lov´ asz. Positive graphs.European Journal of Combinatorics, 52:290–301, 2016

2016
[3]

Springer Science & Business Media, 2012

Andrea Crisanti, Giovanni Paladin, and Angelo Vulpiani.Products of random matrices: in Statistical Physics, volume 104 ofSpringer Series in Solid-State Sciences. Springer Science & Business Media, 2012

2012
[4]

Asymmetric graphs.Acta Mathematica Academiae Scientiarum Hungaricae, 14(3):295–315, 1963

Paul Erd˝ os and Alfr´ ed R´ enyi. Asymmetric graphs.Acta Mathematica Academiae Scientiarum Hungaricae, 14(3):295–315, 1963

1963
[5]

OUP Oxford, 2004

Pavol Hell and Jaroslav Neˇ setˇ ril.Graphs and homomorphisms, volume 28. OUP Oxford, 2004

2004
[6]

John Wiley & Sons, 2000

Svante Janson, Tomasz Luczak, and Andrzej Ruci´ nski.Random graphs. John Wiley & Sons, 2000

2000
[7]

Graph homomorphisms: Open problems, 2008

L´ aszl´ o Lov´ asz. Graph homomorphisms: Open problems, 2008. Manuscript, originally available athttp://www.cs.elte.hu/ ~lovasz/problems.pdf

2008
[8]

American Mathematical Society, Providence, RI, 2012

L´ aszl´ o Lov´ asz.Large networks and graph limits, volume 60 ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012

2012
[9]

Matiyasevich

Yuri V. Matiyasevich. The diophantineness of enumerable sets.Doklady Akademii Nauk SSSR, 191(2):279–282, 1970

1970
[10]

Paterson

Michael S. Paterson. Unsolvability in 3×3 matrices.Studies in Applied Mathematics, 49(1):105– 107, 1970

1970
[11]

A decision method for elementary algebra and geometry

Alfred Tarski. A decision method for elementary algebra and geometry. InQuantifier elimination and cylindrical algebraic decomposition, pages 24–84. Springer, 1998

1998
[12]

Cambridge University Press, 2014

Marcelo Viana.Lectures on Lyapunov exponents, volume 145 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, 2014. 26

2014