paper.md

title	tags	authors	affiliations	date	bibliography
RepnDecomp: A GAP package for decomposing linear representations of finite groups	GAP mathematics groups representations	name orcid affiliation Kaashif Hymabaccus 0000-0001-8581-5804 1 name orcid affiliation Dmitrii Pasechnik 0000-0002-7557-6886 1	name index University of Oxford 1	31 August 2019	paper.bib

Summary

A linear representation of a finite group is a homomorphism from a finite group G to the group of linear automorphisms of a vector space V. When studying problems in algebra and combinatorics, it is often useful to also study associated representations to better understand the structure of the problem. This is also useful for computation, since representations allow us to use tools from linear algebra to solve problems in group theory. A key property of complex representations of finite groups is that all such representations are completely reducible, meaning we can decompose them into direct sums of irreducible representations. When working with matrices, this corresponds to finding a basis which produces an optimal block diagonal form of the representation, with the smallest possible blocks. In cases where there are many small blocks, this can greatly improve the efficiency of computations done with the matrices.

Currently, while methods for doing these decompositions are known (and are described in @serre:1977), there are no open-source computer programs that implement these methods, nor are details on how to achieve good performance of such an implementation published.

Using the GAP system [@gap:2020], we have produced a package RepnDecomp that provides the following functions:

• Decompose a representation into a direct sum of irreducible representations
• Compute the associated basis that gives an optimal block diagonalisation
• Determine whether two representations are isomorphic and compute the isomorphism
• Compute a unitary representation isomorphic to a given representation
• Compute the centraliser of the representation (the vector space of matrices that commute with the matrices of the representation)

Our package deals exclusively with the case where V is a finite-dimensional $\mathbb{C}$-vector space with linear automorphisms represented as square matrices. In fact, we only consider cases where the matrix coefficients are cyclotomic numbers - complex numbers in the $\mathbb{Q}$-vector space spanned by all powers of all roots of unity. Our methods are not specific to cyclotomic numbers, but the GAP system only has facilities to compute with cyclotomics and not general complex numbers.

This package has been applied to improve the block diagonalisation of matrices involved in a semidefinite program for computing bounds on the crossing number of complete graphs [@deklerk:2007]. Our package can also be applied to other problems mentioned by @deklerk:2007, including the computation of bounds for the Lovász $\vartheta$ (and related $\vartheta'$) numbers for graphs, and the truss topology design problem described in @kanno:1970 for trusses with suitable symmetries.

The algorithms used to implement this package are not all original. One algorithm for decomposing representations is original work. The other is based on formulas described in @serre:1977 --- however, we implement apparently novel speedups to make it feasible for groups of large order. Our method for unitarising a representation is based on @dixon:1970, again, with apparently novel speedups.

The development of the package was part of Kaashif Hymabaccus' Master's thesis [@hymabaccus:2019].

Acknowledgements

Kaashif Hymabaccus thanks the Collaborative Computational Project (CCP) in the area of Computational Discrete Mathematics, supported by the EPSRC (EP/M022641/1) for supporting his participation in a GAP workshop.

Dmitrii Pasechnik was partially funded by the OpenDreamKit Horizon 2020 European Research Infrastructures project (#676541).

References