Tensor products of coherent configurations

Abstract

A Cartesian decomposition of a coherent configuration ✗ is defined as a special set of its parabolics that form a Cartesian decomposition of the underlying set. It turns out that every tensor decomposition of ✗ comes from a certain Cartesian decomposition. It is proved that if the coherent configuration ✗ is thick, then there is a unique maximal Cartesian decomposition of ✗; i.e., there is exactly one internal tensor decomposition of ✗ into indecomposable components. In particular, this implies an analog of the Krull–Schmidt theorem for the thick coherent configurations. A polynomial-time algorithm for finding the maximal Cartesian decomposition of a thick coherent configuration is constructed.

Keywords

Coherent configuration / Cartesian decomposition / Krull–Schmidt theorem

References

[1] Bailey R A, Cameron P J, Praeger C E, Schneider C. The geometry of diagonal groups. arXiv: 2007.10726

[2] Chen G, Ponomarenko I. Coherent Configurations. Wuhan: Central China Normal Univ Press, 2019; a draft is available at www.pdmi.ras.ru/~inp/ccNOTES.pdf

[3] Cormen T H, Leiserson C E, Rivest R L, Stein C. Introduction to Algorithms. 3rd ed. Cambridge: The MIT Press, 2009

[4] Ferguson P A, Turull A. Algebraic decomposition of commutative association schemes. J Algebra, 1985, 96: 211–229

[5] Friedl K, Ronyai L. Polynomial time solutions of some problems of computational algebra. In: Proc of the Seventeenth ACM STOC. 1985, 153–162

[6] Hammack R, Imrich W, Klavzar S. Handbook of Product Graphs. Boca Raton: CRC Press, 2011

[7] Higman D G. Coherent configurations. I. Rend Semin Mat Univ Padova, 1971, 44: 1–25

[8] Higman D G. Coherent algebras. Linear Algebra Appl, 1987, 93: 209–239

[9] Kayal N, Nezhmetdinov T. Factoring groups efficiently. Lecture Notes in Comput Sci, 2009, 5555: 585–596

[10] Krause H. Krull–Schmidt categories and projective covers. Expo Math, 2015, 33: 535–549

[11] Praeger C E, Schneider C. Permutation Groups and Cartesian Decompositions. Cambridge: Cambridge Univ Press, 2018

[12] Wilson J B. Existence, algorithms, and asymptotics of direct product decompositions, I. Groups Complex Cryptol, 2012, 4(1): 1–39

[13] Xu B. Direct products of association schemes and tensor products of table algebras. Algebra Colloq, 2013, 20(3): 475–494

[14] Zieschang P-H. Theory of Association Schemes. Berlin: Springer, 2005

RIGHTS & PERMISSIONS

Higher Education Press