The functions described in this chapter are used to handle characters (see Chapter Character Tables). For this, in many cases one needs maps (see Chapter Maps and Parametrized Maps).
There are four kinds of functions:
First, those functions which get informations about characters; they compute the scalar product of characters (see ScalarProduct, MatScalarProducts), decomposition matrices (see Decomposition, Subroutines of Decomposition), the kernel of a character (see KernelChar), p-blocks (see PrimeBlocks), Frobenius-Schur indicators (see Indicator), eigenvalues of the corresponding representations (see Eigenvalues), and Molien series of characters (see MolienSeries), and decide if a character might be a permutation character candidate (see Permutation Character Candidates).
Second, those functions which construct characters or virtual characters, that is, differences of characters; these functions compute reduced characters (see Reduced, ReducedOrdinary), tensor products (see Tensored), symmetrisations (see Symmetrisations, SymmetricParts, AntiSymmetricParts, MinusCharacter, OrthogonalComponents, SymplecticComponents), and irreducibles differences of virtual characters (see IrreducibleDifferences). Further, one can compute restricted characters (see Restricted), inflated characters (see Inflated), induced characters (see Induced, InducedCyclic), and permutation character candidates (see Permutation Character Candidates, PermChars).
Third, those functions which use general methods for lattices. These are the LLL algorithm to compute a lattice base consisting of short vectors (see LLLReducedBasis, LLLReducedGramMat, LLL), functions to compute all orthogonal embeddings of a lattice (see OrthogonalEmbeddings), and one for the special case of D_n lattices (see DnLattice). A backtrack search for irreducible characters in the span of proper characters is performed by Extract.
Finally, those functions which find special elements of parametrized characters (see More about Maps and Parametrized Maps); they compute the set of contained virtual characters (see ContainedDecomposables) or characters (see ContainedCharacters), the set of contained vectors which possibly are virtual characters (see ContainedSpecialVectors, ContainedPossibleVirtualCharacters) or characters (see ContainedPossibleCharacters).
ScalarProduct( tbl, character1, character2 )
returns the scalar product of character1 and character2, regarded as characters of the character table tbl.
gap> t:= CharTable( "A5" );; gap> ScalarProduct( t, t.irreducibles[1], [ 5, 1, 2, 0, 0 ] ); 1 gap> ScalarProduct( t, [ 4, 0, 1, -1, -1 ], [ 5, -1, 1, 0, 0 ] ); 2/3
MatScalarProducts( tbl, chars1, chars2 )
MatScalarProducts( tbl, chars )
For a character table tbl and two lists chars1, chars2 of characters, the first version returns the matrix of scalar products (see ScalarProduct); we have
'MatScalarProducts( <tbl>, <chars1>, <chars2> )[i][j]' = 'ScalarProduct( <tbl>, <chars1>[j], <chars2>[i] )',
i.e., row i
contains the scalar products of chars2[i]
with all
characters in chars1.
The second form returns a lower triangular matrix of scalar products:
'MatScalarProducts( <tbl>, <chars> )[i][j]' = 'ScalarProduct( <tbl>, <chars>[j], <chars>[i] )'
for 'j' leq 'i'.
gap> t:= CharTable( "A5" );; gap> chars:= Sublist( t.irreducibles, [ 2 .. 4 ] );; gap> chars:= Set( Tensored( chars, chars ) );; gap> MatScalarProducts( t, chars ); [ [ 2 ], [ 1, 3 ], [ 1, 2, 3 ], [ 2, 2, 1, 3 ], [ 2, 1, 2, 2, 3 ], [ 2, 3, 3, 3, 3, 5 ] ]
Decomposition( A, B, depth )
Decomposition( A, B, "nonnegative" )
For a m times n matrix A of cyclotomics that has rank m leq n,
and a list B of cyclotomic vectors, each of dimension n,
Decomposition
tries to find integral solutions x of the linear
equation systems x * A = B[i]
by computing the p--adic series
of hypothetical solutions.
Decomposition( A, B, depth )
, where depth is a nonnegative
integer, computes for every vector B[i]
the initial part
sum_{k=0}^{<depth>} x_k p^k (all x_k integer vectors with entries
bounded by pmfrac{p-1}{2}). The prime p is 83 first; if the
reduction of A modulo p is singular, the next prime is chosen
automatically.
A list X is returned. If the computed initial part really is a
solution of x * A = B[i]
, we have X[i] = x
, otherwise
X[i] = false
.
Decomposition( A, B, "nonnegative" )
assumes that the solutions
have only nonnegative entries, and that the first column of A consists
of positive integers. In this case the necessary number depth of
iterations is computed; the i
-th entry of the returned list is false
if there exists no nonnegative integral solution of the system x *
A = B[i]
, and it is the solution otherwise.
If A is singular, an error is signalled.
gap> a5:= CharTable( "A5" );; a5m3:= CharTable( "A5mod3" );; gap> a5m3.irreducibles; [ [ 1, 1, 1, 1 ], [ 3, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 3, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, -1, -1 ] ] gap> reg:= CharTableRegular( a5, 3 );; gap> chars:= Restricted( a5, reg, a5.irreducibles ); [ [ 1, 1, 1, 1 ], [ 3, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 3, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, -1, -1 ], [ 5, 1, 0, 0 ] ] gap> Decomposition( a5m3.irreducibles, chars, "nonnegative" ); [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ], [ 1, 0, 0, 1 ] ] gap> last * a5m3.irreducibles = chars; true
Let A be a square integral matrix, p an odd prime. The reduction of A modulo p is overline{A}, its entries are chosen in the interval [-frac{p-1}{2}, frac{p-1}{2}]. If overline{A} is regular over the field with p elements, we can form A^{prime} = overline{A}^{-1}. Now consider the integral linear equation system x A = b, i.e., we look for an integral solution x. Define b_0 = b, and then iteratively compute
[ x_i = (b_i A^prime) bmod p, b_i+1 = frac1p (b_i - x_i A) mboxrm for i = 0, 1, 2, ldots . ]
By induction, we get
[ p^i+1 b_i+1 + ( sum_j=0^i p^j x_j ) A = b . ]
If there is an integral solution x, it is unique, and there is an index l such that b_{l+1} is zero and x = sum_{j=0}^{l} p^j x_j.
There are two useful generalizations. First, A need not be square; it is only necessary that there is a square regular matrix formed by a subset of columns. Second, A does not need to be integral; the entries may be cyclotomic integers as well, in this case one has to replace each column of A by the columns formed by the coefficients (which are integers). Note that this preprocessing must be performed compatibly for A and b.
And these are the subroutines called by Decomposition
:
LinearIndependentColumns( A )
returns for a matrix A a maximal list lic of positions such that the
rank of List( A, x - Sublist( x, lic ) )
is the same as the rank
of A.
InverseMatMod( A, p )
returns for a square integral matrix A and a prime p a matrix
A^{prime} with the property that A^{prime} A is congruent to the
identity matrix modulo p; if A is singular modulo p, false
is
returned.
PadicCoefficients( A, Amodpinv, b, p, depth )
returns the list [ x_0, x_1, ldots, x_l, b_{l+1} ] where l = <depth> or l is minimal with the property that b_{l+1} = 0.
IntegralizedMat( A )
IntegralizedMat( A, inforec )
return for a matrix A of cyclotomics a record intmat with components
mat
and inforec
. Each family of galois conjugate columns of A is
encoded in a set of columns of the rational matrix intmat.mat
by
replacing cyclotomics by their coefficients. intmat.inforec
is a
record containing the information how to encode the columns.
If the only argument is A, the component inforec
is computed that can
be entered as second argument inforec in a later call of
IntegralizedMat
with a matrix B that shall be encoded compatible with
A.
DecompositionInt( A, B, depth )
does the same as Decomposition
(see Decomposition), but only for
integral matrices A, B, and nonnegative integers depth.
KernelChar( char )
returns the set of classes which form the kernel of the character char, i.e. the set of positions i with <char>[i] = <char>[1].
For a factor fusion map fus, KernelChar( fus )
is the kernel of the
epimorphism.
gap> s4:= CharTable( "Symmetric", 4 );; gap> s4.irreducibles; [ [ 1, -1, 1, 1, -1 ], [ 3, -1, -1, 0, 1 ], [ 2, 0, 2, -1, 0 ], [ 3, 1, -1, 0, -1 ], [ 1, 1, 1, 1, 1 ] ] gap> List( last, KernelChar ); [ [ 1, 3, 4 ], [ 1 ], [ 1, 3 ], [ 1 ], [ 1, 2, 3, 4, 5 ] ]
PrimeBlocks( tbl, prime )
PrimeBlocks( tbl, chars, prime )
For a character table tbl and a prime prime, PrimeBlocks( tbl,
chars, prime )
returns a record with fields
block
:chars[i]
belongs to the n-th prime-block
defect
:
PrimeBlocks( tbl, prime )
does the same for chars =
tbl.irreducibles
, and additionally the result is stored in the
irredinfo
field of tbl.
gap> t:= CharTable( "A5" );; gap> PrimeBlocks( t, 2 ); PrimeBlocks( t, 3 ); PrimeBlocks( t, 5 ); rec( block := [ 1, 1, 1, 2, 1 ], defect := [ 2, 0 ] ) rec( block := [ 1, 2, 3, 1, 1 ], defect := [ 1, 0, 0 ] ) rec( block := [ 1, 1, 1, 1, 2 ], defect := [ 1, 0 ] ) gap> InverseMap( last.block ); # distribution of characters to blocks [ [ 1, 2, 3, 4 ], 5 ]
If InfoCharTable2 = Print
, the defects of the blocks and the heights of
the contained characters are printed.
Indicator( tbl, n )
Indicator( tbl, chars, n )
Indicator( modtbl, 2 )
For a character table tbl, Indicator( tbl, chars, n )
returns
the list of n-th Frobenius Schur indicators for the list chars of
characters.
Indicator( tbl, n )
does the same for chars =
tbl.irreducibles
, and additionally the result is stored in the field
irredinfo
of tbl.
Indicator( modtbl, 2 )
returns the list of 2nd indicators for the
irreducible characters of the Brauer character table modtbl and stores
the indicators in the irredinfo
component of modtbl; this does not
work for tables in characteristic 2.
gap> t:= CharTable( "M11" );; Indicator( t, t.irreducibles, 2 ); [ 1, 1, 0, 0, 1, 0, 0, 1, 1, 1 ]
Eigenvalues( tbl, char, class )
Let M be a matrix of a representation with character char which is a
character of the table tbl, for an element in the conjugacy class
class. Eigenvalues( tbl, char, class )
returns a list of
length n = tbl.orders[ class ]
where at position i
the
multiplicity of E(n)^i = e^{frac{2pi i}{n}}
as eigenvalue of M
is stored.
gap> t:= CharTable( "A5" );; gap> chi:= t.irreducibles[2]; [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ] gap> List( [ 1 .. 5 ], i -> Eigenvalues( t, chi, i ) ); [ [ 3 ], [ 2, 1 ], [ 1, 1, 1 ], [ 0, 1, 1, 0, 1 ], [ 1, 0, 0, 1, 1 ] ]
List( [1..n], i - E(n)^i) * Eigenvalues(tbl,char,class) )
is equal to char[ class ]
.
MolienSeries( psi )
MolienSeries( psi, chi )
MolienSeries( tbl, psi )
MolienSeries( tbl, psi, chi )
returns a record that describes the series [ M_psi,chi(z) = sum_d=0^infty (chi,psi^[d]) z^d ] where psi^{[d]} denotes the symmetrization of psi with the trivial character of the symmetric group S_d (see SymmetricParts).
psi and chi must be characters of the table tbl, the default for chi is the trivial character. If no character table is given, psi and chi must be class function recods.
ValueMolienSeries( series, i )
returns the i-th coefficient of the Molien series series.
gap> psi:= Irr( CharTable( "A5" ) )[3]; Character( CharTable( "A5" ), [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ] ) gap> mol:= MolienSeries( psi );; gap> List( [ 1 .. 10 ], i -> ValueMolienSeries( mol, i ) ); [ 0, 1, 0, 1, 0, 2, 0, 2, 0, 3 ]
The record returned by MolienSeries
has components
summands
:numer
, r
, and k
,
describing the summand 'numer' / (1-z^r)^k,
size
:size
component of the character table,
degree
:Reduced( tbl, constituents, reducibles )
Reduced( tbl, reducibles )
returns a record with fields remainders
and irreducibles
, both
lists: Let rems
be the set of nonzero characters obtained from
reducibles by subtraction of
[ sum_chiin constituents
fracScalarProduct( tbl, chi, reducibles[i] )
ScalarProduct( tbl, chi, constituents[j] )
cdot chi ]
from reducibles[i]
in the first case or subtraction of
[ sum_j leq i
fracScalarProduct( tbl, reducibles[j], reducibles[i] )
ScalarProduct( tbl, reducibles[j], reducibles[j] )
cdot reducibles[j] ]
in the second case.
Let irrs
be the list of irreducible characters in rems
. rems
is
reduced with irrs
and all found irreducibles until no new irreducibles
are found. Then irreducibles
is the set of all found irreducible
characters, remainders
is the set of all nonzero remainders.
If one knows that reducibles are ordinary characters of tbl and
constituents are irreducible ones, ReducedOrdinary ReducedOrdinary
may be faster.
Note that elements of remainders
may be only virtual characters even if
reducibles are ordinary characters.
gap> t:= CharTable( "A5" );; gap> chars:= Sublist( t.irreducibles, [ 2 .. 4 ] );; gap> chars:= Set( Tensored( chars, chars ) );; gap> Reduced( t, chars ); rec( remainders := [ ], irreducibles := [ [ 1, 1, 1, 1, 1 ], [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ] ] )
ReducedOrdinary( tbl, constituents, reducibles )
works like Reduced Reduced
, but assumes that the elements of
constituents and reducibles are ordinary characters of the character
table tbl. So scalar products are calculated only for those pairs of
characters where the degree of the constituent is smaller than the degree
of the reducible.
Tensored( chars1, chars2 )
returns the list of tensor products (i.e. pointwise products) of all characters in the list chars1 with all characters in the list chars2.
gap> t:= CharTable( "A5" );; gap> chars1:= Sublist( t.irreducibles, [ 1 .. 3 ] );; gap> chars2:= Sublist( t.irreducibles, [ 2 .. 3 ] );; gap> Tensored( chars1, chars2 ); [ [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 9, 1, 0, -2*E(5)-E(5)^2-E(5)^3-2*E(5)^4, -E(5)-2*E(5)^2-2*E(5)^3-E(5)^4 ], [ 9, 1, 0, -1, -1 ], [ 9, 1, 0, -1, -1 ], [ 9, 1, 0, -E(5)-2*E(5)^2-2*E(5)^3-E(5)^4, -2*E(5)-E(5)^2-E(5)^3 -2*E(5)^4 ] ]
Note that duplicate tensor products are not deleted; the tensor product
of chars1[i]
with chars2[j]
is stored at position (i-1)
'Length( <chars1> )' + j.
Symmetrisations( tbl, chars, Sn )
Symmetrisations( tbl, chars, n )
returns the list of nonzero symmetrisations of the characters chars, regarded as characters of the character table tbl, with the ordinary characters of the symmetric group of degree n; alternatively, the table of the symmetric group can be entered as Sn.
The symmetrisation chi^{[lambda]} of the character chi of tbl with the character lambda of the symmetric group S_n of degree n is defined by
[ chi^[lambda](g) = frac1n! sum_rho in S_n lambda(rho) prod_k=1^n chi(g^k)^a_k(rho), ]
where a_k(rho) is the number of cycles of length k in rho.
For special symmetrisations, see SymmetricParts, AntiSymmetricParts, MinusCharacter and OrthogonalComponents, SymplecticComponents.
gap> t:= CharTable( "A5" );; gap> chars:= Sublist( t.irreducibles, [ 1 .. 3 ] );; gap> Symmetrisations( t, chars, 3 ); [ [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 1, 1 ], [ 8, 0, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 10, -2, 1, 0, 0 ], [ 1, 1, 1, 1, 1 ], [ 8, 0, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 10, -2, 1, 0, 0 ] ]
Note that the returned list may contain zero characters, and duplicate characters are not deleted.
SymmetricParts( tbl, chars, n )
returns the list of symmetrisations of the characters chars, regarded as characters of the character table tbl, with the trivial character of the symmetric group of degree n (see Symmetrisations).
gap> t:= CharTable( "A5" );; gap> SymmetricParts( t, t.irreducibles, 3 ); [ [ 1, 1, 1, 1, 1 ], [ 10, -2, 1, 0, 0 ], [ 10, -2, 1, 0, 0 ], [ 20, 0, 2, 0, 0 ], [ 35, 3, 2, 0, 0 ] ]
AntiSymmetricParts( tbl, chars, n )
returns the list of symmetrisations of the characters chars, regarded as characters of the character table tbl, with the alternating character of the symmetric group of degree n (see Symmetrisations).
gap> t:= CharTable( "A5" );; gap> AntiSymmetricParts( t, t.irreducibles, 3 ); [ [ 0, 0, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 1, 1 ], [ 4, 0, 1, -1, -1 ], [ 10, -2, 1, 0, 0 ] ]
MinusCharacter( char, prime_powermap, prime )
Maps and Parametrized Maps) character chi^{p-} for the character chi = <char> and a prime p = <prime>, where chi^{p-} is defined by chi^{p-}(g) = ( chi(g)^p - chi(g^p) ) / p, and prime_powermap is the (possibly parametrized) p-th powermap.
gap> t:= CharTable( "S7" );; pow:= InitPowermap( t, 2 );; gap> Congruences( t, t.irreducibles, pow, 2 );; pow; [ 1, 1, 3, 4, [ 2, 9, 10 ], 6, 3, 8, 1, 1, [ 2, 9, 10 ], 3, 4, 6, [ 7, 12 ] ] gap> chars:= Sublist( t.irreducibles, [ 2 .. 5 ] );; gap> List( chars, x-> MinusCharacter( x, pow, 2 ) ); [ [ 0, 0, 0, 0, [ 0, 1 ], 0, 0, 0, 0, 0, [ 0, 1 ], 0, 0, 0, [ 0, 1 ] ], [ 15, -1, 3, 0, [ -2, -1, 0 ], 0, -1, 1, 5, -3, [ 0, 1, 2 ], -1, 0, 0, [ 0, 1 ] ], [ 15, -1, 3, 0, [ -1, 0, 2 ], 0, -1, 1, 5, -3, [ 1, 2, 4 ], -1, 0, 0, 1 ], [ 190, -2, 1, 1, [ 0, 2 ], 0, 1, 1, -10, -10, [ 0, 2 ], -1, -1, 0, [ -1, 0 ] ] ]
OrthogonalComponents( tbl, chars, m )
If chi is a (nonlinear) character with indicator +1, a splitting of the tensor power chi^m is given by the so-called Murnaghan functions (see~Mur58). These components in general have fewer irreducible constituents than the symmetrizations with the symmetric group of degree m (see Symmetrisations).
OrthogonalComponents
returns the set of orthogonal symmetrisations of
the characters of the character table tbl in the list chars, up to
the power m, where the integer m is one of { 2, 3, 4, 5, 6 }.
Note: It is not checked if all characters in chars do really have indicator +1; if there are characters with indicator 0 or -1, the result might contain virtual characters, see also SymplecticComponents.
The Murnaghan functions are implemented as in~Fra82.
gap> t:= CharTable( "A8" );; chi:= t.irreducibles[2]; [ 7, -1, 3, 4, 1, -1, 1, 2, 0, -1, 0, 0, -1, -1 ] gap> OrthogonalComponents( t, [ chi ], 4 ); [ [ 21, -3, 1, 6, 0, 1, -1, 1, -2, 0, 0, 0, 1, 1 ], [ 27, 3, 7, 9, 0, -1, 1, 2, 1, 0, -1, -1, -1, -1 ], [ 105, 1, 5, 15, -3, 1, -1, 0, -1, 1, 0, 0, 0, 0 ], [ 35, 3, -5, 5, 2, -1, -1, 0, 1, 0, 0, 0, 0, 0 ], [ 77, -3, 13, 17, 2, 1, 1, 2, 1, 0, 0, 0, 2, 2 ], [ 189, -3, -11, 9, 0, 1, 1, -1, 1, 0, 0, 0, -1, -1 ], [ 330, -6, 10, 30, 0, -2, -2, 0, -2, 0, 1, 1, 0, 0 ], [ 168, 8, 8, 6, -3, 0, 0, -2, 2, -1, 0, 0, 1, 1 ], [ 35, 3, -5, 5, 2, -1, -1, 0, 1, 0, 0, 0, 0, 0 ], [ 182, 6, 22, 29, 2, 2, 2, 2, 1, 0, 0, 0, -1, -1 ] ]
SymplecticComponents( tbl, chars, m )
If chi is a (nonlinear) character with indicator -1, a splitting of the tensor power chi^m is given in terms of the so-called Murnaghan functions (see~Mur58). These components in general have fewer irreducible constituents than the symmetrizations with the symmetric group of degree m (see Symmetrisations).
SymplecticComponents
returns the set of symplectic symmetrisations of
the characters of the character table tbl in the list chars, up to
the power m, where the integer m is one of { 2, 3, 4, 5 }.
Note: It is not checked if all characters in chars do really have indicator -1; if there are characters with indicator 0 or +1, the result might contain virtual characters, see also OrthogonalComponents.
gap> t:= CharTable( "U3(3)" );; chi:= t.irreducibles[2]; [ 6, -2, -3, 0, -2, -2, 2, 1, -1, -1, 0, 0, 1, 1 ] gap> SymplecticComponents( t, [ chi ], 4 ); [ [ 14, -2, 5, -1, 2, 2, 2, 1, 0, 0, 0, 0, -1, -1 ], [ 21, 5, 3, 0, 1, 1, 1, -1, 0, 0, -1, -1, 1, 1 ], [ 64, 0, -8, -2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 ], [ 14, 6, -4, 2, -2, -2, 2, 0, 0, 0, 0, 0, -2, -2 ], [ 56, -8, 2, 2, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0 ], [ 70, -10, 7, 1, 2, 2, 2, -1, 0, 0, 0, 0, -1, -1 ], [ 189, -3, 0, 0, -3, -3, -3, 0, 0, 0, 1, 1, 0, 0 ], [ 90, 10, 9, 0, -2, -2, -2, 1, -1, -1, 0, 0, 1, 1 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 126, 14, -9, 0, 2, 2, 2, -1, 0, 0, 0, 0, -1, -1 ] ]
IrreducibleDifferences( tbl, chars1, chars2 )
IrreducibleDifferences( tbl, chars1, chars2, scprmat )
IrreducibleDifferences( tbl, chars, "triangle" )
IrreducibleDifferences( tbl, chars, "triangle", scprmat )
returns the list of irreducible characters which occur as difference of
two elements of chars (if "triangle"
is specified) or of an element
of chars1 and an element of chars2; if scprmat is not specified it
will be computed (see MatScalarProducts), otherwise we must have
[
scprmat[i][j] = ScalarProduct( tbl, chars[i], chars[j] )
]
resp.
[
scprmat[i][j] = ScalarProduct( tbl, chars1[i], chars2[j] )
].
gap> t:= CharTable( "A5" );; gap> chars:= Sublist( t.irreducibles, [ 2 .. 4 ] );; gap> chars:= Set( Tensored( chars, chars ) );; gap> IrreducibleDifferences( t, chars, "triangle" ); [ [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ] ]
Restricted( tbl, subtbl, chars )
Restricted( tbl, subtbl, chars, specification )
Restricted( chars, fusionmap )
returns the restrictions, i.e. the indirections, of the characters in the
list chars by a subgroup fusion map. This map can either be entered
directly as fusionmap, or it must be stored on the character table
subtbl and must have destination tbl; in the latter case the value of
the specification
field of the desired fusion may be specified as
specification (see GetFusionMap). If no such fusion is stored,
false
is returned.
More about Maps and Parametrized Maps); any value that is not uniquely determined in a restricted character is set to an unknown (see Unknown); for parametrized indirection of characters, see CompositionMaps.
Restriction and inflation are the same procedures, so Restricted
and
Inflated
are identical, see Inflated.
gap> s5:= CharTable( "A5.2" );; a5:= CharTable( "A5" );; gap> Restricted( s5, a5, s5.irreducibles ); [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 1, 1 ], [ 6, -2, 0, 1, 1 ], [ 4, 0, 1, -1, -1 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ], [ 5, 1, -1, 0, 0 ] ] gap> Restricted( s5.irreducibles, [ 1, 6, 2, 6 ] ); # restrictions to the cyclic group of order 4 [ [ 1, 1, 1, 1 ], [ 1, -1, 1, -1 ], [ 6, 0, -2, 0 ], [ 4, 0, 0, 0 ], [ 4, 0, 0, 0 ], [ 5, -1, 1, -1 ], [ 5, 1, 1, 1 ] ]
Inflated( factortbl, tbl, chars )
Inflated( factortbl, tbl, chars, specification )
Inflated( chars, fusionmap )
returns the inflations, i.e. the indirections of chars by a factor
fusion map. This map can either be entered directly as fusionmap, or
it must be stored on the character table tbl and must have destination
factortbl; in the latter case the value of the specification
field of
the desired fusion may be specified as specification (see
GetFusionMap). If no such fusion is stored, false
is returned.
More about Maps and Parametrized Maps); any value that is not uniquely determined in an inflated character is set to an unknown (see Unknown); for parametrized indirection of characters, see CompositionMaps.
Restriction and inflation are the same procedures, so Restricted
and
Inflated
are identical, see Restricted.
gap> s4:= CharTable( "Symmetric", 4 );; gap> s3:= CharTableFactorGroup( s4, [3] );; gap> s3.irreducibles; [ [ 1, -1, 1 ], [ 2, 0, -1 ], [ 1, 1, 1 ] ] gap> s4.fusions; [ rec( map := [ 1, 2, 1, 3, 2 ], type := "factor", name := [ 'S', '4', '/', '[', ' ', '3', ' ', ']' ] ) ] gap> Inflated( s3, s4, s3.irreducibles ); [ [ 1, -1, 1, 1, -1 ], [ 2, 0, 2, -1, 0 ], [ 1, 1, 1, 1, 1 ] ]
Induced( subtbl, tbl, chars )
Induced( subtbl, tbl, chars, specification )
Induced( subtbl, tbl, chars, fusionmap )
returns a set of characters induced from subtbl to tbl; the elements
of the list chars will be induced. The subgroup fusion map can either
be entered directly as fusionmap, or it must be stored on the table
subtbl and must have destination tbl; in the latter case the value of
the specification
field may be specified by specification (see
GetFusionMap). If no such fusion is stored, false
is returned.
More about Maps and Parametrized Maps); any value that is not uniquely determined in an induced character is set to an unknown (see Unknown).
gap> Induced( a5, s5, a5.irreducibles ); [ [ 2, 2, 2, 2, 0, 0, 0 ], [ 6, -2, 0, 1, 0, 0, 0 ], [ 6, -2, 0, 1, 0, 0, 0 ], [ 8, 0, 2, -2, 0, 0, 0 ], [ 10, 2, -2, 0, 0, 0, 0 ] ]
InducedCyclic( tbl )
InducedCyclic( tbl, "all" )
InducedCyclic( tbl, classes )
InducedCyclic( tbl, classes, "all" )
returns a set of characters of the character table tbl. They are
characters induced from cyclic subgroups of tbl. If "all"
is
specified, all irreducible characters of those subgroups are induced,
otherwise only the permutation characters are computed. If a list
classes is specified, only those cyclic subgroups generated by these
classes are considered, otherwise all classes of tbl are considered.
Note that the powermaps for primes dividing tbl.order
must be stored
on tbl; if any powermap for a prime not dividing tbl.order
that is
smaller than the maximal representative order is not stored, this map
will be computed (see Powermap) and stored afterwards.
More about Maps and Parametrized Maps); any value that is not uniquely determined in an induced character is set to an unknown (see Unknown). The representative orders of the classes to induce from must not be parametrized (see More about Maps and Parametrized Maps).
gap> t:= CharTable( "A5" );; InducedCyclic( t, "all" ); [ [ 12, 0, 0, 2, 2 ], [ 12, 0, 0, E(5)^2+E(5)^3, E(5)+E(5)^4 ], [ 12, 0, 0, E(5)+E(5)^4, E(5)^2+E(5)^3 ], [ 20, 0, -1, 0, 0 ], [ 20, 0, 2, 0, 0 ], [ 30, -2, 0, 0, 0 ], [ 30, 2, 0, 0, 0 ], [ 60, 0, 0, 0, 0 ] ]
CollapsedMat( mat, maps )
returns a record with fields mat
and fusion
: The fusion
field
contains the fusion that collapses the columns of mat that are
identical also for all maps in the list maps, the mat
field contains
the image of mat under that fusion.
gap> t.irreducibles; [ [ 1, 1, 1, 1, 1 ], [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ] ] gap> t:= CharTable( "A5" );; RationalizedMat( t.irreducibles ); [ [ 1, 1, 1, 1, 1 ], [ 6, -2, 0, 1, 1 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ] ] gap> CollapsedMat( last, [] ); rec( mat := [ [ 1, 1, 1, 1 ], [ 6, -2, 0, 1 ], [ 4, 0, 1, -1 ], [ 5, 1, -1, 0 ] ], fusion := [ 1, 2, 3, 4, 4 ] ) gap> Restricted( last.mat, last.fusion ); [ [ 1, 1, 1, 1, 1 ], [ 6, -2, 0, 1, 1 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ] ]
Power( powermap, chars, n )
returns the list of indirections of the characters chars by the n-th powermap; for a character chi in chars, this indirection is often called chi^{(n)}. The powermap is calculated from the (necessarily stored) powermaps of the prime divisors of n if it is not stored in powermap (see Powmap).
Note that chi^{(n)} is in general only a virtual characters.
gap> t:= CharTable( "A5" );; Power( t.powermap, t.irreducibles, 2 ); [ [ 1, 1, 1, 1, 1 ], [ 3, 3, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 3, 3, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 4, 4, 1, -1, -1 ], [ 5, 5, -1, 0, 0 ] ] gap> MatScalarProducts( t, t.irreducibles, last ); [ [ 1, 0, 0, 0, 0 ], [ 1, -1, 0, 0, 1 ], [ 1, 0, -1, 0, 1 ], [ 1, -1, -1, 1, 1 ], [ 1, -1, -1, 0, 2 ] ]
For groups H, G with Hleq G, the induced character (1_G)^H is called the permutation character of the operation of G on the right cosets of H. If only the character table of G is known, one can try to get informations about possible subgroups of G by inspection of those characters pi which might be permutation characters, using that such a character must have at least the following properties:
Any character with these properties will be called a permutation character candidate from now on.
GAP provides some algorithms to compute permutation character
candidates, see PermChars. Some information about the subgroup can
computed from a permutation character using PermCharInfo
(see
PermCharInfo).
IsPermChar( tbl, pi )
missing, like tests TestPerm1
, TestPerm2
, TestPerm3
PermCharInfo( tbl, permchars )
Let tbl be the character table of the group G, and permchars the
permutation character (1_U)^G for a subgroup U of G, or a list of
such characters. PermCharInfo
returns a record with components
contained
:
bound
:permchars[k]
be the permutation character (1_U)^G. Then the
class length in U of an element in class i of tbl must be a
multiple of the value
'bound[<k>][<i>]' = |U| / gcd( |U|, '<tbl>.centralizers[<i>]' ),
display
:DisplayCharTable
to display the permutation characters and the corresponding components
contained
and bound
, for the classes where at least one character
of permchars is nonzero,
ATLAS
:tbl.irreducibles
in ATLAS notation.
gap> t:= CharTable("A6");; gap> PermCharInfo( t, [ 15, 3, 0, 3, 1, 0, 0 ] ); rec( contained := [ [ 1, 9, 0, 8, 6, 0, 0 ] ], bound := [ [ 1, 3, 8, 8, 6, 24, 24 ] ], display := rec( classes := [ 1, 2, 4, 5 ], chars := [ [ 15, 3, 0, 3, 1, 0, 0 ], [ 1, 9, 0, 8, 6, 0, 0 ], [ 1, 3, 8, 8, 6, 24, 24 ] ], letter := "I" ), ATLAS := [ "1a+5b+9a" ] ) gap> DisplayCharTable( t, last.display ); A62 3 3 . 2 3 2 . 2 . 5 1 . . .
1a 2a 3b 4a 2P 1a 1a 3b 2a 3P 1a 2a 1a 4a 5P 1a 2a 3b 4a
I.1 15 3 3 1 I.2 1 9 8 6 I.3 1 3 8 6
Inequalities( tbl )
The condition pi(g) geq 0 for every permutation character candidate pi places restrictions on the multiplicities a_i of the irreducible constituents chi_i of pi = sum_{i=1}^r a_i chi_i. For every group element g holds sum_{i=1}^r a_i chi_i(g) geq 0. The power map provides even stronger conditions.
This system of inequalities is kind of diagonalized, resulting in a
system of inequalities restricting a_i in terms of a_j, j < i.
These inequalities are used to construct characters with nonnegative
values (see PermChars). PermChars
either calls Inequalities
or
takes this information from the record field ineq
of its argument
record.
The number of inequalities arising in the process of diagonalization may grow very strong.
There are two strategies to perform this diagonalization. The default is to simply eliminate one unknown a_i after the other with decreasing i. In some cases it turns out to be better first to look which choice for the next unknown will yield the fewest new inequalities.
PermBounds( tbl, d )
All characters pi satisfying pi(g) > 0 and pi(1) = d for a given
degree d lie in a simplex described by these conditions. PermBounds
computes the boundary points of this simplex for d = 0, from which the
boundary points for any other d are easily derived. Some conditions
from the powermap are also involved.
For this purpose a matrix similar to the rationalized character table has to be inverted.
These boundary points are used by PermChars
(see PermChars) to
construct all permutation character candidates of a given degree.
PermChars
either calls PermBounds
or takes this information from the
record field bounds
of its argument record.
PermChars( tbl )
PermChars( tbl, degree )
PermChars( tbl, arec )
GAP provides several algorithms to determine permutation character candidates from a given character table. The algorithm is selected from the choice of the record fields of the optional argument record arec. The user is encouraged to try different approaches especially if one choice fails to come to an end.
Regardless of the algorithm used in a special case, PermChars
returns a
list of all permutation character candidates with the properties given
in arec. There is no guarantee that a character of this list is in
fact a permutation character. But an empty list always means there is no
permutation character with these properties (e.g. of a certain degree).
In the first form PermChars( tbl )
returns the list of all
permutation characters of the group with character table tbl. This list
might be rather long for big groups, and it might take much time. The
algorithm depends on a preprocessing step, where the inequalities arising
from the condition pi(g) leq 0 are transformed into a system of
inequalities that guides the search (see Inequalities).
gap> m11:= CharTable("M11");; gap> PermChars(m11);; # will return the list of 39 permutation # character candidates of $M11$.
There are two different search strategies for this algorithm. One simply
constructs all characters with nonnegative values and then tests for each
such character whether its degree is a divisor of the order of the group.
This is the default. The other strategy uses the inequalities to predict
if it is possible to find a character of a certain degree in the
currently searched part of the search tree. To choose this strategy set
the field mode
of arec to "preview"
and the field degree
to the
degree (or a list of degrees which might be all divisors of the order of
the group) you want to look for. The record field ineq
can take the
inequalities from Inequalities
if they are needed more than once.
In the second form PermChars( tbl, degree )
returns the list of all
permutation characters of degree degree. For that purpose a
preprocessing step is performed where essentially the rationalized
character table is inverted in order to determine boundary points for the
simplex in which the permutation character candidates of a given degree
must lie (see PermBounds). Note that inverting big integer matrices
needs a lot of time and space. So this preprocessing is restricted to
groups with less than 100 classes, say.
gap> PermChars(m11, 220); [ [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ], [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ], [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ]
In the third form PermChars( tbl, arec )
returns the list of all
permutation characters which have the properties given in the argument
record arec. If arec contains a degree in the record field degree
then PermChars
will behave exactly as in the second form.
gap> PermChars(m11, rec(degree:= 220)); [ [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ], [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ], [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ]
Alternatively arec may have the record fields chars
and torso
.
arec.chars
is a list of (in most cases all) rational irreducible
characters of tbl which might be constituents of the required
characters, and arec.torso
is a list that contains some known values
of the required characters at the right positions.
Note: At least the degree arec.torso[1]
must be an integer. If
arec.chars
does not contain all rational irreducible characters of
G, it may happen that any scalar product of pi with an omitted
character is negative; there should be nontrivial reasons for excluding a
character that is known to be not a constituent of pi.
gap> rat:= RationalizedMat(m11.irreducibles);; gap> PermChars(m11, rec(torso:= [220], chars:= rat)); [ [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ], [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ], [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ] ] gap> PermChars(m11, rec(torso:= [220,,,,,2], chars:= rat)); [ [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ]
PermChars( tbl, arec )
PermChars
may as well determine faithful candidates for permutation
characters. In that case arec requires the fields normalsubgrp
,
nonfaithful
, chars
, lower
, upper
, and torso
.
Let tbl be the character table of the group G, arec.normalsubgrp
a list of classes forming a normal subgroup N of G.
arec.nonfaithful
is a permutation character candidate (see
Permutation Character Candidates) of G with kernel N.
arec.chars
is a list of (in most cases all) rational irreducible
characters of tbl.
PermChars
computes all those permutation character candidates pi
having following properties:
chars
contains every rational irreducible constituent of
pi.
lower
.
upper
.
torso
.
If there exists a subgroup V of G, V geq N, with <nonfaithful> = (1_V)^G, the last condition means that the candidates for those possible subgroups U with V = UN are constructed.
Note: At least the degree <torso>[1] must be an integer. If chars does not contain all rational irreducible characters of G, it may happen that any scalar product of pi with an omitted character is negative; there should be nontrivial reasons for excluding a character that is known to be not a constituent of pi.
LLLReducedBasis([L],vectors[,y][,"linearcomb"])
LLLReducedBasis
provides an implementation of the LLL lattice reduction
algorithm by Lenstra, Lenstra and Lovaccent19 asz (see~LLL82,
Poh87). The implementation follows the description on pages
94f. in~Coh93.
LLLReducedBasis
returns a record whose component basis
is a list of
LLL reduced linearly independent vectors spanning the same lattice as the
list vectors.
L must be a lattice record whose scalar product function is stored in
the component operations.NoMessageScalarProduct
or
operations.ScalarProduct
. It must be a function of three arguments,
namely the lattice and the two vectors. If no lattice L is given the
standard scalar product is taken.
In the case of option "linearcomb"
, the record contains also the
components relations
and transformation
, which have the following
meaning. relations
is a basis of the relation space of vectors,
i.e., of vectors x such that x * vectors
is zero.
transformation
gives the expression of the new lattice basis in terms
of the old, i.e., transformation * vectors
equals the basis
component of the result.
Another optional argument is y, the ``sensitivity'' of the algorithm, a rational number between frac{1}{4} and 1 (the default value is frac{3}{4}).
(The function LLLReducedGramMat computes an LLL reduced Gram matrix.)
gap> vectors:= [ [ 9, 1, 0, -1, -1 ], [ 15, -1, 0, 0, 0 ], > [ 16, 0, 1, 1, 1 ], [ 20, 0, -1, 0, 0 ], > [ 25, 1, 1, 0, 0 ] ];; gap> LLLReducedBasis( vectors, "linearcomb" ); rec( basis := [ [ 1, 1, 1, 1, 1 ], [ 1, 1, -2, 1, 1 ], [ -1, 3, -1, -1, -1 ], [ -3, 1, 0, 2, 2 ] ], relations := [ [ -1, 0, -1, 0, 1 ] ], transformation := [ [ 0, -1, 1, 0, 0 ], [ -1, -2, 0, 2, 0 ], [ 1, -2, 0, 1, 0 ], [ -1, -2, 1, 1, 0 ] ] )
LLLReducedGramMat( G [,y] )
LLLReducedGramMat
provides an implementation of the LLL lattice
reduction algorithm by Lenstra, Lenstra and Lovaccent19 asz
(see~LLL82, Poh87). The implementation follows the
description on pages 94f. in~Coh93.
Let G the Gram matrix of the vectors (b_1, b_2, ldots, b_n); this means G is either a square symmetric matrix or lower triangular matrix (only the entries in the lower triangular half are used by the program).
LLLReducedGramMat
returns a record whose component remainder
is the
Gram matrix of the LLL reduced basis corresponding to (b_1, b_2, ldots,
b_n). If G was a lower triangular matrix then also the remainder
component is a lower triangular matrix.
The result record contains also the components relations
and
transformation
, which have the following meaning.
relations
is a basis of the space of vectors (x_1,x_2,ldots,x_n)
such that sum_{i=1}^n x_i b_i is zero, and transformation
gives the
expression of the new lattice basis in terms of the old, i.e.,
transformation
is the matrix T such that T cdot <G> cdot T^{tr}
is the remainder
component of the result.
The optional argument y denotes the ``sensitivity of the algorithm,
it must be a rational number between frac{1}{4} and 1; the default
value is <y> = frac{3}{4}.
(The function LLLReducedBasis computes an LLL reduced basis.)
gap> g:= [ [ 4, 6, 5, 2, 2 ], [ 6, 13, 7, 4, 4 ], > [ 5, 7, 11, 2, 0 ], [ 2, 4, 2, 8, 4 ], [ 2, 4, 0, 4, 8 ] ];; gap> LLLReducedGramMat( g ); rec( remainder := [ [ 4, 2, 1, 2, -1 ], [ 2, 5, 0, 2, 0 ], [ 1, 0, 5, 0, 2 ], [ 2, 2, 0, 8, 2 ], [ -1, 0, 2, 2, 7 ] ], relation := [ ], transformation := [ [ 1, 0, 0, 0, 0 ], [ -1, 1, 0, 0, 0 ], [ -1, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ -2, 0, 1, 0, 1 ] ], scalarproducts := [ , [ 1/2 ], [ 1/4, -1/8 ], [ 1/2, 1/4, -2/25 ], [ -1/4, 1/8, 37/75, 8/21 ] ], bsnorms := [ 4, 4, 75/16, 168/25, 32/7 ] )
LLL( tbl, characters [, y] [, "sort"] [, "linearcomb"] )
calls the LLL algorithm (see LLLReducedBasis) in the case of lattices
spanned by (virtual) characters characters of the character table tbl
(see ScalarProduct). By finding shorter vectors in the lattice spanned
by characters, i.e. virtual characters of smaller norm, in some cases
LLL
is able to find irreducible characters.
LLL
returns a record with at least components irreducibles
(the list
of found irreducible characters), remainders
(a list of reducible
virtual characters), and norms
(the list of norms of remainders
).
irreducibles
together with remainders
span the same lattice as
characters.
There are some optional parameters:
"sort"
:LLL
sorts characters and the remainders
component of the
result according to the degrees.
"linearcomb"
:irreddecomp
and reddecomp
which are decomposition matrices of irreducibles
and remainders
, with respect to characters.
gap> s4:= CharTable( "Symmetric", 4 );; gap> chars:= [ [ 8, 0, 0, -1, 0 ], [ 6, 0, 2, 0, 2 ], > [ 12, 0, -4, 0, 0 ], [ 6, 0, -2, 0, 0 ], [ 24, 0, 0, 0, 0 ], > [ 12, 0, 4, 0, 0 ], [ 6, 0, 2, 0, -2 ], [ 12, -2, 0, 0, 0 ], > [ 8, 0, 0, 2, 0 ], [ 12, 2, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ] ];; gap> LLL( s4, chars ); rec( irreducibles := [ [ 2, 0, 2, -1, 0 ], [ 1, 1, 1, 1, 1 ], [ 3, 1, -1, 0, -1 ], [ 3, -1, -1, 0, 1 ], [ 1, -1, 1, 1, -1 ] ], remainders := [ ], norms := [ ] )
OrthogonalEmbeddings( G [, "positive" ] [, maxdim ] )
computes all possible orthogonal embeddings of a lattice given by its Gram matrix G which must be a regular matrix (see LLLReducedGramMat). In other words, all solutions X of the problem
[ X^tr X = G ]
are calculated (see~Ple90). Usually there are many solutions X
but all their rows are chosen from a small set of vectors, so
OrthogonalEmbeddings
returns the solutions in an encoded form, namely
as a record with components
vectors
:
norms
:
solutions
:Sublist( L, S[i] )
, so the dimension of the
i--th solution is the length of S[i]
.
The optional argument "positive"
will cause OrthogonalEmbeddings
to
compute only vectors x_i with nonnegative entries. In the context of
characters this is allowed (and useful) if G is the matrix of scalar
products of ordinary characters.
When OrthogonalEmbeddings
is called with the optional argument maxdim
(a positive integer), it computes only solutions up to dimension
maxdim; this will accelerate the algorithm in some cases.
G may be the matrix of scalar products of some virtual characters.
From the characters and the embedding given by the matrix X,
Decreased
(see Decreased) may be able to compute irreducibles.
gap> b := [ [ 3, -1, -1 ], [ -1, 3, -1 ], [ -1, -1, 3 ] ];; gap> c:=OrthogonalEmbeddings(b); rec( vectors := [ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ], [ -1, 1, 0 ], [ -1, 0, 1 ], [ 1, 0, 0 ], [ 0, -1, 1 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], norms := [ 1, 1, 1, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2 ], solutions := [ [ 1, 2, 3 ], [ 1, 6, 6, 7, 7 ], [ 2, 5, 5, 8, 8 ], [ 3, 4, 4, 9, 9 ], [ 4, 5, 6, 7, 8, 9 ] ] ) gap> Sublist( c.vectors, c.solutions[1] ); [ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ] ]
OrthogonalEmbeddingsSpecialDimension
( tbl, reducibles, grammat [, "positive" ], dim )
This form can be used if you want to find irreducible characters of the
table tbl, where reducibles is a list of virtual characters,
grammat is the matrix of their scalar products, and dim is the
maximal dimension of an embedding. First all solutions up to dim are
compute, and then Decreased Decreased
is called in order to find
irreducible characters of tab.
If reducibles consists of ordinary characters only, you should enter
the optional argument "positive"
; this imposes some conditions on the
possible embeddings (see the description of OrthogonalEmbeddings
).
OrthogonalEmbeddingsSpecialDimension
returns a record with components
irreducibles
:Decreased
, for all
possible embeddings, and
remainders
:
gap> s6:= CharTable( "Symmetric", 6 );; gap> b:= InducedCyclic( s6, "all" );; gap> Add( b, [1,1,1,1,1,1,1,1,1,1,1] ); gap> c:= LLL( s6, b ).remainders;; gap> g:= MatScalarProducts( s6, c, c );; gap> d:= OrthogonalEmbeddingsSpecialDimension( s6, c, g, 8 ); rec( irreducibles := [ [ 5, -3, 1, 1, 2, 0, -1, -1, -1, 0, 1 ], [ 5, 1, 1, -3, -1, 1, 2, -1, -1, 0, 0 ], [ 10, -2, -2, 2, 1, 1, 1, 0, 0, 0, -1 ], [ 10, 2, -2, -2, 1, -1, 1, 0, 0, 0, 1 ] ], remainders := [ [ 0, 4, 0, -4, 3, 1, -3, 0, 0, 0, -1 ], [ 4, 0, 0, 4, -2, 0, 1, -2, 2, -1, 1 ], [ 6, 2, 2, -2, 3, -1, 0, 0, 0, 1, -2 ], [ 14, 6, 2, 2, 2, 0, -1, 0, 0, -1, -1 ] ] )
ShortestVectors( G, m )
ShortestVectors( G, m, "positive" )
computes all vectors x with x G x^{tr} leq m, where G is a matrix
of a symmetric bilinear form, and m is a nonnegative integer. If the
optional argument "positive"
is entered, only those vectors x with
nonnegative entries are computed.
ShortestVectors
returns a record with components
vectors
:
norms
:
gap> g:= [ [ 2, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ] ];; gap> ShortestVectors(g,4); rec( vectors := [ [ -1, 1, 1 ], [ 0, 0, 1 ], [ -1, 0, 1 ], [ 1, -1, 1 ], [ 0, -1, 1 ], [ -1, -1, 1 ], [ 0, 1, 0 ], [ -1, 1, 0 ], [ 1, 0, 0 ] ], norms := [ 4, 2, 2, 4, 2, 4, 2, 2, 2 ] )
This algorithm is used in OrthogonalEmbeddings OrthogonalEmbeddings
.
Extract( tbl, reducibles, grammat )
Extract( tbl, reducibles, grammat, missing )
tries to find irreducible characters by drawing conclusions out of a
given matrix grammat of scalar products of the reducible characters in
the list reducibles, which are characters of the table tbl.
Extract
uses combinatorial and backtrack means.
Note: Extract
works only with ordinary characters!
Extract
may be accelerated by the specification of
missing.
Extract
returns a record extr with components solution
and choice
where solution
is a list [ M_1, ldots, M_n ] of decomposition
matrices that satisfy the equation [ M_i^tr cdot X = Sublist(
reducibles, extr.choice[i] )
, ] for a matrix X of irreducible
characters, and choice
is a list of length n whose entries are lists
of indices.
So each column stands for one of the reducible input characters, and each
row stands for an irreducible character. You can use Decreased
Decreased
to examine the solution for computable irreducibles.
gap> s4 := CharTable( "Symmetric", 4 );; gap> y := [ [ 5, 1, 5, 2, 1 ], [ 2, 0, 2, 2, 0 ], [ 3, -1, 3, 0, -1 ], > [ 6, 0, -2, 0, 0 ], [ 4, 0, 0, 1, 2 ] ];; gap> g := MatScalarProducts( s4, y, y ); [ [ 6, 3, 2, 0, 2 ], [ 3, 2, 1, 0, 1 ], [ 2, 1, 2, 0, 0 ], [ 0, 0, 0, 2, 1 ], [ 2, 1, 0, 1, 2 ] ] gap> e:= Extract( s4, y, g, 5 ); rec( solution := [ [ [ 1, 1, 0, 0, 2 ], [ 1, 0, 1, 0, 1 ], [ 0, 1, 0, 1, 0 ], [ 0, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 0 ] ] ], choice := [ [ 2, 5, 3, 4, 1 ] ] ) # continued in 'Decreased' ( see "Decreased" )
Decreased( tbl, reducibles, mat )
Decreased( tbl, reducibles, mat, choice )
tries to solve the output of OrthogonalEmbeddings
OrthogonalEmbeddings
or Extract Extract
in order to find
irreducible characters. tbl must be a character table, reducibles
the list of characters used for the call of OrtgogonalEmbeddings
or
Extract
, mat one solution, and in the case of a solution returned by
Extract
, choice
must be the corresponding choice
component.
Decreased
returns a record with components
irreducibles
:
remainders
:
matrix
:remainders
component, which could not be solved.
# see example in "Extract" 'Extract' gap> d := Decreased( s4, y, e.solution[1], e.choice[1] ); rec( irreducibles := [ [ 1, 1, 1, 1, 1 ], [ 3, -1, -1, 0, 1 ], [ 1, -1, 1, 1, -1 ], [ 3, 1, -1, 0, -1 ], [ 2, 0, 2, -1, 0 ] ], remainders := [ ], matrix := [ ] )
DnLattice( tbl, grammat, reducibles )
tries to find sublattices isomorphic to root lattices of type D_n (for n geq 5 or n = 4) in a lattice that is generated by the norm 2 characters reducibles, which must be characters of the table tbl. grammat must be the matrix of scalar products of reducibles, i.e., the Gram matrix of the lattice.
DnLattice
is able to find irreducible characters if there is a lattice
with n>4. In the case n = 4 DnLattice
only in some cases finds
irreducibles.
DnLattice
returns a record with components
irreducibles
:
remainders
:
gram
:remainders
.
The remaining reducible characters are transformed into a normalized
form, so that the lattice-structure is cleared up for further treatment.
So DnLattice
might be useful even if it fails to find irreducible
characters.
gap> tbl:= CharTable( "Symmetric", 4 );; gap> y1:=[ [ 2, 0, 2, 2, 0 ], [ 4, 0, 0, 1, 2 ], [ 5, -1, 1, -1, 1 ], > [ -1, 1, 3, -1, -1 ] ];; gap> g1:= MatScalarProducts( tbl, y1, y1 ); [ [ 2, 1, 0, 0 ], [ 1, 2, 1, -1 ], [ 0, 1, 2, 0 ], [ 0, -1, 0, 2 ] ] gap> e:= DnLattice( tbl, g1, y1 ); rec( gram := [ ], remainders := [ ], irreducibles := [ [ 2, 0, 2, -1, 0 ], [ 1, -1, 1, 1, -1 ], [ 1, 1, 1, 1, 1 ], [ 3, -1, -1, 0, 1 ] ] )
DnLatticeIterative( tbl, arec )
was made for iterative use of DnLattice
. arec must be either a list
of characters of the table tbl, or a record with components
remainders
:
norms
:remainders
,
e.g., a record returned by LLL LLL
. DnLatticeIterative
will select
the characters of norm 2, call DnLattice
, reduce the characters with
found irreducibles, call DnLattice
for the remaining characters, and so
on, until no new irreducibles are found.
DnLatticeIterative
returns (like LLL LLL
) a record with components
irreducibles
:
remainders
:
norms
:remainders
.
gap> tbl:= CharTable( "Symmetric", 4 );; gap> y1:= [ [ 2, 0, 2, 2, 0 ], [ 4, 0, 0, 1, 2 ], > [ 5, -1, 1, -1, 1 ], [ -1, 1, 3, -1, -1 ], [ 6, -2, 2, 0, 0 ] ];; gap> DnLatticeIterative( tbl, y1); rec( irreducibles := [ [ 2, 0, 2, -1, 0 ], [ 1, -1, 1, 1, -1 ], [ 1, 1, 1, 1, 1 ], [ 3, -1, -1, 0, 1 ] ], remainders := [ ], norms := [ ] )
ContainedDecomposables( constituents, moduls, parachar, func )
For a list of rational characters constituents and a parametrized
More about Maps and Parametrized Maps), the set of all elements chi of parachar is returned that
satisfy <func>( chi ) (i.e., for that true
is returned) and that
``modulo moduls lie in the lattice spanned by constituents''. This
means they lie in the lattice spanned by constituents and the set {
<moduls>[i]cdot e_i; 1leq ileq n}, where n is the length of
parachar and e_i is the i-th vector of the standard base.
gap> hs:= CharTable("HS");; s:= CharTable("HSM12");; s.identifier; "5:4xa5" gap> rat:= RationalizedMat(s.irreducibles);; gap> fus:= InitFusion( s, hs ); [ 1, [ 2, 3 ], [ 2, 3 ], [ 2, 3 ], 4, 5, 5, [ 5, 6, 7 ], [ 5, 6, 7 ], 9, [ 8, 9 ], [ 8, 9 ], [ 8, 9, 10 ], [ 8, 9, 10 ], [ 11, 12 ], [ 17, 18 ], [ 17, 18 ], [ 17, 18 ], 21, 21, 22, [ 23, 24 ], [ 23, 24 ], [ 23, 24 ], [ 23, 24 ] ] # restrict a rational character of 'hs' by 'fus', # see chapter "Maps and Parametrized Maps"\: gap> rest:= CompositionMaps( hs.irreducibles[8], fus ); [ 231, [ -9, 7 ], [ -9, 7 ], [ -9, 7 ], 6, 15, 15, [ -1, 15 ], [ -1, 15 ], 1, [ 1, 6 ], [ 1, 6 ], [ 1, 6 ], [ 1, 6 ], [ -2, 0 ], [ 1, 2 ], [ 1, 2 ], [ 1, 2 ], 0, 0, 1, 0, 0, 0, 0 ] # all vectors in the lattice\: gap> ContainedDecomposables( rat, s.centralizers, rest, x -> true ); [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, -9, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ] ] # better filter, only characters (see "ContainedCharacters")\: gap> ContainedDecomposables( rat, s.centralizers, rest, > x->NonnegIntScalarProducts(s,s.irreducibles,x) ); [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ] ]
An application of ContainedDecomposables
is ContainedCharacters
ContainedCharacters
.
For another strategy that works also for irrational characters, see ContainedSpecialVectors.
ContainedCharacters( tbl, constituents, parachar )
returns the set of all characters contained in the parametrized rational character parachar (see More about Maps and Parametrized Maps), that modulo centralizer orders lie in the linear span of the rational characters constituents of the character table tbl and that have nonnegative integral scalar products with all elements of constituents.
Note: This does not imply that an element of the returned list is necessary a linear combination of constituents.
gap> s:= CharTable( "HSM12" );; hs:= CharTable( "HS" );; gap> rat:= RationalizedMat( s.irreducibles );; gap> fus:= InitFusion( s, hs );; gap> rest:= CompositionMaps( hs.irreducibles[8], fus );; gap> ContainedCharacters( s, rat, rest ); [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ] ]
ContainedCharacters
calls ContainedDecomposables
ContainedDecomposables
.
ContainedSpecialVectors( tbl, chars, parachar, func )
returns the list of all elements vec of the parametrized character
parachar (see More about Maps and Parametrized Maps), that have
integral norm and integral scalar product with the principal character of
the character table tbl and that satisfy func( tbl, chars, vec
)
, i.e., for that true
is returned.
gap> s:= CharTable( "HSM12" );; hs:= CharTable( "HS" );; gap> fus:= InitFusion( s, hs );; gap> rest:= CompositionMaps( hs.irreducibles[8], fus );; # no further condition\: gap> ContainedSpecialVectors( s, s.irreducibles, rest, > function(tbl,chars,vec) return true; end );; gap> Length( last ); 24 # better filter\:\ those with integral scalar products gap> ContainedSpecialVectors( s, s.irreducibles, rest, > IntScalarProducts ); [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, -9, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ] ] # better filter\:\ the scalar products must be nonnegative gap> ContainedSpecialVectors( s, s.irreducibles, rest, > NonnegIntScalarProducts ); [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ] ]
Special cases of ContainedSpecialVectors
are
ContainedPossibleCharacters ContainedPossibleCharacters
and
ContainedPossibleVirtualCharacters
ContainedPossibleVirtualCharacters
.
ContainedSpecialVectors
successively examines all vectors contained in
parachar, thus it might not be useful if the indeterminateness exceeds
10^6. For another strategy that works for rational characters only,
see ContainedDecomposables.
ContainedPossibleCharacters( tbl, chars, parachar )
returns the list of all elements vec of the parametrized character parachar (see More about Maps and Parametrized Maps), which have integral norm and integral scalar product with the principal character of the character table tbl and nonnegative integral scalar product with all elements of the list chars of characters of tbl.
# see example in "ContainedSpecialVectors" gap> ContainedPossibleCharacters( s, s.irreducibles, rest ); [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ] ]
ContainedPossibleCharacters
calls ContainedSpecialVectors
ContainedSpecialVectors
.
ContainedPossibleCharacters
successively examines all vectors contained
in parachar, thus it might not be useful if the indeterminateness
exceeds 10^6. For another strategy that works for rational characters
only, see ContainedDecomposables.
ContainedPossibleVirtualCharacters( tbl, chars, parachar )
returns the list of all elements vec of the parametrized character parachar (see More about Maps and Parametrized Maps), which have integral norm and integral scalar product with the principal character of the character table tbl and integral scalar product with all elements of the list chars of characters of tbl.
# see example in "ContainedSpecialVectors" gap> ContainedPossibleVirtualCharacters( s, s.irreducibles, rest ); [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, -9, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ], [ 231, 7, -9, 7, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0 ] ]
ContainedPossibleVirtualCharacters
calls ContainedSpecialVectors
ContainedSpecialVectors
.
ContainedPossibleVirtualCharacters
successively examines all vectors
that are contained in parachar, thus it might not be useful if the
indeterminateness exceeds 10^6. For another strategy that works for
rational characters only, see ContainedDecomposables.
GAP 3.4.4