Spracherkennung für: .gi vermutete Sprache: Unknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Thomas Breuer, and Willem de Graaf.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains methods for Lie algebras.
##
#############################################################################
##
#M LieUpperCentralSeries( <L> ) . . . . . . . . . . for a Lie algebra
##
InstallMethod( LieUpperCentralSeries,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local S, # upper central series of <L>, result
C, # Lie centre
hom; # homomorphisms of <L> to `<L>/<C>'
S := [ TrivialSubalgebra( L ) ];
C := LieCentre( L );
while C <> Last(S) do
# Replace `L' by `L / C', compute its centre, and get the preimage
# under the natural homomorphism.
Add( S, C );
hom:= NaturalHomomorphismByIdeal( L, C );
C:= PreImages( hom, LieCentre( Range( hom ) ) );
#T we would like to get ideals!
#T is it possible to teach the hom. that the preimage of an ideal is an ideal?
od;
# Return the series when it becomes stable.
return Reversed( S );
end );
#############################################################################
##
#M LieLowerCentralSeries( <L> ) . . . . . . . . . . for a Lie algebra
##
InstallMethod( LieLowerCentralSeries,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local S, # lower central series of <L>, result
C; # commutator subalgebras
# Compute the series by repeated calling of `ProductSpace'.
S := [ L ];
C := LieDerivedSubalgebra( L );
while C <> Last(S) do
Add( S, C );
C:= ProductSpace( L, C );
od;
# Return the series when it becomes stable.
return S;
end );
#############################################################################
##
#M LieDerivedSubalgebra( <L> )
##
## is the (Lie) derived subalgebra of the Lie algebra <L>.
## This is the ideal/algebra/subspace (equivalent in this case)
## generated/spanned by all products $uv$
## where $u$ and $v$ range over a basis of <L>.
##
InstallMethod( LieDerivedSubalgebra,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
L -> ProductSpace( L, L ) );
#############################################################################
##
#M LieDerivedSeries( <L> )
##
InstallMethod( LieDerivedSeries,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function ( L )
local S, # (Lie) derived series of <L>, result
D; # (Lie) derived subalgebras
# Compute the series by repeated calling of `LieDerivedSubalgebra'.
S := [ L ];
D := LieDerivedSubalgebra( L );
while D <> Last(S) do
Add( S, D );
D:= LieDerivedSubalgebra( D );
od;
# Return the series when it becomes stable.
return S;
end );
#############################################################################
##
#M IsLieSolvable( <L> ) . . . . . . . . . . . . . . . for a Lie algebra
##
InstallMethod( IsLieSolvable,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local D;
D:= LieDerivedSeries( L );
return Dimension( Last(D) ) = 0;
end );
InstallTrueMethod( IsLieSolvable, IsLieNilpotent );
#############################################################################
##
#M IsLieNilpotent( <L> ) . . . . . . . . . . . . . . . for a Lie algebra
##
InstallMethod( IsLieNilpotent,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local D;
D:= LieLowerCentralSeries( L );
return Dimension( Last(D) ) = 0;
end );
InstallTrueMethod( IsLieNilpotent, IsLieAbelian );
#############################################################################
##
#M IsLieAbelian( <L> ) . . . . . . . . . . . . . . for a Lie algebra
##
## It is of course sufficient to check products of algebra generators,
## no basis and structure constants of <L> are needed.
## But if we have already a structure constants table we use it.
##
InstallMethod( IsLieAbelian,
"for a Lie algebra with known basis",
true,
[ IsAlgebra and IsLieAlgebra and HasBasis ], 0,
function( L )
local B, # basis of `L'
T, # structure constants table w.r.t. `B'
i, # loop variable
j; # loop variable
B:= Basis( L );
if not HasStructureConstantsTable( B ) then
TryNextMethod();
fi;
T:= StructureConstantsTable( B );
for i in T{ [ 1 .. Length( T ) - 2 ] } do
for j in i do
if not IsEmpty( j[1] ) then
return false;
fi;
od;
od;
return true;
end );
InstallMethod( IsLieAbelian,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local i, # loop variable
j, # loop variable
zero, # zero of `L'
gens; # algebra generators of `L'
zero:= Zero( L );
gens:= GeneratorsOfAlgebra( L );
for i in [ 1 .. Length( gens ) ] do
for j in [ 1 .. i-1 ] do
if gens[i] * gens[j] <> zero then
return false;
fi;
od;
od;
# The algebra multiplication is trivial, and the algebra does
# not know about a basis.
# Here we know at least that the algebra generators are space
# generators.
if not HasGeneratorsOfLeftModule( L ) then
SetGeneratorsOfLeftModule( L, gens );
fi;
# Return the result.
return true;
end );
InstallTrueMethod( IsLieAbelian, IsAlgebra and IsZeroMultiplicationRing );
##############################################################################
##
#M LieCentre( <L> ) . . . . . . . . . . . . . . . . . . . for a Lie algebra
##
## We solve the system
## $\sum_{i=1}^n a_i c_{ijk} = 0$ for $1 \leq j, k \leq n$
## (instead of $\sum_{i=1}^n a_i ( c_{ijk} - c_{jik} ) = 0$).
##
## Additionally we know that the centre of a Lie algebra is an ideal.
##
InstallMethod( LieCentre,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( A )
local R, # left acting domain of `A'
C, # Lie centre of `A', result
B, # a basis of `A'
T, # structure constants table w.r. to `B'
n, # dimension of `A'
M, # matrix of the equation system
zerovector, #
i, j, # loop over ...
row; # one row of `M'
R:= LeftActingDomain( A );
if Characteristic( R ) <> 2 and HasCentre( A ) then
C:= Centre( A );
#T change it to an ideal!
else
# Catch the trivial case.
n:= Dimension( A );
if n = 0 then
return A;
fi;
# Construct the equation system.
B:= Basis( A );
T:= StructureConstantsTable( B );
M:= [];
zerovector:= [ 1 .. n*n ] * Zero( R );
for i in [ 1 .. n ] do
row:= ShallowCopy( zerovector );
for j in [ 1 .. n ] do
if IsBound( T[i][j] ) then
row{ (j-1)*n + T[i][j][1] }:= T[i][j][2];
fi;
od;
M[i]:= row;
od;
# Solve the equation system.
M:= NullspaceMat( M );
# Get the generators from the coefficient vectors.
M:= List( M, x -> LinearCombination( B, x ) );
# Construct the Lie centre.
C:= IdealNC( A, M, "basis" );
fi;
# Return the Lie centre.
return C;
end );
##############################################################################
##
#M LieCentralizer( <A>, <S> ) . . . . . for a Lie algebra and a vector space
##
## Let $(b_1, \ldots, b_n)$ be a basis of <A>, and $(s_1, \ldots, s_m)$
## be a basis of <S>, with $s_j = \sum_{l=1}^m v_{jl} b_l$.
## The structure constants of <A> are $c_{ijk}$ with
## $b_i b_j = \sum_{k=1}^n c_{ijk} b_k$.
## Then we compute a basis of the solution space of the system
## $\sum_{i=1}^n a_i \sum_{l=1}^m v_{jl} c_{ilk} = 0$ for
## $1 \leq j \leq m$ and $1 \leq k \leq n$.
##
## (left null space of an $n \times (nm)$ matrix)
##
InstallMethod( LieCentralizer,
"for an abelian Lie algebra and a vector space",
IsIdenticalObj,
[ IsAlgebra and IsLieAlgebra and IsLieAbelian,
IsVectorSpace ], 0,
function( A, S )
if IsSubset( A, S ) then
return A;
else
TryNextMethod();
fi;
end );
InstallMethod( LieCentralizer,
"for a Lie algebra and a vector space",
IsIdenticalObj,
[ IsAlgebra and IsLieAlgebra, IsVectorSpace ], 0,
function( A, S )
local R, # left acting domain of `A'
B, # basis of `A'
T, # structure constants table w. r. to `B'
n, # dimension of `A'
m, # dimension of `S'
M, # matrix of the equation system
v, # coefficients of basis vectors of `S' w.r. to `B'
zerovector, # initialize one row of `M'
row, # one row of `M'
i, j, k, l, # loop variables
cil, #
offset,
vjl,
pos;
# catch trivial case
if Dimension(S) = 0 then
return A;
fi;
R:= LeftActingDomain( A );
B:= Basis( A );
T:= StructureConstantsTable( B );
n:= Dimension( A );
m:= Dimension( S );
M:= [];
v:= List( BasisVectors( Basis( S ) ),
x -> Coefficients( B, x ) );
zerovector:= [ 1 .. n*m ] * Zero( R );
# Column $(j-1)*n + k$ contains in row $i$ the value
# $\sum_{l=1}^m v_{jl} c_{ilk}$
for i in [ 1 .. n ] do
row:= ShallowCopy( zerovector );
for l in [ 1 .. n ] do
cil:= T[i][l];
for j in [ 1 .. m ] do
offset := (j-1)*n;
vjl := v[j][l];
for k in [ 1 .. Length( cil[1] ) ] do
pos:= cil[1][k] + offset;
row[ pos ]:= row[ pos ] + vjl * cil[2][k];
od;
od;
od;
Add( M, row );
od;
# Solve the equation system.
M:= NullspaceMat( M );
# Construct the generators from the coefficient vectors.
M:= List( M, x -> LinearCombination( B, x ) );
# Return the subalgebra.
return SubalgebraNC( A, M, "basis" );
end );
##############################################################################
##
#M LieNormalizer( <L>, <U> ) . . . . . . for a Lie algebra and a vector space
##
## If $(x_1, \ldots, x_n)$ is a basis of $L$ and $(u_1, \ldots, u_s)$ is
## a basis of $U$, then $x = \sum_{i=1}^n a_i x_i$ is an element of $N_L(U)$
## iff $[x,u_j] = \sum_{k=1}^s b_{j,k} u_k$ for $j = 1, \ldots, s$.
## This leads to a set of $n s$ equations for the $n + s^2$ unknowns $a_i$
## and $b_{jk}$.
## If $u_k= \sum_{l=1}^n v_{kl} x_l$, then these equations can be written as
## $\sum_{i=1}^n (\sum_{j=1}^n v_{lj} c_{ijk} a_i -
## \sum_{i=1}^s v_{ik} b_{li} = 0$,
## for $1 \leq k \leq n$ and $1 \leq j \leq s$,
## where the $c_{ilp}$ are the structure constants of $L$.
## From the solution we only need the "normalizer part" (i.e.,
## the $a_i$ part).
##
InstallMethod( LieNormalizer,
"for a Lie algebra and a vector space",
IsIdenticalObj,
[ IsAlgebra and IsLieAlgebra, IsVectorSpace ], 0,
function( L, U )
local R, # left acting domain of `L'
B, # a basis of `L'
T, # the structure constants table of `L' w.r.t. `B'
n, # the dimension of `L'
s, # the dimension of `U'
A, # the matrix of the equation system
i, j, k, l, # loop variables
v, # the coefficients of the basis of `U' wrt `B'
cij,
bas,
b,
pos;
# catch trivial case
if Dimension(U) = 0 then
return L;
fi;
# We need not work if `U' knows to be an ideal in its parent `L'.
if HasParent( U ) and IsIdenticalObj( L, Parent( U ) )
and HasIsLeftIdealInParent( U ) and IsLeftIdealInParent( U ) then
return L;
fi;
R:= LeftActingDomain( L );
B:= Basis( L );
T:= StructureConstantsTable( B );
n:= Dimension( L );
s:= Dimension( U );
if s = 0 or n = 0 then
return L;
fi;
v:= List( BasisVectors( Basis( U ) ),
x -> Coefficients( B, x ) );
# The equations.
# First the normalizer part, \ldots
A:= NullMat( n + s*s, n*s, R );
for i in [ 1..n ] do
for j in [ 1..n ] do
cij:= T[i][j];
for l in [ 1..s ] do
for k in [ 1..Length( cij[1] ) ] do
pos:= (l-1)*n+cij[1][k];
A[i][pos]:= A[i][pos]+v[l][j]*cij[2][k];
od;
od;
od;
od;
# \ldots and then the "superfluous" part.
for k in [1..n] do
for l in [1..s] do
for i in [1..s] do
A[ n+(l-1)*s+i ][ (l-1)*n+k ]:= -v[i][k];
od;
od;
od;
# Solve the equation system.
b:= NullspaceMat(A);
# Extract the `normalizer part' of the solution.
l:= Length(b);
bas:= NullMat( l, n, R );
for i in [ 1..l ] do
for j in [ 1..n ] do
bas[i][j]:= b[i][j];
od;
od;
# Construct the generators from the coefficients list.
bas:= List( bas, x -> LinearCombination( B, x ) );
# Return the subalgebra.
return SubalgebraNC( L, bas, "basis" );
end );
##############################################################################
##
#M KappaPerp( <L>, <U> ) . . . . . . . . for a Lie algebra and a vector space
##
#T Should this better be `OrthogonalSpace( <F>, <U> )' where <F> is a
#T bilinear form?
#T How to represent forms in GAP?
#T (Clearly the form must know about the space <L>.)
##
## If $(x_1,\ldots, x_n)$ is a basis of $L$ and $(u_1,\ldots, u_s)$ is a
## basis of $U$ such that $u_k = \sum_{j=1}^n v_{kj} x_j$ then an element
## $x = \sum_{i=1}^n a_i x_i$ is an element of $U^{\perp}$ iff the $a_i$
## satisfy the equations
## $\sum_{i=1}^n ( \sum_{j=1}^n v_{kj} \kappa(x_i,x_j) ) a_i = 0$ for
## $k = 1, \ldots, s$.
##
InstallMethod( KappaPerp,
"for a Lie algebra and a vector space",
IsIdenticalObj,
[ IsAlgebra and IsLieAlgebra, IsVectorSpace ], 0,
function( L, U )
local R, # left acting domain of `L'
B, # a basis of L
kap, # the matrix of the Killing form w.r.t. `B'
A, # the matrix of the equation system
n, # the dimension of L
s, # the dimension of U
v, # coefficient list of the basis of U w.r.t. the basis of L
i,j,k, # loop variables
bas; # the basis of the solution space
R:= LeftActingDomain( L );
B:= Basis( L );
n:= Dimension( L );
s:= Dimension( U );
if s = 0 or n = 0 then
return L;
fi;
v:= List( BasisVectors( Basis( U ) ),
x -> Coefficients( B, x ) );
A:= NullMat( n, s, R );
kap:= KillingMatrix( B );
# Compute the equations that define the subspace.
for k in [ 1..s ] do
for i in [ 1..n ] do
for j in [ 1..n ] do
A[i][k]:= A[i][k] + v[k][j] * kap[i][j];
od;
od;
od;
# Solve the equation system.
bas:= NullspaceMat( A );
# Extract the generators.
bas:= List( bas, x -> LinearCombination( B, x ) );
return SubspaceNC( L, bas, "basis" );
end );
#############################################################################
##
#M AdjointMatrix( <B>, <x> )
##
## If the basis vectors are $(b-1, b_2, \ldots, b_n)$, and
## $x = \sum_{i=1}^n x_i b_i$ then $b_j$ is mapped to
## $[ x, b_j ] = \sum_{i=1}^n x_i [ b_i b_j ]
## = \sum_{k=1}^n ( \sum_{i=1}^n x_i c_{ijk} ) b_k$,
## so the entry in the $k$-th row and the $j$-th column of the adjoint
## matrix is $\sum_{i=1}^n x_i c_{ijk}$.
##
## Note that $ad_x$ is a left multiplication, so also the action of the
## adjoint matrix is from the left (i.e., on column vectors).
##
InstallMethod( AdjointMatrix,
"for a basis of a Lie algebra, and an element",
IsCollsElms,
[ IsBasis, IsRingElement ], 0,
function( B, x )
local n, # dimension of the algebra
T, # structure constants table w.r. to `B'
zerovector, # zero of the field
M, # adjoint matrix, result
j, i, l, # loop variables
cij, # structure constants vector
k, # one position in structure constants vector
row; # one row of `M'
x:= Coefficients( B, x );
n:= Length( BasisVectors( B ) );
T:= StructureConstantsTable( B );
zerovector:= [ 1 .. n ] * Last(T);
M:= [];
for j in [ 1 .. n ] do
row:= ShallowCopy( zerovector );
for i in [ 1 .. n ] do
cij:= T[i][j];
for l in [ 1 .. Length( cij[1] ) ] do
k:= cij[1][l];
row[k]:= row[k] + x[i] * cij[2][l];
od;
od;
M[j]:= row;
od;
return TransposedMat( M );
end );
#T general function for arbitrary algebras? (right/left multiplication)
#T RegularRepresentation: right multiplication satisfies M_{xy} = M_x M_y
#T is just the negative of the adjoint ...
#############################################################################
##
#M RightDerivations( <B> )
##
## Let $n$ be the dimension of $A$.
## We start with $n^2$ indeterminates $D = [ d_{i,j} ]_{i,j}$ which
## means that $D$ maps $b_i$ to $\sum_{j=1}^n d_{ij} b_j$.
##
## (Note that this is row convention.)
##
## This leads to the following linear equation system in the $d_{ij}$.
## $\sum_{k=1}^n ( c_{ijk} d_{km} - c_{kjm} d_{ik} - c_{ikm} d_{jk} ) = 0$
## for all $1 \leq i, j, m \leq n$.
## The solution of this system gives us a vector space basis of the
## algebra of derivations.
##
InstallMethod( RightDerivations,
"method for a basis of an algebra",
true,
[ IsBasis ], 0,
function( B )
local T, # structure constants table w.r. to 'B'
L, # underlying Lie algebra
R, # left acting domain of 'L'
n, # dimension of 'L'
eqno,offset,
A,
i, j, k, m,
M; # the Lie algebra of derivations
if not IsAlgebra( UnderlyingLeftModule( B ) ) then
Error( "<B> must be a basis of an algebra" );
fi;
if IsLieAlgebra( UnderlyingLeftModule( B ) ) then
offset:= 1;
else
offset:= 0;
fi;
T:= StructureConstantsTable( B );
L:= UnderlyingLeftModule( B );
R:= LeftActingDomain( L );
n:= Dimension( L );
if n = 0 then
return NullAlgebra( R );
fi;
# The rows in the matrix of the equation system are indexed
# by the $d_{ij}$; the $((i-1) n + j)$-th row belongs to $d_{ij}$.
# Construct the equation system.
if offset = 1 then
A:= NullMat( n^2, (n-1)*n*n/2, R );
else
A:= NullMat( n^2, n^3, R );
fi;
eqno:= 0;
for i in [ 1 .. n ] do
for j in [ offset*i+1 .. n ] do
for m in [ 1 .. n ] do
eqno:= eqno+1;
for k in [ 1 .. n ] do
A[ (k-1)*n+m ][eqno]:= A[ (k-1)*n+m ][eqno] +
SCTableEntry( T,i,j,k );
A[ (i-1)*n+k ][eqno]:= A[ (i-1)*n+k ][eqno] -
SCTableEntry( T,k,j,m );
A[ (j-1)*n+k ][eqno]:= A[ (j-1)*n+k ][eqno] -
SCTableEntry( T,i,k,m );
od;
od;
od;
od;
# Solve the equation system.
# Note that if `L' is a Lie algebra and $n = 1$ the matrix is empty.
if n = 1 and offset = 1 then
A:= [ [ One( R ) ] ];
else
A:= NullspaceMatDestructive( A );
fi;
# Construct the generating matrices from the vectors.
A:= List( A, v -> List( [ 1 .. n ],
i -> v{ [ (i-1)*n + 1 .. i*n ] } ) );
# Construct the Lie algebra.
if IsEmpty( A ) then
M:= AlgebraByGenerators( R, [],
LieObject( Immutable( NullMat( n, n, R ) ) ) );
else
A:= List( A, LieObject );
M:= AlgebraByGenerators( R, A );
UseBasis( M, A );
fi;
# Return the derivations.
return M;
end );
#############################################################################
##
#M LeftDerivations( <B> )
##
## Let $n$ be the dimension of $A$.
## We start with $n^2$ indeterminates $D = [ d_{i,j} ]_{i,j}$ which
## means that $D$ maps $b_i$ to $\sum_{j=1}^n d_{ji} b_j$.
##
## (Note that this is column convention.)
##
InstallMethod( LeftDerivations,
"method for a basis of an algebra",
true,
[ IsBasis ], 0,
function( B )
local T, # structure constants table w.r. to 'B'
L, # underlying Lie algebra
R, # left acting domain of 'L'
n, # dimension of 'L'
eqno,offset,
A,
i, j, k, m,
M; # the Lie algebra of derivations
if not IsAlgebra( UnderlyingLeftModule( B ) ) then
Error( "<B> must be a basis of an algebra" );
fi;
if IsLieAlgebra( UnderlyingLeftModule( B ) ) then
offset:= 1;
else
offset:= 0;
fi;
T:= StructureConstantsTable( B );
L:= UnderlyingLeftModule( B );
R:= LeftActingDomain( L );
n:= Dimension( L );
if n = 0 then
return NullAlgebra( R );
fi;
# The rows in the matrix of the equation system are indexed
# by the $d_{ij}$; the $((i-1) n + j)$-th row belongs to $d_{ij}$.
# Construct the equation system.
if offset = 1 then
A:= NullMat( n^2, (n-1)*n*n/2, R );
else
A:= NullMat( n^2, n^3, R );
fi;
eqno:= 0;
for i in [ 1 .. n ] do
for j in [ offset*i+1 .. n ] do
for m in [ 1 .. n ] do
eqno:= eqno+1;
for k in [ 1 .. n ] do
A[ (m-1)*n+k ][eqno]:= A[ (m-1)*n+k ][eqno] +
SCTableEntry( T,i,j,k );
A[ (k-1)*n+i ][eqno]:= A[ (k-1)*n+i ][eqno] -
SCTableEntry( T,k,j,m );
A[ (k-1)*n+j ][eqno]:= A[ (k-1)*n+j ][eqno] -
SCTableEntry( T,i,k,m );
od;
od;
od;
od;
# Solve the equation system.
# Note that if `L' is a Lie algebra and $n = 1$ the matrix is empty.
if n = 1 and offset = 1 then
A:= [ [ One( R ) ] ];
else
A:= NullspaceMatDestructive( A );
fi;
# Construct the generating matrices from the vectors.
A:= List( A, v -> List( [ 1 .. n ],
i -> v{ [ (i-1)*n + 1 .. i*n ] } ) );
# Construct the Lie algebra.
if IsEmpty( A ) then
M:= AlgebraByGenerators( R, [],
LieObject( Immutable( NullMat( n, n, R ) ) ) );
else
A:= List( A, LieObject );
M:= AlgebraByGenerators( R, A );
UseBasis( M, A );
fi;
# Return the derivations.
return M;
end );
#############################################################################
##
#M KillingMatrix( <B> )
##
## We have $\kappa_{i,j} = \sum_{k,l=1}^n c_{jkl} c_{ilk}$ if $c_{ijk}$
## are the structure constants w.r. to <B>.
##
## (The matrix is symmetric, no matter whether the multiplication is
## (anti-)symmetric.)
##
InstallMethod( KillingMatrix,
"for a basis of a Lie algebra",
true,
[ IsBasis ], 0,
function( B )
local T, # s.c. table w.r. to `B'
L, # the underlying algebra
R, # left acting domain of `L'
kappa, # the matrix of the killing form, result
n, # dimension of `L'
zero, # the zero of `R'
i, j, k, t, # loop variables
row, # one row of `kappa'
val, # one entry of `kappa'
cjk; # `T[j][k]'
T:= StructureConstantsTable( B );
L:= UnderlyingLeftModule( B );
R:= LeftActingDomain( L );
n:= Dimension( L );
kappa:= [];
zero:= Zero( R );
for i in [ 1 .. n ] do
row:= [];
for j in [ 1 .. i ] do
val:= zero;
for k in [ 1 .. n ] do
cjk:= T[j][k];
for t in [ 1 .. Length( cjk[1] ) ] do
val:= val + cjk[2][t] * SCTableEntry( T, i, cjk[1][t], k );
od;
od;
row[j]:= val;
if i <> j then
kappa[j][i]:= val;
fi;
od;
kappa[i]:= row;
od;
# Return the result.
return kappa;
end );
##############################################################################
##
#M AdjointBasis( <B> )
##
## The input is a basis of a (Lie) algebra $L$.
## This function returns a particular basis $C$ of the matrix space generated
## by $ad L$, namely a basis consisting of elements of the form $ad x_i$
## where $x_i$ is a basis element of <B>.
## An extra component `indices' is added to this space.
## This is a list of integers such that `ad <B>.basisVectors[ indices[i] ]'
## is the `i'-th basis vector of <C>, for i in [1..Length(indices)].
## (This list is added in order to be able to identify the basis element of
## <B> with the property that its adjoint matrix is equal to a given basis
## vector of <C>.)
##
InstallMethod( AdjointBasis,
"for a basis of a Lie algebra",
true,
[ IsBasis ], 0,
function( B )
local bb, # the basis vectors of `B'
n, # the dimension of `B'
F, # the field over which the algebra is defined
adL, # a list of matrices that form a basis of adLsp
adLsp, # the matrix space spanned by ad L
inds, # the list of indices
i, # loop variable
adi, # the adjoint matrix of the i-th basis vector of `B'
adLbas; # the basis of `adLsp' compatible with `adL'
bb:= BasisVectors( B );
n:= Length( bb );
F:= LeftActingDomain( UnderlyingLeftModule( B ) );
adL:= [];
adLsp:= MutableBasis( F, [ NullMat(n,n,F) ] );
#T better declare the zero ?
inds:= [];
for i in [1..n] do
adi:= AdjointMatrix( B, bb[i] );
if not IsContainedInSpan( adLsp, adi ) then
Add( adL, adi );
Add( inds, i );
CloseMutableBasis( adLsp, adi );
fi;
od;
if adL = [ ] then
adLbas:= Basis( VectorSpace( F, [ ], NullMat( n, n, F ) ) );
else
adLbas:= Basis( VectorSpace( F, adL ), adL );
fi;
SetIndicesOfAdjointBasis( adLbas, inds );
return adLbas;
end );
##############################################################################
##
#M IsRestrictedLieAlgebra( <L> ) . . . . . . . . . . . . . for a Lie algebra
##
## A Lie algebra <L> is defined to be {\em restricted} when it is defined
## over a field of characteristic $p \neq 0$, and for every basis element
## $x$ of <L> there exists $y\in <L>$ such that $(ad x)^p = ad y$
## (see Jacobson, p. 190).
##
InstallMethod( IsRestrictedLieAlgebra,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local F, # the field over which L is defined
B, # the basis of L
p, # the characteristic of F
adL, # basis for the (matrix) vector space generated by ad L
v; # loop over basis vectors of adL
F:= LeftActingDomain( L );
p:= Characteristic( F );
if p = 0 then
return false;
fi;
B:= Basis( L );
adL:= AdjointBasis( B );
# Check if ad(L) is closed under the p-th power operation.
for v in BasisVectors( adL ) do
if not v^p in UnderlyingLeftModule( adL ) then
return false;
fi;
od;
return true;
end );
#############################################################################
##
#F PowerSi( <F>, <i> )
##
InstallGlobalFunction( PowerSi, function( F, i )
local si, # a function of two arguments: seqs, a list of sequences,
# and l, a list containing the two arguments of the
# function s_i. The list seqs contains
# all possible sequences of i-1 1's and p-2-i+1 2's
# This function returns the value of s_i(l[1],l[2])
j,k, # loop variables
p, # the characteristic of F
combs, # the list of all i-1 element subsets of {1,2,\ldots, p-2}
# it serves to make the list seqs
v, # a vector of 1's and 2's
seqs; # the list of all sequences of 1's and 2's of length p-2,
# with i-1 1's and p-2 2's serving as input for si
# for example, the sequence [1,1,2] means the element
# [[[[x,y],x],x],y] (the first element [x,y] is present
# 1 1 2 in all terms of the sum s_i(x,y)).
si:= function( seqs, l )
local x,
j,k,
sum;
for j in [1..Length(seqs)] do
x:= l[1]*l[2];
for k in seqs[j] do
x:= x*l[k];
od;
if j=1 then
sum:= x;
else
sum:= sum+x;
fi;
od;
return ( i * One( F ) )^(-1)*sum;
end;
p:= Characteristic( F );
combs:= Combinations( [1..p-2], i-1 );
# Now all sequences of 1's and 2's of length p and containing i-1 1's
# are constructed the 1's in the jth sequence are put at the positions
# contained in combs[j].
seqs:=[];
for j in [1..Length( combs )] do
v:= List( [1..p-2], x -> 2);
for k in combs[j] do
v[k]:= 1;
od;
Add( seqs, v );
od;
return arg -> si( seqs, arg );
end );
#############################################################################
##
#F PowerS( <L> )
##
InstallMethod( PowerS,
"for a Lie algebra",
true,
[ IsLieAlgebra ], 0,
function( L )
local F, # the coefficients domain
p; # the characteristic of `F'
F:= LeftActingDomain( L );
p:= Characteristic( F );
return List( [ 1 .. p-1 ], i -> PowerSi( F , i ) );
end );
##############################################################################
##
#F PthPowerImage( <B>, <x> )
##
BindGlobal("PTHPOWERIMAGE_PPI_VEC", function(L,zero,p,bv,pmap,cf,x)
local
n, # the dimension of L
s, # the list of s_i functions
im, # the image of x under the p-th power map
i,j; # loop variables
n:= Dimension( L );
s:= PowerS( L );
im:= Zero( L );
# First the sum of all $\alpha_i^p x_i^{[p]}$ is calculated.
for i in [1..n] do
im:= im + cf[i]^p * pmap[i];
od;
# To this the double sum of all
# $s_i(\alpha_j x_j, \sum_{k=j+1}^n \alpha_k x_k)$
# is added.
for j in [1..n-1] do
if cf[j] <> zero then
x:= x - cf[j] * bv[j];
for i in [1..p-1] do
im:= im + s[i]( [cf[j]*bv[j],x] );
od;
fi;
od;
return im;
end);
InstallMethod( PthPowerImage,
"for a basis of an algebra, and a ring element",
IsCollsElms,
[ IsBasis, IsRingElement ], 0,
function( B, x )
local L, # the Lie algebra of which B is a basis
F, # the coefficients domain of `L'
n, # the dimension of L
p, # the characteristic of the ground field
s, # the list of s_i functions
pmap, # the list containing x_i^{[p]}
cf, # the coefficients of x wrt the basis of L
im, # the image of x under the p-th power map
i,j, # loop variables
zero, # zero of `F'
bv, # basis vectors of `B'
adx, # adjoint matrix of x
adL; # a basis of the matrix space ad L
L:= UnderlyingLeftModule( B );
if not IsLieAlgebra( L ) then
TryNextMethod();
fi;
F:= LeftActingDomain( L );
p:= Characteristic( F );
if Dimension( LieCentre( L ) ) = 0 then
# We calculate the inverse image $ad^{-1} ((ad x)^p)$.
adx:= AdjointMatrix( B, x );
adL:= AdjointBasis( B );
adx:= adx^p;
cf:= Coefficients( adL, adx );
return LinearCombination( B, cf );
else
return PTHPOWERIMAGE_PPI_VEC(L,Zero(F),p,BasisVectors(B),PthPowerImages(B),Coeffi
cients(B,x),x);
fi;
end );
InstallMethod( PthPowerImage, "for an element of a restricted Lie algebra",
[ IsJacobianElement ], # weaker filter, we maybe only discovered later
# that the algebra is restricted
function(x)
local fam;
fam := FamilyObj(x);
if not IsBound(fam!.pMapping) then TryNextMethod(); fi;
return PTHPOWERIMAGE_PPI_VEC(fam!.fullSCAlgebra,fam!.zerocoeff,Characteristic(fam),fam!.basisVectors,fam!.pMapping,ExtRepOfObj(x),x);
end);
InstallMethod( PthPowerImage, "for an element of a restricted Lie algebra and an integer",
[ IsJacobianElement, IsInt ],
function(x,n)
local fam;
fam := FamilyObj(x);
if not IsBound(fam!.pMapping) then TryNextMethod(); fi;
while n>0 do
x := PTHPOWERIMAGE_PPI_VEC(fam!.fullSCAlgebra,fam!.zerocoeff,Characteristic(fam),fam!.basisVectors,fam!.pMapping,ExtRepOfObj(x),x);
n := n-1;
od;
return x;
end);
InstallMethod( PClosureSubalgebra, "for a subalgebra of restricted jacobian elements",
[ IsLieAlgebra and IsJacobianElementCollection ],
function(A)
local i, oldA;
repeat
oldA := A;
for i in Basis(oldA) do
A := ClosureLeftModule(A,PthPowerImage(i));
od;
until A=oldA;
return A;
end);
#############################################################################
##
#M PthPowerImages( <B> ) . . . . . . . . . . . for a basis of a Lie algebra
##
InstallMethod( PthPowerImages,
"for a basis of a Lie algebra",
true,
[ IsBasis ], 0,
function( B )
local L, # the underlying algebra
p, # the characteristic of `L'
adL, # a basis of the matrix space spanned by ad L
basL; # the list of basis vectors `b' of `B' such that
# `ad b' is a basis vector of `adL'
L:= UnderlyingLeftModule( B );
if not IsRestrictedLieAlgebra( L ) then
Error( "<L> must be a restricted Lie algebra" );
fi;
p:= Characteristic( LeftActingDomain( L ) );
adL:= AdjointBasis( B );
if Dimension( UnderlyingLeftModule( adL ) ) = 0 then
# The algebra is abelian.
return List( BasisVectors( B ), x -> Zero( L ) );
fi;
# Now `IndicesOfAdjointBasis( adL )' is a list of indices with `i'-th
# entry the position of the basis vector of `B'
# whose adjoint matrix is the `i'-th basis vector of `adL'.
basL:= BasisVectors( B ){ IndicesOfAdjointBasis( adL ) };
# We calculate the coefficients of $x_i^{[p]}$ wrt the basis basL.
return List( BasisVectors( B ),
x -> Coefficients( adL, AdjointMatrix( B, x ) ^ p ) * basL );
#T And why do you compute the adjoint matrices again?
#T Aren't they stored as basis vectors in adL ?
end );
############################################################################
##
#M CartanSubalgebra( <L> )
##
## A Cartan subalgebra of the Lie algebra <L> is by definition a nilpotent
## subalgebra equal to its own normalizer in <L>.
##
## By definition, an Engel subalgebra of <L> is the generalized eigenspace
## of a non nilpotent element, corresponding to the eigenvalue 0.
## In a restricted Lie algebra of characteristic p we have that every Cartan
## subalgebra of an Engel subalgebra of <L> is a Cartan subalgebra of <L>.
## Hence in this case we construct a decreasing series of Engel subalgebras.
## When it becomes stable we have found a Cartan subalgebra.
## On the other hand, when <L> is not restricted and is defined over a field
## $F$ of cardinality greater than the dimension of <L> we can proceed as
## follows.
## Let $a$ be a non nilpotent element of <L> and $K$ the corresponding
## Engel subalgebra. Furthermore, let $b$ be a non nilpotent element of $K$.
## Then there is an element $c \in F$ such that $a + c ( b - a )$ has an
## Engel subalgebra strictly contained in $K$
## (see Humphreys, proof of Lemma A, p 79).
##
InstallMethod( CartanSubalgebra,
"for a Lie algebra",
true,
[ IsLieAlgebra ], 0,
function( L )
local n, # the dimension of L
F, # coefficients domain of `L'
root, # prim. root of `F' if `F' is finite
K, # a subalgebra of L (on termination a Cartan subalg.)
a,b, # (non nilpotent) elements of L
A, # matrix of the equation system (ad a)^n(x)=0
bas, # basis of the solution space of Ax=0
sp, # the subspace of L generated by bas
found,ready, # boolean variables
c, # an element of `F'
newelt, # an element of L of the form a+c*(b-a)
i; # loop variable
n:= Dimension(L);
F:= LeftActingDomain( L );
if IsRestrictedLieAlgebra( L ) then
K:= L;
while true do
a:= NonNilpotentElement( K );
if a = fail then
# `K' is a nilpotent Engel subalgebra, hence a Cartan subalgebra.
return K;
fi;
# `a' is a non nilpotent element of `K'.
# We construct the generalized eigenspace of this element w.r.t.
# the eigenvalue 0. This is a subalgebra of `K' and of `L'.
A:= TransposedMat( AdjointMatrix( Basis( K ), a));
A:= A ^ Dimension( K );
bas:= NullspaceMat( A );
bas:= List( bas, x -> LinearCombination( Basis( K ), x ) );
K:= SubalgebraNC( L, bas, "basis");
od;
elif n < Size( F ) then
# We start with an Engel subalgebra. If it is nilpotent
# then it is a Cartan subalgebra and we are done.
# Otherwise we make it smaller.
a:= NonNilpotentElement( L );
if a = fail then
# `L' is nilpotent.
return L;
fi;
# `K' will be the Engel subalgebra corresponding to `a'.
A:= TransposedMat( AdjointMatrix( Basis( L ), a ) );
A:= A^n;
bas:= NullspaceMat( A );
bas:= List( bas, x -> LinearCombination( Basis( L ), x ) );
K:= SubalgebraNC( L, bas, "basis");
# We locate a nonnilpotent element in this Engel subalgebra.
b:= NonNilpotentElement( K );
# If `b = fail' then `K' is nilpotent and we are done.
ready:= ( b = fail );
while not ready do
# We locate an element $a + c*(b-a)$ such that the Engel subalgebra
# belonging to this element is smaller than the Engel subalgebra
# belonging to `a'.
# We do this by checking a few values of `c'
# (At most `n' values of `c' will not yield a smaller subalgebra.)
sp:= VectorSpace( F, BasisVectors( Basis(K) ), "basis");
found:= false;
if Characteristic( F ) = 0 then
c:= 0;
else
root:= PrimitiveRoot( F );
c:= root;
fi;
while not found do
if Characteristic( F ) = 0 then
c:= c+1;
else
c:= c*root;
fi;
newelt:= a+c*(b-a);
# Calculate the Engel subalgebra belonging to `newelt'.
A:= TransposedMat( AdjointMatrix( Basis( K ), newelt ) );
A:= A^Dimension( K );
bas:= NullspaceMat( A );
bas:= List( bas, x -> LinearCombination( Basis( K ), x ) );
# We have found a smaller subalgebra if the dimension is smaller
# and new basis elements are contained in the old space.
found:= Length( bas ) < Dimension( K );
i:= 1;
while i <= Length( bas ) and found do
if not bas[i] in sp then
found:= false;
fi;
i:= i+1;
od;
od;
a:= newelt;
K:= SubalgebraNC( L, bas, "basis");
b:= NonNilpotentElement( K );
# If `b = fail' then `K' is nilpotent and we are done.
ready:= b = fail;
od;
return K;
else
# the field over which <L> is defined is too small
TryNextMethod();
fi;
end );
##############################################################################
##
#M AdjointAssociativeAlgebra( <L>, <K> )
##
## This function calculates a basis of the associative matrix algebra
## generated by ad_L K, where <K> is a subalgebra of <L>.
## If {x_1,\ldots ,x_n} is a basis of K, then this algebra is spanned
## by all words
## ad x_{i_1}\cdots ad x_{i_t}
## where t>0.
## The degree of such a word is t.
## The algorithm first calculates a maximal linearly independent set
## of words of degree 1, then of degree 2 and so on.
## Since ad x ad y -ady ad x = ad [x,y], we have that we only have
## to consider words where i_1\leq i_2\leq \cdots \leq i_t.
##
InstallMethod( AdjointAssociativeAlgebra,
"for a Lie algebra and a subalgebra",
true,
[ IsAlgebra and IsLieAlgebra, IsAlgebra and IsLieAlgebra ], 0,
function( L, K )
local n, # the dimension of L
F, # the field of L
asbas, # a list containing the basis elts. of the assoc. alg.
highdeg, # a list of the elements of the highest degree computed
# so far
degree1, # a list of elements of degree 1 (i.e. ad x_i)
lowinds, # a list of indices such that lowinds[i] is the smallest
# index in the word highdeg[i]
hdeg, # the new highdeg constructed each step
linds, # the new lowinds constructed each step
i,j,k, # loop variables
ind, # an index
m, # a matrix
posits, # a list of positions in matrices:
# posits[i] is a list of the form [p,q] such that
# the matrix asbas[i] has a nonzero entry at position
# [p][q] and furthermore the matrices asbas[j] with j>i
# will have a zero at that position (so the basis
# constructed will be in `upper triangular form')
l1,l2, # loop variables
found; # a boolean
F:= LeftActingDomain( L );
if Dimension( K ) = 0 then
return Algebra( F, [ [ [ Zero(F) ] ] ] );
elif IsLieAbelian( L ) then
return Algebra( F, [ AdjointMatrix( Basis( L ),
GeneratorsOfAlgebra( K )[1] ) ] );
fi;
n:= Dimension( L );
# Initialisations that ensure that the first step of the loop will select
# a maximal linearly independent set of matrices of degree 1.
degree1:= List( BasisVectors( Basis(K) ),
x -> AdjointMatrix( Basis(L), x ) );
posits := [ [ 1, 1 ] ];
highdeg := [ IdentityMat( n, F ) ];
asbas := [ Immutable( highdeg[1] ) ];
lowinds := [ Dimension( K ) ];
# If after some steps all words of degree t (say) can be reduced modulo
# lower degree, then all words of degree >t can be reduced to linear
# combinations of words of lower degree.
# Hence in that case we are done.
while not IsEmpty( highdeg ) do
hdeg:= [];
linds:= [];
for i in [1..Length(highdeg)] do
# Now we multiply all elements `highdeg[i]' with all possible
# elements of degree 1 (i.e. elements having an index <= the lowest
# index of the word `highdeg[i]')
ind:= lowinds[i];
for j in [1..ind] do
m:= degree1[j]*highdeg[i];
# Now we first reduce `m' on the basis computed so far
# and then add it to the basis.
for k in [1..Length(posits)] do
l1:= posits[k][1];
l2:= posits[k][2];
m:= m-(m[l1][l2]/asbas[k][l1][l2])*asbas[k];
od;
if not IsZero( m ) then
#'m' is not an element of the span of `asbas'
Add( hdeg, m );
Add( linds, j );
Add( asbas, m);
# Now we look for a nonzero entry in `m'
# and add the position of that entry to `posits'.
found:= false;
l1:= 1; l2:= 1;
while not found do
if not IsZero( m[l1][l2] ) then
Add( posits, [l1,l2] );
found:= true;
else
if l2 = n then
l1:= l1+1;
l2:= 1;
else
l2:= l2+1;
fi;
fi;
od;
fi;
od;
od;
if lowinds = [Dimension(K)] then
# We are in the first step and hence `degree1' must be made
# equal to the linearly independent set that we have just calculated.
degree1:= ShallowCopy( hdeg );
linds:= [1..Length(degree1)];
fi;
highdeg:= ShallowCopy( hdeg );
lowinds:= ShallowCopy( linds );
od;
return Algebra( F, asbas, "basis" );
end );
##############################################################################
##
#M LieNilRadical( <L> )
##
## Let $p$ be the characteristic of the coefficients field of <L>.
## If $p=0$ the we use the following characterisation of the LieNilRadical:
## Let $S$ be the solvable radical of <L>. And let $H$ be a Cartan subalgebra
## of $S$. Decompose $S$ as $S = H \oplus S_1(H)$, where $S_1(H)$ is the
## Fitting 1-component of the adjoint action of $H$ on $S$. Let $H*$ be the
## associative algebra generated by $ad H$, then $S_1(H)$ is the intersection
## of the spaces $H*^i( S )$ for $i>0$. Let $R$ be the radical of the
## algebra $H*$. Then the LieNilRadical of <L> consists of $S_1(H)$ together
## with all elements $x$ in $H$ such that $ad x\in R$. This last space
## is also characterised as the space of all elements $x$ such that
## $ad x$ lies in the vector space spanned by all nilpotent parts of all
## $ad h$ for $h\in H$.
##
## In the case where $p>0$ we calculate the radical of the associative
## matrix algebra $A$ generated by $ad `L'$.
## The nil radical is then equal to $\{ x\in L \mid ad x \in A \}$.
##
InstallMethod( LieNilRadical,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local F, # the coefficients domain of `L'
p, # the characteristic of `F'
bv, # basis vectors of a basis of `L'
S, # the solvable radical of `L'
H, # Cartan subalgebra of `S'
HS, # Fitting 1-component of `S' wrt `H'
adH, # list of ad x for x in a basis of `H'
n, # dimension of `L'
t, # the dimension of an ideal
eqs, # equation set
I, # basis vectors of an ideal of `L'
i,j,k, # loop variables
sol, # solution set
adL, # list of matrices ad x where x runs through a basis of
# `L'
A, # an associative algebra
R, # the radical of this algebra
B; # list of basis vectors of R
F:= LeftActingDomain( L );
p:= Characteristic( F );
if p = 0 then
# The LieNilRadical of <L> is equal to
# the LieNilRadical of its solvable radical.
S:= LieSolvableRadical( L );
n:= Dimension( S );
if n in [ 0, 1 ] then return S; fi;
H:= CartanSubalgebra(S);
if Dimension(H) = n then return S; fi;
# We calculate the Fitting 1-component $S_1(H)$.
HS:= ProductSpace( H, S );
while Dimension( HS ) + Dimension( H ) <> n do
HS:= ProductSpace( H, HS );
od;
if Dimension( H ) = 1 then
return IdealNC( L, BasisVectors(Basis(HS)), "basis" );
fi;
# Now we compute the intersection of `R' and `<ad H>'.
adH:= List( BasisVectors(Basis(H)), x -> AdjointMatrix(Basis(S),x));
R:= RadicalOfAlgebra( AdjointAssociativeAlgebra( S, H ) );
B:= BasisVectors( Basis( R ) );
eqs:= NullMat(Dimension(H)+Dimension(R),n^2,F);
for i in [1..n] do
for j in [1..n] do
for k in [1..Dimension(H)] do
eqs[k][j+(i-1)*n]:= adH[k][i][j];
od;
for k in [1..Dimension(R)] do
eqs[Dimension(H)+k][j+(i-1)*n]:= B[k][i][j];
od;
od;
od;
sol:= NullspaceMat( eqs );
I:= List( sol, x-> LinearCombination( Basis(H), x{[1..Dimension(H)]} ) );
Append( I, BasisVectors( Basis( HS ) ) );
return IdealNC( L, I, "basis" );
else
n:= Dimension( L );
bv:= BasisVectors( Basis(L) );
adL:= List( bv, x -> AdjointMatrix(Basis(L),x) );
A:= AdjointAssociativeAlgebra( L, L );
R:= RadicalOfAlgebra( A );
if Dimension( R ) = 0 then
# In this case the intersection of `ad L' and `R' is the centre of L.
return LieCentre( L );
fi;
B:= BasisVectors( Basis( R ) );
t:= Dimension( R );
# Now we compute the intersection of `R' and `<ad L>'.
eqs:= NullMat(n+t,n*n,F);
for i in [1..n] do
for j in [1..n] do
for k in [1..n] do
eqs[k][j+(i-1)*n]:= adL[k][i][j];
od;
for k in [1..t] do
eqs[n+k][j+(i-1)*n]:= -B[k][i][j];
od;
od;
od;
sol:= NullspaceMat( eqs );
I:= List( sol, x-> LinearCombination( bv, x{[1..n]} ) );
return SubalgebraNC( L, I, "basis" );
fi;
end );
##############################################################################
##
#M LieSolvableRadical( <L> )
##
## In characteristic zero, the solvable radical of the Lie algebra <L> is
## just the orthogonal complement of $[ <L> <L> ]$ w.r.t. the Killing form.
##
## In characteristic $p > 0$, the following fact is used:
## $R( <L> / NR( <L> ) ) = R( <L> ) / NR( <L> )$ where
## $R( <L> )$ denotes the solvable radical of $L$ and $NR( <L> )$ its
## nil radical).
##
InstallMethod( LieSolvableRadical,
"for a Lie algebra",
true,
[ IsLieAlgebra ], 0,
function( L )
local LL, # the derived algebra of L
n, # the nil radical of L
B, # a basis of the solvable radical of L
quo, # the quotient L/n
r1, # the solvable radical of L/n
hom; # the canonical map L -> L/n
if Characteristic( LeftActingDomain( L ) ) = 0 then
LL:= LieDerivedSubalgebra( L );
B:= BasisVectors( Basis( KappaPerp( L, LL ) ) );
else
n:= LieNilRadical( L );
if Dimension( n ) = 0 or Dimension( n ) = Dimension( L ) then
return n;
fi;
hom:= NaturalHomomorphismByIdeal( L, n );
quo:= ImagesSource( hom );
r1:= LieSolvableRadical( quo );
B:= BasisVectors( Basis( r1 ) );
B:= List( B, x -> PreImagesRepresentative( hom, x ) );
Append( B, BasisVectors( Basis( n ) ) );
fi;
SetIsLieSolvable( L, Length( B ) = Dimension( L ) );
return IdealNC( L, B, "basis");
end );
##############################################################################
##
#M DirectSumDecomposition( <L> )
##
## This function calculates a list of ideals of `L' such that `L' is equal
## to the direct sum of them.
## The existence of a decomposition of `L' is equivalent to the existence
## of a nontrivial idempotent in the centralizer of `ad L' in the full
## matrix algebra `M_n(F)'. In the general case we try to find such
## idempotents.
## In the case where the Killing form of `L' is nondegenerate we can use
## a more elegant method. In this case the action of the Cartan subalgebra
## will `identify' the direct summands.
##
InstallMethod( DirectSumDecomposition,
"for a Lie algebra",
true,
[ IsAlgebra and IsLieAlgebra ], 0,
function( L )
local F, # The field of `L'.
BL, # basis of `L'
bvl, # basis vectors of `BL'
n, # The dimension of `L'.
m, # An integer.
set, # A list of integers.
C, # The centre of `L'.
bvc, # basis vectors of a basis of `C'
D, # The derived subalgebra of `L'.
CD, # The intersection of `C' and `D'.
H, # A Cartan subalgebra of `L'.
BH, # basis of `H'
B, # A list of bases of subspaces of `L'.
cf, # Coefficient list.
comlist, # List of commutators.
ideals, # List of ideals.
bb, # List of basis vectors.
B1,B2, # Bases of the ideals.
sp, # A vector space.
x, # An element of `sp'.
b, # A list of basis vectors.
bas,res, # Bases of associative algebras.
i,j,k,l, # Loop variables.
centralizer, # The centralizer of `adL' in the matrix algebra.
Rad, # The radical of `centralizer'.
M,mat, # Matrices.
facs, # A list of factors of a polynomial.
f, # Polynomial.
contained, # Boolean variable.
adL, # A basis of the matrix space `ad L'.
Q, # The factor algebra `centralizer/Rad'
q, # Number of elements of the field of `L'.
ei,ni,E, # Elements from `centralizer'
hom, # A homomorphism.
id, # A list of idempotents.
vv; # A list of vectors.
F:= LeftActingDomain( L );
n:= Dimension( L );
if n=0 then
return [ L ];
fi;
if RankMat( KillingMatrix( Basis( L ) ) ) = n then
# The algorithm works as follows.
# Let `H' be a Cartan subalgebra of `L'.
# First we decompose `L' into a direct sum of subspaces `B[i]'
# such that the minimum polynomial of the adjoint action of an element
# of `H' restricted to `B[i]' is irreducible.
# If `L' is a direct sum of ideals, then each of these subspaces
# will be contained in precisely one ideal.
# If the field `F' is big enough then we can look for a splitting
# element in `H'.
# This is an element `h' such that the minimum polynomial of `ad h'
# has degree `dim L - dim H + 1'.
# If the size of the field is bigger than `2*m' then there is a
# powerful randomised algorithm (Las Vegas type) for finding such an
# element. We just take a random element from `H' and with probability
# > 1/2 this will be a splitting element.
# If the field is small, then we use decomposable elements instead.
H:= CartanSubalgebra( L );
BH:= Basis( H );
BL:= Basis( L );
m:= (( n - Dimension(H) ) * ( n - Dimension(H) + 2 )) / 8;
if 2*m < Size(F) and ( not Characteristic( F ) in [2,3] ) then
set:= [ -m .. m ];
repeat
cf:= List([ 1 .. Dimension( H ) ], x -> Random( set ) );
x:= LinearCombination( BH, cf );
M:= AdjointMatrix( BL, x );
f:= CharacteristicPolynomial( F, F, M );
f:= f/Gcd( f, Derivative( f ) );
until DegreeOfLaurentPolynomial( f )
= Dimension( L ) - Dimension( H ) + 1;
# We decompose the action of the splitting element:
facs:= Factors( PolynomialRing( F ), f );
B:= [];
for i in facs do
Add( B, List( NullspaceMat( TransposedMat( Value( i, M ) ) ),
x -> LinearCombination( BL, x ) ) );
od;
B:= Filtered( B, x -> not ( x[1] in H ) );
else
# Here `L' is a semisimple Lie algebra over a small field or a field
# of characteristic 2 or 3. This means that
# the existence of splitting elements is not assured. So we work
# with decomposable elements rather than with splitting ones.
# A decomposable element is an element from the associative
# algebra `T' generated by `ad H' that has a reducible minimum
# polynomial. Let `V' be a stable subspace (under the action of `H')
# computed in the process. Then we proceed as follows.
# We choose a random element from `T' and restrict it to `V'. If this
# element has an irreducible minimum polynomial of degree equal to
# the dimension of the associative algebra `T' restricted to `V',
# then `V' is irreducible. On the other hand,
# if this polynomial is reducible, then we decompose `V'.
# `bas' will be a basis of the associative algebra generated by
# `ad H'. The computation of this basis is facilitated by the fact
# that we know the dimension of this algebra.
bas:= List( BH, x -> AdjointMatrix( Basis( L ), x ) );
sp:= MutableBasis( F, bas );
k:=1; l:=1;
while k<=Length(bas) do
if Length(bas)=Dimension(L)-Dimension(H) then break; fi;
M:= bas[ k ]*bas[ l ];
if not IsContainedInSpan( sp, M ) then
CloseMutableBasis( sp, M );
Add( bas, M );
fi;
if l < Length(bas) then l:=l+1;
else k:=k+1; l:=1;
fi;
od;
Add( bas, Immutable( IdentityMat( Dimension( L ), F ) ) );
# Now `B' will be a list of subspaces of `L' stable under `H'.
# We stop once every element from `B' is irreducible.
cf:= AsList( F );
B:= [ ProductSpace( H, L ) ];
k:= 1;
while k <= Length( B ) do
if Dimension( B[k] ) = 1 then
k:=k+1;
else
b:= BasisVectors( Basis( B[k] ) );
M:= LinearCombination( bas, List( bas, x -> Random( cf ) ) );
# Now we restrict `M' to the space `B[k]'.
mat:= [ ];
for i in [1..Length(b)] do
x:= LinearCombination( BL, M*Coefficients( BL, b[i] ) );
Add( mat, Coefficients( Basis( B[k], b ), x ) );
od;
M:= TransposedMat( mat );
f:= MinimalPolynomial( F, M );
facs:= Factors( PolynomialRing( F ), f );
if Length(facs)=1 then
# We restrict the basis `bas' to the space `B[k]'. If the length
# of the result is equal to the degree of `f' then `B[k]' is
# irreducible.
sp:= MutableBasis( F,
[ Immutable( IdentityMat( Dimension(B[k]), F ) ) ] );
for j in [1..Length(bas)] do
mat:= [ ];
for i in [1..Length(b)] do
x:= LinearCombination( BL, bas[j]*Coefficients( BL, b[i] ) );
Add( mat, Coefficients( Basis( B[k], b ), x ) );
od;
mat:= TransposedMat( mat );
if not IsContainedInSpan( sp, mat ) then
CloseMutableBasis( sp, mat );
fi;
od;
res:= BasisVectors( sp );
if Length( res ) = DegreeOfLaurentPolynomial( f ) then
# The space is irreducible.
k:=k+1;
fi;
else
# We decompose.
for i in facs do
vv:= List( NullspaceMat( TransposedMat( Value( i, M ) ) ),
x -> LinearCombination( b, x ) );
sp:= VectorSpace( F, vv );
if not sp in B then Add( B, sp ); fi;
od;
# We remove the old space from the list;
B:= Filtered( B, x -> (x <> B[k]) );
fi;
fi;
od;
B:= List( B, x -> BasisVectors( Basis( x ) ) );
fi;
# Now the pieces in `B' are grouped together.
ideals:=[];
while B <> [ ] do
# Check whether `B[1]' is contained in any of
# the ideals obtained so far.
contained := false;
i:=1;
while not contained and i <= Length(ideals) do
if B[1][1] in ideals[i] then
contained:= true;
fi;
i:=i+1;
od;
if contained then # we do not need B[1] any more
B:= Filtered( B, x -> x<> B[1] );
else
# `B[1]' generates a new ideal.
# We form this ideal by taking `B[1]' together with
# all pieces from `B' that do not commute with `B[1]'.
# At the end of this process, `bb' will be a list of elements
# commuting with all elements of `B'.
# From this it follows that `bb' will generate
# a subalgebra that is a simple ideal. (No remaining piece of `B'
# can be in this ideal because in that case this piece would
# generate a smaller ideal inside this one.)
bb:= ShallowCopy( B[1] );
B:= Filtered( B, x -> x<> B[1] );
i:=1;
while i<= Length( B ) do
comlist:= [ ];
for j in [1..Length(bb)] do
Append( comlist, List( B[i], y -> bb[j]*y ) );
od;
if not ForAll( comlist, IsZero ) then
Append( bb, B[i] );
B:= Filtered( B, x -> x <> B[i] );
i:= 1;
else
i:=i+1;
fi;
od;
Add( ideals, SubalgebraNC( L, bb ) );
fi;
od;
return List( ideals,
I -> IdealNC( L, BasisVectors( Basis( I ) ), "basis" ));
else
# First we try to find a central component, i.e., a decomposition
# `L=I_1 \oplus I_2' such that `I_1' is contained in the center of `L'.
# Such a decomposition exists if and only if the center of `L' is not
# contained in the derived subalgebra of `L'.
C:= LieCentre( L );
bvc:= BasisVectors( Basis( C ) );
if Dimension( C ) = Dimension( L ) then
#Now `L' is abelian; hence `L' is the direct sum of `dim L' ideals.
return List( bvc, v -> IdealNC( L, [ v ], "basis" ) );
fi;
BL:= Basis( L );
bvl:= BasisVectors( BL );
if 0 < Dimension( C ) then
D:= LieDerivedSubalgebra( L );
CD:= Intersection2( C, D );
if Dimension( CD ) < Dimension( C ) then
# The central component is the complement of `C \cap D' in `C'.
B1:=[];
k:=1;
sp:= MutableBasis( F,
BasisVectors( Basis( CD ) ), Zero( CD ) );
while Length( B1 ) + Dimension( CD ) <> Dimension( C ) do
x:= bvc[k];
if not IsContainedInSpan( sp, x ) then
Add( B1, x );
CloseMutableBasis( sp, x );
fi;
k:=k+1;
od;
# The second ideal is a complement of the central component
# in `L' containing `D'.
#W next statement modified:
B2:= ShallowCopy( BasisVectors( Basis( D ) ) );
k:= 1;
b:= ShallowCopy( B1 );
Append( b, B2 );
sp:= MutableBasis( F, b );
while Length( B2 )+Length( B1 ) <> n do
x:= bvl[k];
if not IsContainedInSpan( sp, x ) then
Add( B2, x );
CloseMutableBasis( sp, x );
fi;
k:= k+1;
od;
ideals:= Flat([
DirectSumDecomposition(IdealNC( L, B1, "basis" )),
DirectSumDecomposition(IdealNC( L, B2, "basis" ))
]);
return ideals;
fi;
fi;
# Now we assume that `L' does not have a central component
# and compute the centralizer of `ad L' in `M_n(F)'.
adL:= List( bvl, x -> AdjointMatrix( BL, x ) );
centralizer:= FullMatrixAlgebraCentralizer( F, adL );
Rad:= RadicalOfAlgebra( centralizer );
if Dimension( centralizer ) - Dimension( Rad ) = 1 then
return [ L ];
fi;
# We calculate a complete set of orthogonal primitive idempotents
# in the Abelian algebra `centralizer/Rad'.
hom:= NaturalHomomorphismByIdeal( centralizer, Rad );
Q:= ImagesSource( hom );
SetCentre( Q, Q );
SetRadicalOfAlgebra( Q, Subalgebra( Q, [ Zero( Q ) ] ) );
id:= List( CentralIdempotentsOfAlgebra( Q ),
x->PreImagesRepresentative(hom,x));
# Now we lift the idempotents to the big algebra `A'. The
# first idempotent is lifted as follows:
# We have that `id[1]^2-id[1]' is an element of `Rad'.
# We construct the sequences e_{i+1} = e_i + n_i - 2e_in_i,
--> --------------------
--> maximum size reached
--> --------------------
