aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/rep2.spad.pamphlet
blob: 4219ab675a38f511db9cb7b1a4b3709e707d8bc4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra rep2.spad}
\author{Holger Gollan, Johannes Grabmeier}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject

\section{package REP2 RepresentationPackage2}

<<package REP2 RepresentationPackage2>>=
import Boolean
import Integer
import PositiveInteger
import List
import Vector
import Matrix

)abbrev package REP2 RepresentationPackage2
++ Authors: Holger Gollan, Johannes Grabmeier
++ Date Created: 10 September 1987
++ Date Last Updated: 20 August 1990
++ Basic Operations: areEquivalent?, isAbsolutelyIrreducible?,
++   split, meatAxe 
++ Related Constructors: RepresentationTheoryPackage1
++ Also See: IrrRepSymNatPackage
++ AMS Classifications:
++ Keywords: meat-axe, modular representation
++ Reference:
++   R. A. Parker: The Computer Calculation of Modular Characters
++   (The Meat-Axe), in M. D. Atkinson (Ed.), Computational Group Theory
++   Academic Press, Inc., London 1984
++   H. Gollan, J. Grabmeier: Algorithms in Representation Theory and
++    their Realization in the Computer Algebra System Scratchpad,
++    Bayreuther Mathematische Schriften, Heft 33, 1990, 1-23.
++ Description: 
++   RepresentationPackage2 provides functions for working with
++   modular representations of finite groups and algebra.
++   The routines in this package are created, using ideas of R. Parker,
++   (the meat-Axe) to get smaller representations from bigger ones, 
++   i.e. finding sub- and factormodules, or to show, that such the
++   representations are irreducible.
++   Note: most functions are randomized functions of Las Vegas type
++   i.e. every answer is correct, but with small probability
++   the algorithm fails to get an answer.
RepresentationPackage2(R): public == private where
 
  R    : Ring
  OF    ==> OutputForm
  I     ==> Integer
  L     ==> List
  SM    ==> SquareMatrix
  M     ==> Matrix
  NNI   ==> NonNegativeInteger
  V     ==> Vector
  PI    ==> PositiveInteger
  B     ==> Boolean
  RADIX ==> RadixExpansion
 
  public ==> with
 
    completeEchelonBasis : V V R  ->  M R
      ++ completeEchelonBasis(lv) completes the basis {\em lv} assumed
      ++ to be in echelon form of a subspace of {\em R**n} (n the length
      ++ of all the vectors in {\em lv}) with unit vectors to a basis of
      ++ {\em R**n}. It is assumed that the argument is not an empty
      ++ vector and that it is not the basis of the 0-subspace.
      ++ Note: the rows of the result correspond to the vectors of the basis.
    createRandomElement : (L M R, M R) -> M R
      ++ createRandomElement(aG,x) creates a random element of the group
      ++ algebra generated by {\em aG}. 
    -- randomWord : (L L I, L M)  ->  M R
      --++ You can create your own 'random' matrix with "randomWord(lli, lm)".
      --++ Each li in lli determines a product of matrices, the entries in li
      --++ determine which matrix from lm is chosen. Finally we sum over all
      --++ products. The result "sm" can be used to call split with (e.g.)
      --++ second parameter "first nullSpace sm"
    if R has EuclideanDomain then   -- using rowEchelon
      cyclicSubmodule  : (L M R, V R) ->   V V R
        ++ cyclicSubmodule(lm,v) generates a basis as follows.
        ++ It is assumed that the size n of the vector equals the number
        ++ of rows and columns of the matrices. Then the matrices generate
        ++ a subalgebra, say \spad{A}, of the algebra of all square matrices of
        ++ dimension n. {\em V R} is an \spad{A}-module in the natural way.
        ++ cyclicSubmodule(lm,v) generates the R-Basis of {\em Av} as
        ++ described in section 6 of R. A. Parker's "The Meat-Axe".
        ++ Note: in contrast to the description in "The Meat-Axe" and to
        ++ {\em standardBasisOfCyclicSubmodule} the result is in
        ++ echelon form.
      standardBasisOfCyclicSubmodule  : (L M R, V R) ->   M R
        ++ standardBasisOfCyclicSubmodule(lm,v) returns a matrix as follows.
        ++ It is assumed that the size n of the vector equals the number
        ++ of rows and columns of the matrices.  Then the matrices generate
        ++ a subalgebra, say \spad{A}, 
        ++ of the algebra of all square matrices of
        ++ dimension n. {\em V R} is an \spad{A}-module in the natural way.
        ++ standardBasisOfCyclicSubmodule(lm,v) calculates a matrix whose
        ++ non-zero column vectors are the R-Basis of {\em Av} achieved
        ++ in the way as described in section 6 
        ++ of R. A. Parker's "The Meat-Axe".
        ++ Note: in contrast to {\em cyclicSubmodule}, the result is not
        ++ in echelon form.
    if R has Field then  -- only because of inverse in SM
      areEquivalent? : (L M R, L M R, B, I) -> M R
        ++ areEquivalent?(aG0,aG1,randomelements,numberOfTries) tests
        ++ whether the two lists of matrices, all assumed of same
        ++ square shape, can be simultaneously conjugated by a non-singular
        ++ matrix. If these matrices represent the same group generators,
        ++ the representations are equivalent. 
        ++ The algorithm tries
        ++ {\em numberOfTries} times to create elements in the
        ++ generated algebras in the same fashion. If their ranks differ,
        ++ they are not equivalent. If an
        ++ isomorphism is assumed, then 
        ++ the kernel of an element of the first algebra
        ++ is mapped to the kernel of the corresponding element in the
        ++ second algebra. Now consider the one-dimensional ones.
        ++ If they generate the whole space (e.g. irreducibility !)
        ++ we use {\em standardBasisOfCyclicSubmodule} to create the
        ++ only possible transition matrix. The method checks whether the 
        ++ matrix conjugates all corresponding matrices from {\em aGi}.
        ++ The way to choose the singular matrices is as in {\em meatAxe}.
        ++ If the two representations are equivalent, this routine
        ++ returns the transformation matrix {\em TM} with
        ++ {\em aG0.i * TM = TM * aG1.i} for all i. If the representations
        ++ are not equivalent, a small 0-matrix is returned.
        ++ Note: the case
        ++ with different sets of group generators cannot be handled.
      areEquivalent? : (L M R, L M R) -> M R
        ++ areEquivalent?(aG0,aG1) calls {\em areEquivalent?(aG0,aG1,true,25)}.
        ++ Note: the choice of 25 was rather arbitrary.
      areEquivalent? : (L M R, L M R, I) -> M R
        ++ areEquivalent?(aG0,aG1,numberOfTries) calls
        ++ {\em areEquivalent?(aG0,aG1,true,25)}.
        ++ Note: the choice of 25 was rather arbitrary.
      isAbsolutelyIrreducible? : (L M R, I) -> B
        ++ isAbsolutelyIrreducible?(aG, numberOfTries) uses
        ++ Norton's irreducibility test to check for absolute
        ++ irreduciblity, assuming if a one-dimensional kernel is found.
        ++ As no field extension changes create "new" elements
        ++ in a one-dimensional space, the criterium stays true
        ++ for every extension. The method looks for one-dimensionals only
        ++ by creating random elements (no fingerprints) since
        ++ a run of {\em meatAxe} would have proved absolute irreducibility
        ++ anyway.
      isAbsolutelyIrreducible? : L M R -> B
        ++ isAbsolutelyIrreducible?(aG) calls
        ++ {\em isAbsolutelyIrreducible?(aG,25)}.
        ++ Note: the choice of 25 was rather arbitrary.
      split : (L M R, V R)  ->  L L M R
        ++ split(aG, vector) returns a subalgebra \spad{A} of all 
        ++ square matrix of dimension n as a list of list of matrices,
        ++ generated by the list of matrices aG, where n denotes both
        ++ the size of vector as well as the dimension of each of the
        ++ square matrices.
        ++ {\em V R} is an A-module in the natural way.
        ++ split(aG, vector) then checks whether the cyclic submodule
        ++ generated by {\em vector} is a proper submodule of {\em V R}.
        ++ If successful, it returns a two-element list, which contains
        ++ first the list of the representations of the submodule,
        ++ then the list of the representations of the factor module.
        ++ If the vector generates the whole module, a one-element list
        ++ of the old representation is given.
        ++ Note: a later version this should call the other split.
      split:  (L M R, V V R) -> L L M R
        ++ split(aG,submodule) uses a proper submodule of {\em R**n}
        ++ to create the representations of the submodule and of
        ++ the factor module.
    if (R has Finite) and (R has Field) then
      meatAxe  : (L M R, B, I, I)  ->  L L M R
        ++ meatAxe(aG,randomElements,numberOfTries, maxTests) returns
        ++ a 2-list of representations as follows.
        ++ All matrices of argument aG are assumed to be square
        ++ and of equal size.
        ++ Then \spad{aG} generates a subalgebra, say \spad{A}, of the algebra
        ++ of all square matrices of dimension n. {\em V R} is an A-module
        ++ in the usual way.  
        ++ meatAxe(aG,numberOfTries, maxTests) creates at most
        ++ {\em numberOfTries} random elements of the algebra, tests
        ++ them for singularity. If singular, it tries at most {\em maxTests}
        ++ elements of its kernel to generate a proper submodule.
        ++ If successful, a 2-list is returned: first, a list 
        ++ containing first the list of the
        ++ representations of the submodule, then a list of the
        ++ representations of the factor module.
        ++ Otherwise, if we know that all the kernel is already
        ++ scanned, Norton's irreducibility test can be used either
        ++ to prove irreducibility or to find the splitting.
        ++ If {\em randomElements} is {\em false}, the first 6 tries
        ++ use Parker's fingerprints.
      meatAxe : L M R -> L L M R
        ++ meatAxe(aG) calls {\em meatAxe(aG,false,25,7)} returns
        ++ a 2-list of representations as follows.
        ++ All matrices of argument \spad{aG} are assumed to be square
        ++ and of
        ++ equal size. Then \spad{aG} generates a subalgebra, 
        ++ say \spad{A}, of the algebra
        ++ of all square matrices of dimension n. {\em V R} is an A-module
        ++ in the usual way.  
        ++ meatAxe(aG) creates at most 25 random elements 
        ++ of the algebra, tests
        ++ them for singularity. If singular, it tries at most 7
        ++ elements of its kernel to generate a proper submodule.
        ++ If successful a list which contains first the list of the
        ++ representations of the submodule, then a list of the
        ++ representations of the factor module is returned.
        ++ Otherwise, if we know that all the kernel is already
        ++ scanned, Norton's irreducibility test can be used either
        ++ to prove irreducibility or to find the splitting.
        ++ Notes: the first 6 tries use Parker's fingerprints.
        ++ Also, 7 covers the case of three-dimensional kernels over 
        ++ the field with 2 elements.
      meatAxe: (L M R, B) ->  L L M R
        ++ meatAxe(aG, randomElements) calls {\em meatAxe(aG,false,6,7)},
        ++ only using Parker's fingerprints, if {\em randomElemnts} is false.
        ++ If it is true, it calls {\em  meatAxe(aG,true,25,7)},
        ++ only using random elements.
        ++ Note: the choice of 25 was rather arbitrary.
        ++ Also, 7 covers the case of three-dimensional kernels over the field
        ++ with 2 elements.
      meatAxe : (L M R, PI)  ->  L L M R
        ++ meatAxe(aG, numberOfTries) calls 
        ++ {\em meatAxe(aG,true,numberOfTries,7)}.
        ++ Notes: 7 covers the case of three-dimensional 
        ++ kernels over the field with 2 elements.
      scanOneDimSubspaces: (L V R, I)  ->  V R
        ++ scanOneDimSubspaces(basis,n) gives a canonical representative
        ++ of the {\em n}-th one-dimensional subspace of the vector space
        ++ generated by the elements of {\em basis}, all from {\em R**n}.
        ++ The coefficients of the representative are of shape
        ++ {\em (0,...,0,1,*,...,*)}, {\em *} in R. If the size of R
        ++ is q, then there are {\em (q**n-1)/(q-1)} of them.
        ++ We first reduce n modulo this number, then find the
        ++ largest i such that {\em +/[q**i for i in 0..i-1] <= n}.
        ++ Subtracting this sum of powers from n results in an
        ++ i-digit number to basis q. This fills the positions of the
        ++ stars.
        -- would prefer to have (V V R,....   but nullSpace  results
        -- in L V R
 
  private ==> add
 
    -- import of domain and packages
    import OutputForm
 
    -- declarations and definitions of local variables and
    -- local function
 
    blockMultiply: (M R, M R, L I, I) -> M R
      -- blockMultiply(a,b,li,n) assumes that a has n columns
      -- and b has n rows, li is a sublist of the rows of a and
      -- a sublist of the columns of b. The result is the
      -- multiplication of the (li x n) part of a with the
      -- (n x li) part of b. We need this, because just matrix
      -- multiplying the parts would require extra storage.
    blockMultiply(a, b, li, n) ==
      matrix([[ +/[a(i,s) * b(s,j) for s in 1..n ] _
        for j in li  ]  for i in li])
 
    fingerPrint: (NNI, M R, M R, M R) -> M R
      -- is local, because one should know all the results for smaller i
    fingerPrint (i : NNI, a : M R, b : M R, x :M R) ==
      -- i > 2 only gives the correct result if the value of x from
      -- the parameter list equals the result of fingerprint(i-1,...)
      (i::PI) = 1 => x := a + b + a*b
      (i::PI) = 2 => x := (x + a*b)*b
      (i::PI) = 3 => x := a + b*x
      (i::PI) = 4 => x := x + b
      (i::PI) = 5 => x := x + a*b
      (i::PI) = 6 => x := x - a + b*a
      error "Sorry, but there are only 6 fingerprints!"
      x
 
 
    -- definition of exported functions
 
 
    --randomWord(lli,lm)  ==
    --  -- we assume that all matrices are square of same size
    --  numberOfMatrices := #lm
    --  +/[*/[lm.(1+i rem numberOfMatrices) for i in li ] for li in lli]
 
    completeEchelonBasis(basis) ==
 
      dimensionOfSubmodule : NNI := #basis
      n : NNI := # basis.1
      indexOfVectorToBeScanned : NNI := 1
      row : NNI := dimensionOfSubmodule
 
      completedBasis : M R := zero(n, n)
      for i in 1..dimensionOfSubmodule repeat
        completedBasis := setRow!(completedBasis, i, basis.i)
      if #basis <= n then
        newStart : NNI := 1
        for j in 1..n
          while indexOfVectorToBeScanned <= dimensionOfSubmodule repeat
            if basis.indexOfVectorToBeScanned.j = 0 then
              completedBasis(1+row,j) := 1  --put unit vector into basis
              row := row + 1
            else
              indexOfVectorToBeScanned := indexOfVectorToBeScanned + 1
            newStart : NNI := j + 1
        for j in newStart..n repeat
          completedBasis(j,j) := 1  --put unit vector into basis
      completedBasis
 
 
    createRandomElement(aG,algElt) ==
      numberOfGenerators : NNI := #aG
      -- randomIndex := randnum numberOfGenerators
      randomIndex := 1+(random()$Integer rem numberOfGenerators)
      algElt := algElt * aG.randomIndex
      -- randomIndxElement := randnum numberOfGenerators
      randomIndex := 1+(random()$Integer rem numberOfGenerators)
      algElt + aG.randomIndex
 
 
    if R has EuclideanDomain then
      cyclicSubmodule (lm : L M R, v : V R)  ==
        basis : M R := rowEchelon matrix list entries v
        -- normalizing the vector
        -- all these elements lie in the submodule generated by v
        furtherElts : L V R := [(lm.i*v)::V R for i in 1..maxIndex lm]
        --furtherElts has elements of the generated submodule. It will
        --will be checked whether they are in the span of the vectors
        --computed so far. Of course we stop if we have got the whole
        --space.
        while (not null furtherElts) and (nrows basis < #v)  repeat
          w : V R := first furtherElts
          nextVector : M R := matrix list entries w -- normalizing the vector
          -- will the rank change if we add this nextVector
          -- to the basis so far computed?
          addedToBasis : M R := vertConcat(basis, nextVector)
          if rank addedToBasis ~= nrows basis then
             basis := rowEchelon addedToBasis  -- add vector w to basis
             updateFurtherElts : L V R := _
               [(lm.i*w)::V R for i in 1..maxIndex lm]
             furtherElts := append (rest furtherElts, updateFurtherElts)
          else
             -- the vector w lies in the span of matrix, no updating
             -- of the basis
             furtherElts := rest furtherElts
        vector [row(basis, i) for i in 1..maxRowIndex basis]
 
 
      standardBasisOfCyclicSubmodule (lm : L M R, v : V R)  ==
        dim   : NNI := #v
        standardBasis : L L R := list(entries v)
        basis : M R := rowEchelon matrix list entries v
        -- normalizing the vector
        -- all these elements lie in the submodule generated by v
        furtherElts : L V R := [(lm.i*v)::V R for i in 1..maxIndex lm]
        --furtherElts has elements of the generated submodule. It will
        --will be checked whether they are in the span of the vectors
        --computed so far. Of course we stop if we  have got the whole
        --space.
        while (not null furtherElts) and (nrows basis < #v)  repeat
          w : V R := first furtherElts
          nextVector : M R := matrix list entries w  -- normalizing the vector
          -- will the rank change if we add this nextVector
          -- to the basis so far computed?
          addedToBasis : M R := vertConcat(basis, nextVector)
          if rank addedToBasis ~= nrows basis then
             standardBasis := cons(entries w, standardBasis)
             basis := rowEchelon addedToBasis  -- add vector w to basis
             updateFurtherElts : L V R := _
               [lm.i*w for i in 1..maxIndex lm]
             furtherElts := append (rest furtherElts, updateFurtherElts)
          else
             -- the vector w lies in the span of matrix, therefore
             -- no updating of matrix
             furtherElts := rest furtherElts
        transpose matrix standardBasis
 
 
    if R has Field then  -- only because of inverse in Matrix
 
      -- as conditional local functions, *internal have to be here
 
      splitInternal: (L M R, V R, B) -> L L M R
      splitInternal(algebraGenerators : L M R, vector: V R,doSplitting? : B) ==
 
        n : I := # vector    -- R-rank of representation module =
                               -- degree of representation
        submodule : V V R := cyclicSubmodule (algebraGenerators,vector)
        rankOfSubmodule : I := # submodule  -- R-Rank of submodule
        submoduleRepresentation    : L M R := nil()
        factormoduleRepresentation : L M R := nil()
        if n ~= rankOfSubmodule then
          messagePrint "  A proper cyclic submodule is found."
          if doSplitting? then   -- no else !!
            submoduleIndices : L I := [i for i in 1..rankOfSubmodule]
            factormoduleIndices : L I := [i for i in (1+rankOfSubmodule)..n]
            transitionMatrix : M R := _
              transpose completeEchelonBasis submodule
            messagePrint "  Transition matrix computed"
            inverseTransitionMatrix := inverse(transitionMatrix)::M(R)
            messagePrint "  The inverse of the transition matrix computed"
            messagePrint "  Now transform the matrices"
            for i in 1..maxIndex algebraGenerators repeat
              helpMatrix : M R := inverseTransitionMatrix * algebraGenerators.i
              -- in order to not create extra space and regarding the fact
              -- that we only want the two blocks in the main diagonal we
              -- multiply with the aid of the local function blockMultiply
              submoduleRepresentation := cons( blockMultiply( _
                helpMatrix,transitionMatrix,submoduleIndices,n), _
                submoduleRepresentation)
              factormoduleRepresentation := cons( blockMultiply( _
                helpMatrix,transitionMatrix,factormoduleIndices,n), _
                factormoduleRepresentation)
          [reverse submoduleRepresentation, reverse _
            factormoduleRepresentation]
        else -- represesentation is irreducible
          messagePrint "  The generated cyclic submodule was not proper"
          [algebraGenerators]
 
 
 
      irreducibilityTestInternal: (L M R, M R, B) -> L L M R
      irreducibilityTestInternal(algebraGenerators,_
          singularMatrix,split?) ==
        algebraGeneratorsTranspose : L M R := [transpose _
           algebraGenerators.j for j in 1..maxIndex algebraGenerators]
        xt : M R := transpose singularMatrix
        messagePrint "  We know that all the cyclic submodules generated by all"
        messagePrint "    non-trivial element of the singular matrix under view are"
        messagePrint "    not proper, hence Norton's irreducibility test can be done:"
        -- actually we only would need one (!) non-trivial element from
        -- the kernel of xt, such an element must exist as the transpose
        -- of a singular matrix is of course singular. Question: Can
        -- we get it more easily from the kernel of x = singularMatrix?
        kernel : L V R := nullSpace xt
        result : L L M R :=  _
          splitInternal(algebraGeneratorsTranspose,first kernel,split?)
        if null rest result then  -- this means first kernel generates
          -- the whole module
          if 1 = #kernel then
             messagePrint "  Representation is absolutely irreducible"
          else
             messagePrint "  Representation is irreducible, but we don't know "
             messagePrint "    whether it is absolutely irreducible"
        else
          if split? then
            messagePrint "  Representation is not irreducible and it will be split:"
            -- these are the dual representations, so calculate the
            -- dual to get the desired result, i.e. "transpose inverse"
            -- improvements??
            for i in 1..maxIndex result repeat
              for j in 1..maxIndex (result.i) repeat
                mat : M R := result.i.j
                result.i.j := transpose(inverse(mat)::M(R))
          else
            messagePrint "  Representation is not irreducible, use meatAxe to split"
        -- if "split?" then dual representation interchange factor
        -- and submodules, hence reverse
        reverse result
 
 
 
      -- exported functions for FiniteField-s.
 
 
      areEquivalent? (aG0, aG1) ==
        areEquivalent? (aG0, aG1, true, 25)
 
 
      areEquivalent? (aG0, aG1, numberOfTries) ==
        areEquivalent? (aG0, aG1, true, numberOfTries)
 
 
      areEquivalent? (aG0, aG1, randomelements, numberOfTries) ==
          result : B := false
          transitionM : M R := zero(1, 1)
          numberOfGenerators  : NNI := #aG0
          -- need a start value for creating random matrices:
          -- if we switch to randomelements later, we take the last
          -- fingerprint.
          x0,x1: M R
          if randomelements then   -- random should not be from I
             --randomIndex  : I   := randnum numberOfGenerators
             randomIndex := 1+(random()$Integer rem numberOfGenerators)
             x0 := aG0.randomIndex
             x1 := aG1.randomIndex
          n : NNI := #row(x0,1)   -- degree  of representation
          foundResult : B := false
          for i in 1..numberOfTries until foundResult repeat
            -- try to create a non-singular element of the algebra
            -- generated by "aG". If only two generators,
            -- i < 7 and not "randomelements" use Parker's  fingerprints
            -- i >= 7 create random elements recursively:
            -- x_i+1 :=x_i * mr1 + mr2, where mr1 and mr2 are randomly
            -- chosen elements form "aG".
            if i = 7 then randomelements := true
            if randomelements then
               --randomIndex := randnum numberOfGenerators
               randomIndex := 1+(random()$Integer rem numberOfGenerators)
               x0 := x0 * aG0.randomIndex
               x1 := x1 * aG1.randomIndex
               --randomIndex := randnum numberOfGenerators
               randomIndex := 1+(random()$Integer rem numberOfGenerators)
               x0 := x0 + aG0.randomIndex
               x1 := x1 + aG1.randomIndex
            else
               x0 := fingerPrint (i, aG0.0, aG0.1 ,x0)
               x1 := fingerPrint (i, aG1.0, aG1.1 ,x1)
            -- test singularity of x0 and x1
            rk0 : NNI := rank x0
            rk1 : NNI := rank x1
            rk0 ~= rk1 =>
              messagePrint  "Dimensions of kernels differ"
              foundResult := true
              result := false
            -- can assume dimensions are equal
            rk0 ~= n - 1 =>
              -- not of any use here if kernel not one-dimensional
              if randomelements then
                messagePrint  "Random element in generated algebra does"
                messagePrint  "  not have a one-dimensional kernel"
              else
                messagePrint  "Fingerprint element in generated algebra does"
                messagePrint  "  not have a one-dimensional kernel"
            -- can assume dimensions are equal and equal to n-1
            if randomelements then
              messagePrint  "Random element in generated algebra has"
              messagePrint  "  one-dimensional kernel"
            else
              messagePrint  "Fingerprint element in generated algebra has"
              messagePrint  "  one-dimensional kernel"
            kernel0 : L V R := nullSpace x0
            kernel1 : L V R := nullSpace x1
            baseChange0 : M R := standardBasisOfCyclicSubmodule(_
              aG0,kernel0.1)
            baseChange1 : M R := standardBasisOfCyclicSubmodule(_
              aG1,kernel1.1)
            (ncols baseChange0) ~= (ncols baseChange1) =>
              messagePrint  "  Dimensions of generated cyclic submodules differ"
              foundResult := true
              result := false
            -- can assume that dimensions of cyclic submodules are equal
            (ncols baseChange0) = n =>   -- full dimension
              transitionM := baseChange0 * (inverse(baseChange1)::M(R))
              foundResult := true
              result := true
              for j in 1..numberOfGenerators while result repeat
                if (aG0.j*transitionM) ~= (transitionM*aG1.j) then
                  result := false
                  transitionM := zero(1 ,1)
                  messagePrint "  There is no isomorphism, as the only possible one"
                  messagePrint "    fails to do the necessary base change"
            -- can assume that dimensions of cyclic submodules are not "n"
            messagePrint  "  Generated cyclic submodules have equal, but not full"
            messagePrint  "    dimension, hence we can not draw any conclusion"
          -- here ends the for-loop
          if not foundResult then
            messagePrint  " "
            messagePrint  "Can neither prove equivalence nor inequivalence."
            messagePrint  "  Try again."
          else
            if result then
              messagePrint  " "
              messagePrint  "Representations are equivalent."
            else
              messagePrint  " "
              messagePrint  "Representations are not equivalent."
          transitionM
 
 
      isAbsolutelyIrreducible?(aG) == isAbsolutelyIrreducible?(aG,25)
 
 
      isAbsolutelyIrreducible?(aG, numberOfTries) ==
        result : B := false
        numberOfGenerators  : NNI := #aG
        -- need a start value for creating random matrices:
        -- randomIndex  : I   := randnum numberOfGenerators
        randomIndex := 1+(random()$Integer rem numberOfGenerators)
        x : M R := aG.randomIndex
        n : NNI := #row(x,1)   -- degree  of representation
        foundResult : B := false
        for i in 1..numberOfTries until foundResult repeat
          -- try to create a non-singular element of the algebra
          -- generated by "aG", dimension of its kernel being 1.
          -- create random elements recursively:
          -- x_i+1 :=x_i * mr1 + mr2, where mr1 and mr2 are randomly
          -- chosen elements form "aG".
          -- randomIndex := randnum numberOfGenerators
          randomIndex := 1+(random()$Integer rem numberOfGenerators)
          x := x * aG.randomIndex
          --randomIndex := randnum numberOfGenerators
          randomIndex := 1+(random()$Integer rem numberOfGenerators)
          x := x + aG.randomIndex
          -- test whether rank of x is n-1
          rk : NNI := rank x
          if rk = n - 1 then
            foundResult := true
            messagePrint "Random element in generated algebra has"
            messagePrint "  one-dimensional kernel"
            kernel : L V R := nullSpace x
            if n=#cyclicSubmodule(aG, first kernel) then
              result := (irreducibilityTestInternal(aG,x,false)).1 ~= nil()$(L M R)
              -- result := not null? first irreducibilityTestInternal(aG,x,false) -- this down't compile !!
            else -- we found a proper submodule
              result := false
              --split(aG,kernel.1) -- to get the splitting
          else -- not of any use here if kernel not one-dimensional
            messagePrint "Random element in generated algebra does"
            messagePrint "  not have a one-dimensional kernel"
        -- here ends the for-loop
        if not foundResult then
          messagePrint "We have not found a one-dimensional kernel so far,"
          messagePrint "  as we do a random search you could try again"
        --else
        --  if not result then
        --    messagePrint "Representation is not irreducible."
        --  else
        --    messagePrint "Representation is irreducible."
        result
 
 
 
      split(algebraGenerators: L M R, vector: V R) ==
        splitInternal(algebraGenerators, vector, true)
 
 
      split(algebraGenerators : L M R, submodule: V V R) == --not zero submodule
        n : NNI := #submodule.1 -- R-rank of representation module =
                                -- degree of representation
        rankOfSubmodule : I := (#submodule) :: I --R-Rank of submodule
        submoduleRepresentation    : L M R := nil()
        factormoduleRepresentation : L M R := nil()
        submoduleIndices : L I := [i for i in 1..rankOfSubmodule]
        factormoduleIndices : L I := [i for i in (1+rankOfSubmodule)..(n::I)]
        transitionMatrix : M R := _
          transpose completeEchelonBasis submodule
        messagePrint "  Transition matrix computed"
        inverseTransitionMatrix := inverse(transitionMatrix)::M(R)
        messagePrint "  The inverse of the transition matrix computed"
        messagePrint "  Now transform the matrices"
        for i in 1..maxIndex algebraGenerators repeat
          helpMatrix : M R := inverseTransitionMatrix * algebraGenerators.i
          -- in order to not create extra space and regarding the fact
          -- that we only want the two blocks in the main diagonal we
          -- multiply with the aid of the local function blockMultiply
          submoduleRepresentation := cons( blockMultiply( _
            helpMatrix,transitionMatrix,submoduleIndices,n), _
            submoduleRepresentation)
          factormoduleRepresentation := cons( blockMultiply( _
            helpMatrix,transitionMatrix,factormoduleIndices,n), _
            factormoduleRepresentation)
        cons(reverse submoduleRepresentation, list( reverse _
          factormoduleRepresentation)::(L L M R))
 
 
    -- the following is "under"  "if R has Field", as there are compiler
    -- problems with conditinally defined local functions, i.e. it
    -- doesn't know, that "FiniteField" has "Field".
 
 
      -- we are scanning through the vectorspaces
      if (R has Finite) and (R has Field) then
 
        meatAxe(algebraGenerators, randomelements, numberOfTries, _
           maxTests) ==
          numberOfGenerators  : NNI := #algebraGenerators
          result : L L M R := nil()$(L L M R)
          q   : PI  := size()$R:PI
          -- need a start value for creating random matrices:
          -- if we switch to randomelements later, we take the last
          -- fingerprint.
          if randomelements then   -- random should not be from I
             --randomIndex  : I   := randnum numberOfGenerators
             randomIndex := 1+(random()$Integer rem numberOfGenerators)
             x : M R := algebraGenerators.randomIndex
          foundResult : B := false
          for i in 1..numberOfTries until foundResult repeat
            -- try to create a non-singular element of the algebra
            -- generated by "algebraGenerators". If only two generators,
            -- i < 7 and not "randomelements" use Parker's  fingerprints
            -- i >= 7 create random elements recursively:
            -- x_i+1 :=x_i * mr1 + mr2, where mr1 and mr2 are randomly
            -- chosen elements form "algebraGenerators".
            if i = 7 then randomelements := true
            if randomelements then
               --randomIndex := randnum numberOfGenerators
               randomIndex := 1+(random()$Integer rem numberOfGenerators)
               x := x * algebraGenerators.randomIndex
               --randomIndex := randnum numberOfGenerators
               randomIndex := 1+(random()$Integer rem numberOfGenerators)
               x := x + algebraGenerators.randomIndex
            else
               x := fingerPrint (i, algebraGenerators.1,_
                 algebraGenerators.2 , x)
            -- test singularity of x
            n : NNI := #row(x, 1)  -- degree  of representation
            if (rank x) ~= n then  -- x singular
              if randomelements then
                 messagePrint "Random element in generated algebra is singular"
              else
                 messagePrint "Fingerprint element in generated algebra is singular"
              kernel : L V R := nullSpace x
              -- the first number is the maximal number of one dimensional
              -- subspaces of the kernel, the second is a user given
              -- constant
              numberOfOneDimSubspacesInKernel : I := (q**(#kernel)-1)quo(q-1)
              numberOfTests : I :=  _
                min(numberOfOneDimSubspacesInKernel, maxTests)
              for j in 1..numberOfTests repeat
                 --we create an element in the kernel, there is a good
                 --probability for it to generate a proper submodule, the
                 --called "split" does the further work:
                 result := _
                   split(algebraGenerators,scanOneDimSubspaces(kernel,j))
                 -- we had "not null rest result" directly in the following
                 -- if .. then, but the statment there foundResult := true
                 -- didn't work properly
                 foundResult :=  not null rest result
                 if foundResult then
                   leave -- inner for-loop
                   -- finish here with result
                 else  -- no proper submodule
                   -- we were not successfull, i.e gen. submodule was
                   -- not proper, if the whole kernel is already scanned,
                   -- Norton's irreducibility test is used now.
                   if (j+1)>numberOfOneDimSubspacesInKernel then
                     -- we know that all the cyclic submodules generated
                     -- by all non-trivial elements of the kernel are proper.
                     foundResult := true
                     result : L L M R := irreducibilityTestInternal (_
                       algebraGenerators,x,true)
                     leave  -- inner for-loop
              -- here ends the inner for-loop
            else  -- x non-singular
              if randomelements then
                messagePrint "Random element in generated algebra is non-singular"
              else
                messagePrint "Fingerprint element in generated algebra is non-singular"
          -- here ends the outer for-loop
          if not foundResult then
             result : L L M R := [nil()$(L M R), nil()$(L M R)]
             messagePrint " "
             messagePrint "Sorry, no result, try meatAxe(...,true)"
             messagePrint "  or consider using an extension field."
          result
 
 
        meatAxe (algebraGenerators) ==
          meatAxe(algebraGenerators, false, 25, 7)
 
 
        meatAxe (algebraGenerators: L M R, randomElements?: Boolean) ==
          randomElements? => meatAxe (algebraGenerators, true, 25, 7)
          meatAxe(algebraGenerators, false, 6, 7)
 
 
        meatAxe (algebraGenerators:L M R, numberOfTries:PI) ==
          meatAxe (algebraGenerators, true, numberOfTries, 7)
 
 
 
        scanOneDimSubspaces(basis,n) ==
          -- "dimension" of subspace generated by "basis"
          dim : NNI := #basis
          -- "dimension of the whole space:
          nn : NNI := #(basis.1)
          q : NNI := size()$R
          -- number of all one-dimensional subspaces:
          nred : I := n rem ((q**dim -1) quo (q-1))
          pos : I := nred
          i : I := 0
          for i: free in 0..dim-1 while nred >= 0 repeat
            pos := nred
            nred := nred - (q**i)
          i  := if i = 0 then 0 else i-1
          coefficients : V R := new(dim,0$R)
          coefficients.(dim-i) := 1$R
          iR : L I := wholeRagits(pos::RADIX q)
          for j in 1..(maxIndex iR) repeat
            coefficients.(dim-((#iR)::I) +j) := index((iR.j+(q::I))::PI)$R
          result : V R := new(nn,0)
          for i: local in 1..maxIndex coefficients repeat
            newAdd : V R := coefficients.i * basis.i
            for j in 1..nn repeat
              result.j := result.j + newAdd.j
          result

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<package REP2 RepresentationPackage2>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}