Collapsed Adjacency Matrices, Character Tables and Ramanujan Graphs

This is a database of character tables of endomorphism rings. Let G be a finite group, K a field and M a finite set on which G acts transitively. For a in M let M₁={a},M₂,...,M_r be the distinct orbits of G_a, which have respective representatives a₁=a, a₂,..., a_r. Let E_i be an orbital for G as a subset of MxM. For 1 <= i <= r let A_i[k,l] be the collapsed adjacency matrix for the orbital digraph (M,E_i). Therefore A_i is defined as the number of neighbours of a_k in M_l (see PrSoi for details).
Let R denote the endomorphism ring End_KG(KM) with Schurbasis S={S₁,...,S_k}. Assume that R is abelian. Then the character table of R relative to S can be obtained by computing simultaneous eigenvectors of collapsed adjacency matrices.
The entries of a column of the character table are the eigenvalues of the corresponding orbital digraph (see PrSoi for details).
A regular graph X of degree k is called a Ramanujan graph if max { |b| | b is an eigenvalue of X with |b|< k } is less than or equal 2(k-1)^1/2 (see CePoTeTrVe for details).

For rank up to 5 the collapsed adjacency matrices have been computed by Cheryl E. Praeger and Leonard H. Soicher (PrSoi). Several matrices (also for larger rank cases) can be found in IvLiLuSaSoi, where numerous further references are given.) The following matrices originally have been published in:
LLS: Fi₂₃ with 2¹¹.M₂₃
Soi: Co₁ with 2₊¹⁺⁸.O₈⁺(2)
IM: J₄ with 2¹¹.M₂₄
Nor: M with 2.BM.

All programs used to produce this data base are written in GAP4.

Status of this data base

If you have suggestions for improving this data base please feel free to send an e-mail message to ines.hoehler@math.rwth-aachen.de. This may concern for example known character tables that are missing here, possible errors or the layout of the pages.

Structure of this data base

If you are interested in collapsed adjacency matrices, in a character table, in informations about the permutation character or in finding Ramanujan graphs, go to the section Table of Collapsed Adjacency Matrices, Character Tables and Ramanujan Graphs.

The methods how the collapsed adjacency matrices and the character tables were computed and the program which tests if a graph is a Ramanujan graph are described in the section Computing collapsed adjacency matrices and character tables. There you will also find links to the GAP-programs used.

You will also find GAP-readable data bases. You can use them to compute with the collapsed adjacency matrices and character tables presented here.

Some cases are left open. These are listed in the section Unsolved Cases.

Table of Collapsed Adjacency Matrices, Character Tables and Ramanujan Graphs

First choose the sporadic group G. Then you can choose a subgroup U corresponding to a multiplicity-free transitive action (the notation U < H means that U is contained in the maximal subgroup H of G; if no < sign appears U is itself a maximal subgroup of G). You then have the following choices:
CollapsedAdjacencyMatrices is a list of the collapsed adjacency matrices. These matrices are given as vectors of rows, so they can be read by GAP.
CharacterTable.gap is a GAP-readable file of the character table, and
PermutationCharacter&CharacterTable.dvi is a dvi-file which contains informations about the irreducible characters of the group. These informations were taken out of BrLux; a short description concerning the notation here. The notation follows Chapter 5 of the ATLAS. In some files there are two tables with character information. Then exist two permutation representations, but their stabilizers are conjugate under an outer automorphism of G, so that the collapsed adjacency matrices are the same for both cases.
The file also contains the numbers of the ordinary characters referring to the character table of the group and the character table itself. The lines of the character table are corresponding to the numbers of the ordinary characters arranged.
Finally, the columns which produce Ramanujan graphs are given. The numbers refer to the columns of the character table. More than one number in parenthesis means that the graph corresponding to the union of the columns with the shown numbers is considered. (For the subgroup 2⁴⁺⁶:3A₆ < 2⁴⁺⁶:3S₆ of Suz.2 no Ramanujan graphs are listed because the rank is too large to compute them. This means not that there are no Ramanujan graphs!)
Some large character tables are printed in landscape format. In these cases a PostScript-file PermutationCharacter&CharacterTable.ps is given.

The Groups

B	Co₁	Co₂	Co₃	Fi₂₂	Fi₂₃	Fi'₂₄	He
HN	HS	J₁	J₂	J₃	J₄	Ly	M
M₁₁	M₁₂	M₂₂	M₂₃	M₂₄	McL	O'N	Ru	Suz

Computing collapsed adjacency matrices, character tables and Ramanujan graphs

For the transitive actions of the sporadic simple groups and their automorphism groups with rank 2, a generic form of the collapsed adjacency matrices and the character tables exists. See these generic forms in a dvi-file.

For the transitive actions of the sporadic simple groups and their automorphism groups of ranks 3 up to 5, all collapsed adjacency matrices have been computed by Cheryl E. Praeger and Leonard H. Soicher and are given in PrSoi. For computing the collapsed adjacency matrices of rank > 5 a permutation representation has to be found. For M₁₁, M₁₂, J₁, M₂₂, J₂, M₂₃, HS, J₃, M₂₄, McL, He and their automorphism groups (except HS.2) the program MultFreeFromTOM computes a permutation representation of the groups with the help of the TableOfMarks, which is implemented in GAP. For the other cases the permutation representations can be found in Rob Wilson's Atlas of Group Representations, or have been computed by Jürgen Müller.
Using these permutation representation the program CompCAM computes the collapsed adjacency matrices. The input is the permutation representation and the number of points the group is acting on.

With the input of a list of the collapsed adjacency matrices the program CAMToChar computes the character table in each case. The program CharToLaTeXChar is a program which returns a LaTeX-readable character table.

The information on which graphs are Ramanujan graphs is computed by the GAP-program RamanujanTest. The input has to be a character table, the output is a list of all combinations of columns of the character table for which the corresponding graph is Ramanujan.

Data bases

All results (except the informations on Ramanujan graphs) are unified in these GAP-readable data bases. The data bases contain a list of GAP-records with informations of the following kind:
name for the name of the group,
sbgame for the name of the subgroup,
degree,
rank,
permchar for the Permutation Character given as a string,
charnmbs for the Permutation Character referring to the ordinary characters of the Character Table of the group,
ctbl for the Character Table, and
mats for the list of the Collapsed Adjacency Matrices.
e.g. M11Database[3].sbgname is "3^2:8".
You can view the complete data base with all available informations, but you can also view data bases for singular groups:

Data bases

Complete Data base

B	Co₁	Co₂	Co₃	Fi₂₂	Fi₂₃	Fi'₂₄	He
HN	HS	J₁	J₂	J₃	J₄	Ly	M
M₁₁	M₁₂	M₂₂	M₂₃	M₂₄	McL	O'N	Ru	Suz

Unsolved Cases

Some cases are left unsolved since the degree is too large to compute the collapsed adjacency matrices. You can find a dvi-file containing a list with group, subgroup, degree, permutation character and rank of the unsolved cases here.

Great thanks to all people of Lehrstuhl D for fantastic help, especially Jürgen Müller for computing numerous permutation representations and Thomas Breuer for the programs MultFreeFromTOM and CompCAM and for his help with GAP-problems.

File created on 2nd May 2001
Last modified: 14th May 2001 by Ines Hoehler