HEXAGONbeta

Complexity of Mutation-Acyclicity and Matrix Mutation Equivalence

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricscs.CC — Computational Complexity

Contributed by Qiyue Tang ↗

Version 1 / Nov 07, 2026 / CC BY 4.0

Abstract

Mutation-acyclicity of integral skew-symmetrizable matrices belongs to NP. Mutation equivalence belongs to promise-NP when at least one input is mutation-acyclic. For pairs of mutation-cyclic matrices, mutation equivalence is RE-complete and strongly NP-hard. Both results hold even for connected skew-symmetric matrices.

Provenance statement

GPT-6-Pro was used in a research session whose preserved records span approximately seven and a half hours. Codex was used to review and polish the manuscript. A further review using Rethlas-OSV is planned.

References

  1. S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations , J. Amer. Math. Soc. 15 (2002), 497--529.
  2. S. Fomin, L. Williams, and A. Zelevinsky, Introduction to cluster algebras. Chapters 1--3 , arXiv:1608.05735v4 (https://arxiv.org/abs/1608.05735v4); combined preliminary draft of Chapters 1--7 (2021), Problems 2.6.14 and 2.8.2, https://pages.uoregon.edu/arkadiy/intro.clust.alg.pdf.arXiv
  3. K. T. K. Armstrong-Williams, E. Hirst, B. Jackson, and K.-H. Lee, Mutation-acyclicity in rank four is decidable but not semialgebraic , arXiv:2610.36179v1 (https://arxiv.org/abs/2610.36179v1), 2026.arXiv
  4. Q. Tang, Decidability of mutation-acyclicity , Hexagon preprint 2611.00163v1 (https://hexagonmath.org/2611.00163v1), 2026.hexagon
  5. D. Soukup, Complexity of ice quiver mutation equivalence , Ann. Comb. 29 (2025), 91--100, doi:10.1007/s00026-023-00668-w (https://doi.org/10.1007/s00026-023-00668-w).DOI
  6. Q. Tang, Undecidability of quiver mutation equivalence , Hexagon preprint 2611.00158v1 (https://hexagonmath.org/2611.00158v1), 2026.hexagon
  7. S. Fomin and A. Zelevinsky, Cluster algebras II: Finite type classification , Invent. Math. 154 (2003), 63--121, doi:10.1007/s00222-003-0302-y (https://doi.org/10.1007/s00222-003-0302-y).DOI
  8. E. S. Dias and D. Castonguay, Polynomial recognition of cluster algebras of finite type , arXiv:1507.03844v1 (https://arxiv.org/abs/1507.03844v1), 2015.arXiv
  9. P. Caldero and B. Keller, From triangulated categories to cluster algebras II , Ann. Sci. Éc. Norm. Supér. (4) 39 (2006), 983--1009, doi:10.1016/j.ansens.2006.09.003 (https://doi.org/10.1016/j.ansens.2006.09.003).DOI
  10. I. Assem, M. Blais, T. Brüstle, and A. Samson, Mutation classes of skew-symmetric 3×33\times3-matrices , Comm. Algebra 36 (2008), 1209--1220, arXiv:math/0610627 (https://arxiv.org/abs/math/0610627).arXiv
Show all 32 referencesShow fewer references
  1. A. I. Seven, Mutation classes of skew-symmetrizable 3×33\times3 matrices , arXiv:1012.3318v2 (https://arxiv.org/abs/1012.3318v2), 2011.arXiv
  2. R. Akagi, Cluster-cyclic condition of skew-symmetrizable matrices of rank 3 via the Markov constant , arXiv:2411.07083v2 (https://arxiv.org/abs/2411.07083v2), 2025.arXiv
  3. A. Felikson, M. Shapiro, and P. Tumarkin, Skew-symmetric cluster algebras of finite mutation type , J. Eur. Math. Soc. 14 (2012), 1135--1180, doi:10.4171/JEMS/329 (https://doi.org/10.4171/JEMS/329).DOI
  4. S. Fomin, K. Igusa, and K. Lee, Universal quivers , Algebr. Comb. 4 (2021), 683--702, doi:10.5802/alco.175 (https://doi.org/10.5802/alco.175).DOI
  5. S. Fomin, Quiver mutations , Open Problems in Algebraic Combinatorics, Minneapolis, May 16, 2022, https://www.samuelfhopkins.com/OPAC/files/slides/fomin.pdf.link
  6. S. Fomin and S. Neville, Long mutation cycles , Selecta Math. (N.S.) 31 (2025), article 103, doi:10.1007/s00029-025-01090-1 (https://doi.org/10.1007/s00029-025-01090-1).DOI
  7. V. G. Kac, Infinite-dimensional Lie algebras , third edition, Cambridge University Press, Cambridge, 1990.
  8. C. T. McMullen, Coxeter groups, Salem numbers and the Hilbert metric, Publications Mathématiques de l'IHÉS 95 (2002), 151--183, doi:10.1007/s102400200001 (https://doi.org/10.1007/s102400200001).DOI
  9. N. Chapelier-Laget and C. Hohlweg, Shi arrangements and low elements in affine Coxeter groups, Canadian Journal of Mathematics 77 (2025), 683--713, doi:10.4153/S0008414X24000130 (https://doi.org/10.4153/S0008414X24000130).DOI
  10. A. Hubery and H. Krause, A categorification of non-crossing partitions , J. Eur. Math. Soc. 18 (2016), 2273--2313, doi:10.4171/JEMS/641 (https://doi.org/10.4171/JEMS/641).DOI
  11. A. Hubery, The cluster complex of an hereditary Artin algebra , Algebr. Represent. Theory 14 (2011), 1163--1185, arXiv:0812.1475 (https://arxiv.org/abs/0812.1475).arXiv
  12. D. Rupel, Quantum cluster characters for valued quivers , Trans. Amer. Math. Soc. 367 (2015), 7061--7102, doi:10.1090/S0002-9947-2015-06251-5 (https://doi.org/10.1090/S0002-9947-2015-06251-5).DOI
  13. D. Happel and C. M. Ringel, Tilted algebras , Trans. Amer. Math. Soc. 274 (1982), 399--443.
  14. A. B. Buan, R. J. Marsh, M. Reineke, I. Reiten, and G. Todorov, Tilting theory and cluster combinatorics , Adv. Math. 204 (2006), 572--618, arXiv:math/0402054 (https://arxiv.org/abs/math/0402054).arXiv
  15. C. M. Ringel, The spectral radius of the Coxeter transformations for a generalized Cartan matrix , Math. Ann. 300 (1994), 331--339, doi:10.1007/BF01450490 (https://doi.org/10.1007/BF01450490).DOI
  16. D. E. Speyer, Powers of Coxeter elements in infinite groups are reduced , Proc. Amer. Math. Soc. 137 (2009), 1295--1302, arXiv:0710.3188 (https://arxiv.org/abs/0710.3188).arXiv
  17. M. Fiedler, Numerical range of matrices and Levinger's theorem , Linear Algebra Appl. 220 (1995), 171--180, doi:10.1016/0024-3795(94)00073-M (https://doi.org/10.1016/0024-3795(94)00073-M).DOI
  18. G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London Ser. A 262 (1961), 455--475. doi:10.1098/rspa.1961.0132 (https://doi.org/10.1098/rspa.1961.0132).DOI
  19. R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory , Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 89, Springer-Verlag, Berlin--New York, 1977.
  20. A. Beineke, T. Brüstle and L. Hille, Cluster-cyclic quivers with three vertices and the Markov equation, with an appendix by O. Kerner, Algebr. Represent. Theory 14 (2011), 97--112. doi:10.1007/s10468-009-9179-9 (https://doi.org/10.1007/s10468-009-9179-9).DOI
  21. A. B. Buan, B. R. Marsh and I. Reiten, Cluster mutation via quiver representations, Comment. Math. Helv. 83 (2008), 143--177. doi:10.4171/CMH/121 (https://doi.org/10.4171/CMH/121).DOI
  22. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, San Francisco, 1979.

Version history

  1. v1 · 35 pagesSubmitted by Qiyue TangInitial depositCurrentNov 07, 2026