This chapter documents various functions which enhance GAP3's ability to work with matrices.
EigenvaluesMat( mat )
mat should be a square matrix of Cyclotomics. The function returns the eigenvalues of M which are 0 or roots of unity.
gap> EigenvaluesMat(DiagonalMat(0,1,E(3),2,3)); [ 0, 1, E(3) ] gap> EigenvaluesMat(PermutationMat((1,2,3,4),5)); [ 1, 1, -1, E(4), -E(4) ]
DecomposedMat( mat )
Finds if the square matrix mat with zeroes (or false
) in symmetric
positions admits a block decomposition.
Define a graph G with vertices [1..Length(mat)]
and with an edge
between i
and j
if either mat[i][j]
or mat[j][i]
is non-zero.
DecomposedMat
return a list of lists l
such that l[1],l[2]
, etc.. are
the vertices in each connected component of G. In other words, the
matrices mat{l[1]}{l[1]},mat{l[2]}{l[2]}
, etc... are blocks of
the matrix mat. This function may also be applied to boolean matrices
where non-zero is replaced by true
.
gap> m := [ [ 0, 0, 0, 1 ], > [ 0, 0, 1, 0 ], > [ 0, 1, 0, 0 ], > [ 1, 0, 0, 0 ] ];; gap> DecomposedMat( m ); [ [ 1, 4 ], [ 2, 3 ] ] gap> PrintArray( m{[ 1, 4 ]}{[ 1, 4 ]}); [[0, 1], [1, 0]]
BlocksMat( M )
Finds if the matrix M admits a block decomposition.
Define a bipartite graph G with vertices [1..Length(M)]
,
[1..Length(M[1])]
and with an edge between i
and j
if M[i][j]
is
not zero. BlocksMat returns a list of pairs of lists I
such that
[I[1][1],I[1][2]]
, etc.. are the vertices in each connected component of
G. In other words, M{I[1][1]}{I[1][2]}
, M{I[2][1]}{I[2][2]}
,etc...
are blocks of M
.
This function may also be applied to boolean matrices where non-zero is
replaced by true
.
gap> m:=[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 1, 0 ], > [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ] ];; gap> BlocksMat(m); [ [ [ 1, 3, 5 ], [ 1, 3 ] ], [ [ 2 ], [ 2 ] ], [ [ 4 ], [ 4 ] ] ] gap> PrintArray(m{[1,3,5]}{[1,3]}); [[1, 0], [1, 1], [0, 1]]
105.4 RepresentativeDiagonalConjugation
RepresentativeDiagonalConjugation( M, N )
M and N must be square matrices. This function returns a list d
such that N=M^DiagonalMat(d)
if such a list exists, and false
otherwise.
gap> M:=[[1,2],[2,1]]; [ [ 1, 2 ], [ 2, 1 ] ] gap> N:=[[1,4],[1,1]]; [ [ 1, 4 ], [ 1, 1 ] ] gap> RepresentativeDiagonalConjugation(M,N); [ 1, 2 ]
Transporter( l1, l2 )
l1 and l2 should be lists of the same length of square matrices all of
the same size. The result is a basis of the vector space of matrices A
such that for any i we have A*l1[i]=l2[i]*A
--- the basis is returned
as a list, empty if the vector space is 0. This is useful to find whether
two representations are isomorphic.
gap> W:=CoxeterGroup("A",3); CoxeterGroup("A",3) gap> Transporter(W.matgens,List(W.matgens,x->x^W.matgens[1])); [ [ [ 1, 0, 0 ], [ -1, -1, 0 ], [ 0, 0, -1 ] ] ] gap> W.matgens[1]; [ [ -1, 0, 0 ], [ 1, 1, 0 ], [ 0, 0, 1 ] ] gap> Transporter([W.matgens[1]],[W.matgens[1]]); [ [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 0 ] ], [ [ 0, 0, 0 ], [ 1, 2, 0 ], [ 0, 0, 0 ] ], [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 0, 0 ] ], [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 1, 2, 0 ] ], [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ] ]
In the second case above, we get a base of the centralizer in matrices of
W.matgens[1]
.
105.6 ProportionalityCoefficient
ProportionalityCoefficient( v, w )
v and w should be two vectors of the same length. The function
returns a scalar c such that v=c*w
if such a scalar exists, and
false
otherwise.
gap> ProportionalityCoefficient([1,2],[2,4]); 1/2 gap> ProportionalityCoefficient([1,2],[2,3]); false
ExteriorPower( mat, n )
mat should be a square matrix. The function returns the n-th exterior
power of mat, in the basis naturally indexed by Combinations([1..r],n)
,
where r=Length(<mat>)
.
gap> M:=[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]; [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 1 ], [ 3, 4, 1, 2 ], [ 4, 1, 2, 3 ] ] gap> ExteriorPower(M,2); [ [ -1, -2, -7, -1, -10, -13 ], [ -2, -8, -10, -10, -12, 2 ], [ -7, -10, -13, 1, 2, 1 ], [ -1, -10, 1, -13, 2, 7 ], [ -10, -12, 2, 2, 8, 10 ], [ -13, 2, 1, 7, 10, -1 ] ]
SymmetricPower( mat, n )
mat should be a square matrix. The function returns the n-th symmetric
power of mat, in the basis naturally indexed by UnorderedTuples([1..r],n)
,
where r=Length(<mat>)
.
gap> M:=[[1,2],[3,4]]; [ [ 1, 2 ], [ 3, 4 ] ] gap> SymmetricPower(M,2); [ [ 1, 2, 4 ], [ 6, 10, 16 ], [ 9, 12, 16 ] ]
SchurFunctor(mat,l)
mat should be a square matrix and l a partition. The result is the
Schur functor of the matrix mat corresponding to partition l; for
example, if l=[n]
it returns the n-th symmetric power and if l=[1,1,1]
it returns the 3rd exterior power. The current algorithm (from Littlewood)
is rather inefficient so it is quite slow for partitions of n where n>6.
gap> m:=CartanMat("A",3); [ [ 2, -1, 0 ], [ -1, 2, -1 ], [ 0, -1, 2 ] ] gap> SchurFunctor(m,[2,2]); [ [ 10, 12, -16, 16, -16, 12 ], [ 3/2, 9, -6, 4, -2, 1 ], [ -4, -12, 16, -16, 8, -4 ], [ 2, 4, -8, 16, -8, 4 ], [ -4, -4, 8, -16, 16, -12 ], [ 3/2, 1, -2, 4, -6, 9 ] ]
IsNormalizing( lst, mat )
returns true or false according to whether the matrix mat leaves the
vectors in lst as a set invariant, i.e., Set(l * M) = Set( l )
.
gap> a := [ [ 1, 2 ], [ 3, 1 ] ];; gap> l := [ [ 1, 0 ], [ 0, 1 ], [ 1, 1 ], [ 0, 0 ] ];; gap> l * a; [ [ 1, 2 ], [ 3, 1 ], [ 4, 3 ], [ 0, 0 ] ] gap> IsNormalizing( l, a ); false
IndependentLines( M )
Returns the smallest (for lexicographic order) subset I of [1..Length(M)]
such that the rank of M{I}
is equal to the rank of M.
gap> M:=CartanMat(ComplexReflectionGroup(31)); [ [ 2, 1+E(4), 1-E(4), -E(4), 0 ], [ 1-E(4), 2, 1-E(4), -1, -1 ], [ 1+E(4), 1+E(4), 2, 0, -1 ], [ E(4), -1, 0, 2, 0 ], [ 0, -1, -1, 0, 2 ] ] gap> IndependentLines(M); [ 1, 2, 4, 5 ]
OnMatrices( M , p)
Effects the simultaneous permutation of the lines and columns of the matrix M specified by the permutation p.
gap> M:=DiagonalMat([1,2,3]); [ [ 1, 0, 0 ], [ 0, 2, 0 ], [ 0, 0, 3 ] ] gap> OnMatrices(M,(1,2,3)); [ [ 3, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 2 ] ]
PermutedByCols( M , p)
Effects the permutation p on the columns of matrix M.
gap> m:=List([0..2],i->3*i+[1..3]); [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] gap> PermutedByCols(m,(1,2,3)); [ [ 3, 1, 2 ], [ 6, 4, 5 ], [ 9, 7, 8 ] ]
MatStab(M[, l])
Fast implementation of
Stabilizer(SymmetricGroup(Length(M)),M,OnMatrices)
. The program uses
sophisticated algorithms, and can handle matrices up to 80× 80.
gap> uc:=UnipotentCharacters(ComplexReflectionGroup(34)); UnipotentCharacters( G34 ) gap> MatStab(Fourier(uc.families[20])); Group( ( 7,38), (39,44)(40,43)(41,42) )
PermMatMat( M , N [, l1, l2])
M and N should be symmetric matrices. PermMatMat
returns a
permutation p such that OnMatrices(M,p)=N
if such a permutation
exists, and false
otherwise. If list arguments l1 and l2 are
given, the permutation p should also satisfy Permuted(l1,p)=l2
.
This routine is useful to identify two objects which are isomorphic but with different labelings. It is used in CHEVIE to identify Cartan matrices and Lusztig Fourier transform matrices with standard (classified) data. The program uses sophisticated algorithms, and can often handle matrices up to 80× 80.
gap> M:=CartanMat("D",12);; gap> p:=( 1,12, 7, 5, 9, 8, 3, 6)( 2,10)( 4,11);; gap> N:=OnMatrices(M,p);; gap> PermMatMat(M,N); ( 1,12, 7, 5, 9, 8, 3, 6)( 2,10)( 4,11)
105.16 RepresentativeRowColPermutation
RepresentativeRowColPermutation(M1, M2)
M1 and M2 should be rectangular matrices of the same dimensions. The
function returns a pair of permutations [p1,p2]
such that
PermutedByCols(Permuted(m1,p1),p2)=Permuted(PermutedByCols(m1,p2),p1)=m2
if such permutations exist, and false
otherwise.
gap> ct:=CharTable(CoxeterGroup("A",5)); CharTable( "A5" ) gap> ct1:=CharTable(Group((1,2,3,4,5,6),(1,2))); CharTable( Group( (1,2,3,4,5,6), (1,2) ) ) gap> RepresentativeRowColPermutation(ct.irreducibles,ct1.irreducibles); [ ( 1, 2, 5, 9, 8,10, 6,11)( 3, 7), ( 3, 4, 8, 5)( 7,10) ]
BigCellDecomposition(M [, b])
M should be a square matrix, and b specifies a block structure for a
matrix of same size as M (it is a list of lists whose union is
[1..Length(M)]
). If b is not given, the trivial block structure
[[1],..,[Length(M)]]
is assumed.
The function decomposes M as a product P1 L P where P is upper
block-unitriangular (with identity diagonal blocks), P1 is lower
block-unitriangular and L is block-diagonal for the block structure b.
If M is symmetric then P1 is the transposed of P and the result is
the pair [P,L]
; else the result is the triple [P1,L,P]
. The only
condition for this decomposition of M to be possible is that the
principal minors according to the block structure be invertible. This
routine is used when computing the green functions and the example below is
extracted from the computation of the Green functions for G2.
gap> q:=X(Rationals);;q.name:="q";; gap> M:= [ [ q^6, q^0, q^3, q^3, q^5 + q, q^4 + q^2 ], > [ q^0, q^6, q^3, q^3, q^5 + q, q^4 + q^2 ], > [ q^3, q^3, q^6, q^0, q^4 + q^2, q^5 + q ], > [ q^3, q^3, q^0, q^6, q^4 + q^2, q^5 + q ], > [ q^5 + q, q^5 + q, q^4 + q^2, q^4 + q^2, q^6 + q^4 + q^2 + 1, > q^5 + 2*q^3 + q ], > [ q^4 + q^2, q^4 + q^2, q^5 + q, q^5 + q, q^5 + 2*q^3 + q, > q^6 + q^4 + q^2 + 1 ] ];; gap> bb:=[ [ 2 ], [ 4 ], [ 6 ], [ 3, 5 ], [ 1 ] ];; gap> PL:=BigCellDecomposition(M,bb); [ [ [ q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0 ], [ q^(-6), q^0, q^(-3), q^(-3), q^(-1) + q^(-5), q^(-2) + q^(-4) ], [ 0*q^0, 0*q^0, q^0, 0*q^0, 0*q^0, 0*q^0 ], [ q^(-3), 0*q^0, 0*q^0, q^0, q^(-2), q^(-1) ], [ q^(-1), 0*q^0, 0*q^0, 0*q^0, q^0, 0*q^0 ], [ q^(-2), 0*q^0, q^(-1), 0*q^0, q^(-1), q^0 ] ], [ [ q^6 - q^4 - 1 + q^(-2), 0*q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0 ], [ 0*q^0, q^6, 0*q^0, 0*q^0, 0*q^0, 0*q^0 ], [ 0*q^0, 0*q^0, q^6 - q^4 - 1 + q^(-2), 0*q^0, 0*q^0, 0*q^0 ], [ 0*q^0, 0*q^0, 0*q^0, q^6 - 1, 0*q^0, 0*q^0 ], [ 0*q^0, 0*q^0, 0*q^0, 0*q^0, q^6 - q^4 - 1 + q^(-2), 0*q^0 ], [ 0*q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0, q^6 - 1 ] ] ] gap> M=TransposedMat(PL[1])*PL[2]*PL[1]; true
gap3-jm