Generalized spectral characterization of signed bipartite graphs

Lele Li; Songlin Guo; Wei Wang

REVIEW 2 major objections 4 minor 12 references

Generalized spectral characterization of signed bipartite graphs

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

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

Pith's one-line read For controllable and almost controllable signed bipartite graphs, a squarefree scaled discriminant and a ±1 coefficient condition force determination by generalized spectrum.

desk verdict A genuine extension of the signed-tree DGS criterion, with a proof that hinges on an unproved lemma from the authors' preprint. read the letter →

arxiv 2505.12446 v1 pith:LX3H7OZN submitted 2025-05-18 math.CO

Songlin Guo , Wei Wang , Lele Li This is my paper · ORCID

classification math.CO MSC 05C50

keywords signedbipartitegraphgeneralizedspectrumdiscriminantdeterminedbycontrollablealmostsquarefreeregularorthogonalmatrix

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 establishes a sufficient arithmetic condition for a signed bipartite graph to be determined by its generalized spectrum, meaning the pair of spectra (adjacency matrix and complement-style matrix $J-I-A$) pins the graph down up to isomorphism. The condition applies to graphs that are controllable or almost controllable, i.e. whose walk matrix has rank $n$ or $n-1$. If the characteristic polynomial has constant term $\pm1$ (for even $n$) or linear coefficient $\pm1$ (for odd $n$), and if the integer $2^{-\lfloor n/2\rfloor}\sqrt{\Delta_\Sigma}$ built from the discriminant is squarefree, then the graph is determined by its generalized spectrum. This extends a recent criterion that worked only for signed trees with irreducible characteristic polynomials, and it covers odd-order and reducible cases that the earlier theorem could not reach. A reader should care because generalized spectral uniqueness is a strong form of "the spectrum and complement spectrum tell you everything."

What carries the argument

The machinery is the block decomposition of a bipartite adjacency matrix $A = \begin{pmatrix}0&B\\B^T&0\end{pmatrix}$, joined to the discriminant identity $\Delta_A = 4^{\lfloor n/2\rfloor}\Delta_{BB^T}^2$. This identity converts the squarefree hypothesis into the statement that $\Delta_{BB^T}$ is squarefree. The proof then establishes two exclusion results about the level $\ell(Q)$ of any regular rational orthogonal matrix $Q$ intertwining $A$ with another signed graph, where the level is the smallest positive integer $k$ such that $kQ$ is an integer matrix: if $\ell(Q)$ is even then $\Delta_{BB^T}$ is even, and if an odd prime $p$ divides $\ell(Q)$ then $p^2\mid \Delta_{BB^T}$. Squarefreeness of $\Delta_{BB^T}$ therefore eliminates every prime divisor of $\ell(Q)$, forcing $\ell(Q)=1$; level-1 regular orthogonal matrices are exactly permutation matrices, and Lemma 1 turns that into the DGS conclusion.

What would settle it

Take any controllable or almost controllable signed bipartite graph satisfying the coefficient condition and compute $2^{-\lfloor n/2\rfloor}\sqrt{\Delta_\Sigma}$. If it is squarefree, the theorem predicts that every regular rational orthogonal matrix in $\mathcal{Q}(\Sigma)$ is a permutation matrix; a concrete falsifying observation would be a generalized cospectral partner $\Gamma$ whose intertwining matrix has level greater than 1, or a direct computation in which an odd prime $p$ divides the level of $Q$ while $p^2\nmid \Delta_{BB^T}$. Since the proof depends on unproved lemmas from [9], a small example where those lemmas fail would also break the theorem.

Watch

Extended reading notes

Core claim

The central claim, Theorem 2, is: let $\Sigma$ be an $n$-vertex signed bipartite graph that is controllable or almost controllable, and suppose the constant term ($n$ even) or linear coefficient ($n$ odd) of $\chi(\Sigma;x)$ is $\pm1$. If $2^{-\lfloor n/2\rfloor}\sqrt{\Delta_\Sigma}$ is squarefree, then $\Sigma$ is determined by its generalized spectrum. The proof shows that any regular rational orthogonal matrix $Q$ with $Q^T A(\Sigma)Q = A(\Gamma)$ for a generalized cospectral partner $\Gamma$ must have level 1, hence be a permutation matrix; then $\Gamma$ is isomorphic to $\Sigma$. In particular, the result subsumes the earlier signed-tree theorem and applies to reducible characteristic polynomials and to odd-order signed bipartite graphs.

Load-bearing premise

The load-bearing premise is that the technical lemmas imported without proof from the authors' earlier preprint, in particular Proposition 2 and Lemma 3 of reference [9], correctly control which primes divide the level of an intertwining orthogonal matrix; the claim that Theorem 2 subsumes Theorem 1 also relies on the unstated premise that irreducible signed trees are controllable.

Editorial extensions

If this is right

Every signed tree covered by the earlier irreducible-tree theorem also satisfies the new criterion, and the new criterion additionally covers reducible signed trees and odd-order signed bipartite graphs.
For any signed bipartite graph meeting the two conditions, generalized cospectrality becomes isomorphism: the spectrum plus complement spectrum determines the graph exactly.
The condition is finitely checkable: compute the characteristic polynomial, its discriminant, the constant or linear coefficient, and test squarefreeness of the scaled integer.
In the almost controllable case, satisfying the theorem forces the graph to have a nontrivial automorphism, because only permutation matrices lie in $\mathcal{Q}(\Sigma)$.
The discriminant identity shows that $\Delta_{BB^T}$ is the operative squarefree integer, so the DGS property is tied to the arithmetic of the half-size matrix $BB^T$ rather than to the full adjacency matrix.

Reading between the lines

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

The same squarefree-discriminant mechanism may extend to non-bipartite signed graphs if an analogue of the $\Delta_A = 4^{\lfloor n/2\rfloor}\Delta_{BB^T}^2$ identity can be found for a suitable principal submatrix; the bipartite block form is doing real work in the proof.
The squarefree condition is sufficient, not necessary; graphs with non-squarefree scaled discriminants may still be DGS by other routes, so the criterion likely underestimates the true family of DGS signed bipartite graphs.
Since the almost-controllable case needs a nontrivial automorphism, rigid almost-controllable signed bipartite graphs are unreachable by this argument; a separate mechanism would be required to settle their DGS status.
The proof's reliance on lemmas from an earlier preprint suggests that a formal verification or self-contained proof of the imported lemmas would be the most direct way to confirm the result before using it in applications.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

The headline result is a real extension: Theorem 2 removes the irreducibility and even-order restrictions from Ji-Wang-Zhang's signed-tree criterion and covers almost controllable signed bipartite graphs, answering a question they posed. The proof is largely sound, and the p=2 part—the total-isotropy argument in Section 3.1—is the most substantial new work. I checked the discriminant identity (Lemma 11), the walk-matrix rank calculations, and the examples; they are consistent, and the computed factorizations look reproducible.

The soft spot is structural. The odd-prime case in Section 3.2 depends on Proposition 2 of the authors' own arXiv:2504.12932, imported without proof. That proposition is what converts divisibility of the level of Q into divisibility of det(A^2 - λ0 I) and det(A ± λ1 I), and without it the contradiction in Proposition 5 does not go through. The stress-test note is right that this is the decisive external dependency. In a journal submission the authors should be required to either prove Proposition 2 in full or state it with hypotheses and a proof sketch; a paper whose main theorem hinges on an unproved claim in a preprint is not self-contained. The related Lemma 3 is easy and could be proven in two lines, so that one is a minor omission.

A second, smaller gap: the paper says Theorem 2 subsumes Theorem 1 but doesn't justify that irreducible signed trees are controllable. It is true—if χ(A) is irreducible then e is cyclic, so W(Σ) has full rank—and it should be a one-sentence remark.

Overall, I think the theorem is very likely true and the contribution is meaningful within the generalized spectral characterization niche. The dependency on Proposition 2 is a real but fixable weakness, not a sign of a broken argument. The paper deserves a serious referee, and I would send it to review, with the clear instruction that the authors supply the missing proof of Proposition 2 before acceptance.

Referee Report

2 major / 4 minor

Summary. The paper studies the generalized spectral characterization (DGS) of signed bipartite graphs. Theorem 2 states that if an n-vertex controllable or almost controllable signed bipartite graph has the coefficient of the constant term (n even) or linear term (n odd) equal to ±1, and if 2^{-⌊n/2⌋}√Δ_Σ is squarefree, then the graph is DGS. The proof strategy is to show that every rational regular orthogonal matrix Q in Q(Σ) must have level 1. For the prime p=2 this is done through a totally isotropic subspace argument over F_2; for odd primes the contradiction is obtained by transferring a p-adic divisibility of det(A^2-λ0 I) or det(A±λ1 I) to det(BB^T-λ0 I), then invoking Lemma 7 and Lemma 8(iv). The paper also provides three Mathematica-verified examples illustrating reducible and almost controllable cases.

Significance. If correct, the result is a meaningful extension of the recent criterion of Ji, Wang, and Zhang for irreducible signed trees to a larger class of signed bipartite graphs, including reducible and almost controllable cases. The p=2 argument is detailed and the total-isotropy reasoning in Lemma 15 is coherent; Lemma 11 correctly reduces the discriminant condition to Δ_{BB^T} being squarefree; the examples are concrete and support the applicability of the theorem. The main reservation is that the odd-prime case depends essentially on Proposition 2, which is imported without proof from the authors' own unpublished arXiv preprint [9]; the central claim is therefore plausible but not yet fully self-contained.

major comments (2)

[§2.1 and §3.2] Proposition 2 is stated without proof and is load-bearing in the proof of Proposition 5. In Case 1 it is used to conclude p^3 | det(A^2-λ0 I), and in Case 2 it is used to conclude p^2 | det(A-λ1 I) or p^2 | det(A+λ1 I). These are exactly the steps that bridge the level of Q to the determinant of BB^T, after which Lemma 7 closes the argument. Since Proposition 2 is a non-elementary assertion about the level of a rational regular orthogonal matrix and a primary factor of χ(A) over F_p, and since reference [9] is an unpublished arXiv preprint by the same authors, the manuscript should include a complete proof of Proposition 2, or at minimum a precise statement of all its hypotheses together with a proof. Without this, the odd-prime part of Proposition 5 is not verifiable from the paper itself.
[§3.2] The transition from Proposition 1 to the applications of Proposition 2 needs to be made explicit. Proposition 1 only guarantees a multiple factor φ(x) of χ(A;x) over F_p with col(Qhat)∩ker φ(A) ≠ 0, while Proposition 2 is applied to the specific integer polynomials x^2-λ0 and x±λ1 in Cases 1 and 2. The paper should state how these integer polynomials represent the relevant factors over F_p and verify that all hypotheses of Proposition 2 (regularity of Q, rationality, and the stated condition on φ) are met in both cases.

minor comments (4)

[§2.2, Proposition 3] In the proof of Proposition 3, the phrase 'by Lemma (ii)' should read 'by Lemma 8(ii)'; the reference is incomplete as printed.
[§2.2, Lemma 9] The displayed expression for u(x) in the proof of Lemma 9 appears to contain a typo: it should be u(x)=u_{n-2}x^{n-2}+u_{n-3}x^{n-3}+...+u_0, not a repetition of u_0 in several terms.
[§1] The claim that Theorem 2 subsumes Theorem 1 relies on the fact that an irreducible signed tree is controllable. This is true because irreducibility of χ(A) makes e a cyclic vector, but the paper does not state this; a one-sentence explanation would remove an implicit step.
[§3.2] The symbol φ is used both for the polynomial supplied by Lemma 6 and for the multiple factor appearing in Proposition 1/Proposition 2; the notation should be distinguished to avoid confusion in Cases 1 and 2.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction found; the proof combines prior arithmetic lemmas, with the main unproved dependency being same-author Proposition 2 of [9], a soundness concern rather than a circularity.

full rationale

I traced the derivation of Theorem 2 through Lemma 11 and Propositions 4 and 5. The hypothesis that the relevant coefficient of the characteristic polynomial is ±1 is used to force det(BBT)=1 and to control the parity of the bipartition; the squarefree discriminant hypothesis is used only at the final step to rule out p^2|Δ_BBT. Proposition 4 is proved internally from Lemmas 12 and 15, and Proposition 5 is proved from Lemmas 5-7 together with Proposition 2. None of these steps assumes the DGS conclusion of Theorem 2, and no equation in the paper defines the target property in terms of the discriminant criterion. The only load-bearing step that is imported rather than proved is Proposition 2 of [9], a same-group arXiv preprint; the proof needs it twice, in Case 1 to obtain p^3|χ(A^2;λ0) and in Case 2 to obtain p^2|det(A−λ1I) or p^2|det(A+λ1I). Even if that lemma were unsound, the failure would be a gap in an external premise, not a circular reduction of the prediction to its inputs. The sentence claiming that Theorem 2 subsumes Theorem 1 also presupposes, without proof, that irreducible signed trees are controllable; that is a separate correctness concern and is not used in the proof of Theorem 2. I therefore find no circular step; the score 2 reflects the unproved same-author dependency and the heavy self-citation density, not a circularity.

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

The paper's central claim rests on a network of previously established lemmas, several from the authors' own prior work ([4], [6], [9]); these are cited rather than proved here. No free parameters are fitted and no new entities are postulated.

assumptions (6)

domain assumption For any prime p dividing the level of Q, the column space of Q-hat modulo p is nonzero, totally isotropic and A-invariant (Lemma 3, from [9]).
Used at the start of Sections 3.1 and 3.2 to analyze even and odd prime factors of the level of a rational orthogonal matrix Q in Q(Σ).
domain assumption If p is an odd prime factor of the level of Q and φ(x) satisfies the conclusion of Proposition 1, then p^(deg φ + 1) divides det φ(A) (Proposition 2, from [9]).
Central in the proof of Proposition 5 in Section 3.2 to force p^2 dividing det(λ0 I − BB^T).
domain assumption Any prime factor of the level of Q is a factor of the discriminant Δ_A (Lemma 5, from [4]).
Used in the proof of Proposition 5 to connect prime factors of the level to the discriminant.
domain assumption Lemmas 6 and 7 from [4]: the structure of the characteristic polynomial modulo an odd prime and the equivalence between a congruence solvability condition and p^2 dividing det(M − λ0 I).
Used in Section 3.2 to reduce the odd-prime case to a divisibility condition on det(λ0 I − BB^T).
domain assumption Lemma 12 from [6]: if Q has even level, then q^T A^k q is congruent to 0 modulo 4 for all integer vectors q in the column space of Q-hat.
Used in Section 3.1 to prove the total isotropy of ker φ(BB^T) in Lemma 15.
domain assumption Theorem 3 from [2,3,11]: generalized cospectrality of controllable or almost controllable signed graphs is equivalent to the existence of a regular rational orthogonal matrix Q with Q^T A(Σ) Q = A(Γ).
Provides the basic framework used in Lemma 1 and throughout the proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Generalized spectral characterization of signed bipartite graphs." pith.science (2026). https://pith.science/paper/LX3H7OZN

@misc{pith2026250512446,
  author       = {Pith},
  title        = {Pith review of: Generalized spectral characterization of signed bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LX3H7OZN}},
  note         = {Machine review of arXiv:2505.12446}
}

abstract

Let $\Sigma$ be an $n$-vertex controllable or almost controllable signed bipartite graph, and let $\Delta_\Sigma$ denote the discriminant of its characteristic polynomial $\chi(\Sigma; x)$. We prove that if (\rmnum{1}) the integer $2^{ -\lfloor n/2 \rfloor }\sqrt{\Delta _{\Sigma}}$ is squarefree, and (\rmnum{2}) the constant term (even $n$) or linear coefficient (odd $n$) of $\chi(\Sigma; x)$ is $\pm 1$, then $\Sigma$ is determined by its generalized spectrum. This result extends a recent theorem of Ji, Wang, and Zhang [Electron. J. Combin. 32 (2025), \#P2.18], which established a similar criterion for signed trees with irreducible characteristic polynomials.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

[9]

P. L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics, Version 2.2, Department of Computer Science, University of Chicago, 2022

work page 2022
[1]

Schwenk, Almost all trees are cospectral, in: F

A.J. Schwenk, Almost all trees are cospectral, in: F. Harary (Ed.), New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 275--307

work page 1973
[2]

C. D. Godsil, Controllable subsets in graphs, Ann. Comb. 16 (2012) 733--744

work page 2012
[3]

C. R. Johnson, M. Newman, A note on cospectral graphs, J. Combin. Theory, Ser. B, 28 (1980) 96--103

work page 1980
[4]

Wang, C.-X

W. Wang, C.-X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra, European J. Combin. 27 (6) (2006) 826--840

work page 2006
[5]

W. Wang, T. Yu, Square-free discriminants of matrices and the generalized spectral characterizations of graphs, arXiv:1608.01144

arXiv
[6]

Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J

W. Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J. Combin. Theory, Ser. B, 122 (2017) 438--451

work page 2017
[7]

Wang, Generalized spectral characterization revisited, Electron

W. Wang, Generalized spectral characterization revisited, Electron. J. Combin. 20 (2013) \#P4

work page 2013

Show all 12 references

[8]

Y. Ji, W. Wang, H. Zhang, Generalized spectral characterization of signed trees, Electron. J. Combin. 32 (2025), \#P2.18

2025
[10]

S. Guo, W. Wang, W. Wang, Primary decomposition theorem and generalized spectral characterization of graphs, arXiv:2504.12932
[11]

Lang, Algebra, Springer-Verlag, New York, 2002

S. Lang, Algebra, Springer-Verlag, New York, 2002

2002
[12]

W. Wang, F. Liu, W. Wang, Generalized spectral characterizations of almost controllable graphs, European J. Combin. 96 (2021) 103348

2021

Pith tools

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

[1] [9]

P. L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics, Version 2.2, Department of Computer Science, University of Chicago, 2022

work page 2022

[2] [1]

Schwenk, Almost all trees are cospectral, in: F

A.J. Schwenk, Almost all trees are cospectral, in: F. Harary (Ed.), New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 275--307

work page 1973

[3] [2]

C. D. Godsil, Controllable subsets in graphs, Ann. Comb. 16 (2012) 733--744

work page 2012

[4] [3]

C. R. Johnson, M. Newman, A note on cospectral graphs, J. Combin. Theory, Ser. B, 28 (1980) 96--103

work page 1980

[5] [4]

Wang, C.-X

W. Wang, C.-X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra, European J. Combin. 27 (6) (2006) 826--840

work page 2006

[6] [5]

W. Wang, T. Yu, Square-free discriminants of matrices and the generalized spectral characterizations of graphs, arXiv:1608.01144

arXiv

[7] [6]

Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J

W. Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J. Combin. Theory, Ser. B, 122 (2017) 438--451

work page 2017

[8] [7]

Wang, Generalized spectral characterization revisited, Electron

W. Wang, Generalized spectral characterization revisited, Electron. J. Combin. 20 (2013) \#P4

work page 2013