  
  [1X5 [33X[0;0YUtility Functions[133X[101X
  
  
  [1X5.1 [33X[0;0YMatrix Functions[133X[101X
  
  [1X5.1-1 MatrixByEntries[101X
  
  [33X[1;0Y[29X[2XMatrixByEntries[102X( [3Xfield[103X, [3XnrRows[103X, [3XnrCols[103X, [3Xentries[103X ) [32X function[133X
  
  [33X[0;0YReturn a [3XnrRows[103X by [3XnrCols[103X matrix with entries over the field [3Xfield[103X which are
  given  by  the  list  [3Xentries[103X  in the following way: If [3Xentries[103X is a list of
  three-element lists [10X[i, j, a][110X, then the entry in position [10X(i, j)[110X will be set
  to  [10Xa[110X  (and  to  zero if [3Xentries[103X does not contain a list [10X[i, j, a][110X with some
  arbitrary [10Xa[110X); if this is not the case and [3Xentries[103X is a list of length [10XnrRows
  *  nrCols[110X,  the  elements  of [3Xentries[103X will be written into the matrix row by
  row.[133X
  
  [1X5.1-2 AntidiagonalMat[101X
  
  [33X[1;0Y[29X[2XAntidiagonalMat[102X( [3Xentries[103X, [3Xfield[103X ) [32X function[133X
  
  [33X[0;0YReturn  an  antidiagonal  matrix [10XM[110X with entries as specified by the argument
  [3Xentries[103X in the following way:[133X
  
  [30X    [33X[0;6YIf  [3Xentries[103X  is a list, the entries of [10XM[110X are, from top right to bottom
        left, the entries of that list.[133X
  
  [30X    [33X[0;6YIf [3Xentries[103X is an integer, the entries of [10XM[110X are all ones and the number
        of them is [3Xentries[103X.[133X
  
  [1X5.1-3 AntidiagonalHalfOneMat[101X
  
  [33X[1;0Y[29X[2XAntidiagonalHalfOneMat[102X( [3Xd[103X, [3Xfield[103X ) [32X function[133X
  
  [33X[0;0YReturn  an  antidiagonal  [3Xd[103X by [3Xd[103X matrix over the given field, with the first
  half of the entries on the antidiagonal equal to one, the reaming half equal
  to minus one. Note that [3Xd[103X must be even.[133X
  
  [1X5.1-4 RotateMat[101X
  
  [33X[1;0Y[29X[2XRotateMat[102X( [3XA[103X ) [32X function[133X
  
  [33X[0;0YReturn  the  matrix  [10XB[110X  which  is  the rotation of [10XA[110X by 180 degrees. This is
  equivalent  to  multiplying  [10XA[110X  by  the correctly sized matrices of the form
  AntiDiag(1,  ...,  1)  from the left and right respectively, but rotation is
  more efficient than matrix multiplication.[133X
  
  
  [1X5.2 [33X[0;0YCreating Matrix Groups[133X[101X
  
  [1X5.2-1 MatrixGroup[101X
  
  [33X[1;0Y[29X[2XMatrixGroup[102X( [3XF[103X, [3Xgens[103X ) [32X function[133X
  
  [33X[0;0YReturn  a  matrix  group  [10XG[110X  generated  by the matrices in [3Xgens[103X, regarded as
  matrices  over the field [3XF[103X. The generators are stored as immutable matrices;
  over  small  fields  (with  at  most  256  elements)  this yields compressed
  matrices   that   store   the  base  field,  but  not  over  larger  fields.
  Consequently,    the    attribute    [2XDefaultFieldOfMatrixGroup[102X   ([14XReference:
  DefaultFieldOfMatrixGroup[114X)  of  the resulting group is not necessarily equal
  to  [3XF[103X and may in fact be a proper subfield when the entries lie in a smaller
  field.[133X
  
  [1X5.2-2 MatrixGroupWithSize[101X
  
  [33X[1;0Y[29X[2XMatrixGroupWithSize[102X( [3XF[103X, [3Xgens[103X, [3Xsize[103X ) [32X function[133X
  
  [33X[0;0YReturn  a  matrix  group over the field [3XF[103X generated by the matrices from the
  list  [3Xgens[103X  and  set  its  size to [3Xsize[103X. Except for additionally setting the
  group's size, this does the same as [2XMatrixGroup[102X ([14X5.2-1[114X).[133X
  
  
  [1X5.3 [33X[0;0YSpecial generators for classical groups[133X[101X
  
  [33X[0;0YThis  section  provides  functions to construct explicit generating sets for
  classical groups, namely orthogonal and linear groups over finite fields, as
  used in [HR05] and [HR10].[133X
  
  [1X5.3-1 GeneratorsOfOrthogonalGroup[101X
  
  [33X[1;0Y[29X[2XGeneratorsOfOrthogonalGroup[102X( [3Xepsilon[103X, [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya record with components [10XgeneratorsOfSO[110X, [10XD[110X and [10XE[110X.[133X
  
  [33X[0;0YConstructs  generators  for the orthogonal groups with the properties listed
  in [HR05, Lemma 2.4]. Construction as in [Ron04, Lemma 2.4].[133X
  
  [1X5.3-2 StandardGeneratorsOfOrthogonalGroup[101X
  
  [33X[1;0Y[29X[2XStandardGeneratorsOfOrthogonalGroup[102X( [3Xepsilon[103X, [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya record with components [10XgeneratorsOfOmega[110X, [10XS[110X, [10XG[110X and [10XD[110X.[133X
  
  [33X[0;0YConstructs standard generators [10XgeneratorsOfOmega[110X, [10XS[110X, [10XG[110X, [10XD[110X for the orthogonal
  groups  with  respect  to  our  standard  form  as  used in [HR10], with the
  following properties:[133X
  
  [30X    [33X[0;6Y[10XgeneratorsOfOmega[110X generate [23X\Omega^\varepsilon_n(q)[123X[133X
  
  [30X    [33X[0;6Y[10XgeneratorsOfOmega[110X and [10XS[110X generate [23X{\rm SO}_n(q)[123X[133X
  
  [30X    [33X[0;6Y[10XgeneratorsOfOmega[110X and [10XG[110X generate [23X{\rm GO}_n(q)[123X[133X
  
  [30X    [33X[0;6Ythe spinor norm of [10XG[110X is [23X1[123X[133X
  
  [30X    [33X[0;6Y[10XD[110X      generates     [23X{\rm     CO}^\varepsilon_n(q)[123X     modulo     [23X{\rm
        GO}^\varepsilon_n(q)[123X.[133X
  
  [33X[0;0YConstruction as in Theorem 3.9 loc. cit.[133X
  
  [1X5.3-3 AlternativeGeneratorsOfOrthogonalGroup[101X
  
  [33X[1;0Y[29X[2XAlternativeGeneratorsOfOrthogonalGroup[102X( [3Xn[103X, [3Xq[103X, [3XsquareDiscriminant[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya record with components [10XgeneratorsOfOmega[110X, [10XS[110X, [10XG[110X and [10XD[110X.[133X
  
  [33X[0;0YConstructs standard generators [10XgeneratorsOfOmega[110X, [10XS[110X, [10XG[110X, [10XD[110X for the orthogonal
  groups  with  respect  to our [13Xdiagonal form[113X of given discriminant as used in
  [HR10].[133X
  
  [33X[0;0YThe  generators  satisfy  exactly  the  same properties as those returned by
  [2XStandardGeneratorsOfOrthogonalGroup[102X    ([14X5.3-2[114X),   except   that   they   are
  constructed  with  respect to a diagonal form (rather than the standard form
  used there).[133X
  
  [33X[0;0YNote  that  the  parameter  [23X\varepsilon[123X  is  uniquely determined by [3Xn[103X, [3Xq[103X and
  [3XsquareDiscriminant[103X.[133X
  
  [33X[0;0YConstruction as in Theorem 3.9 loc. cit.[133X
  
  [33X[0;0Y[3Xq[103X must be odd.[133X
  
  [1X5.3-4 StandardGeneratorsOfLinearGroup[101X
  
  [33X[1;0Y[29X[2XStandardGeneratorsOfLinearGroup[102X( [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya record with components [10XL1[110X, [10XL2[110X and [10XL3[110X.[133X
  
  [33X[0;0YConstructs  standard  generators  [10XL1[110X,  [10XL2[110X,  [10XL3[110X  as  used  in [HR10] with the
  following properties (analogous to Theorem 3.11 loc. cit.):[133X
  
  [30X    [33X[0;6Y[10XL1[110X and [10XL2[110X generate [23X{\rm GL}_n(q)[123X.[133X
  
  [30X    [33X[0;6Y[10XL1[110X and [10XL3[110X generate [23X{\rm SL}_n(q)[123X.[133X
  
  [30X    [33X[0;6Yall matrix entries lie in [23X\{0, \pm 1, \pm \zeta^{\pm 1}\}[123X, where [23X\zeta[123X
        is a primitive element of [23X\mathbb{F}_q[123X.[133X
  
  [30X    [33X[0;6YIf  [10Xq[110X  is  odd, [10XL1[110X and [10XL2^2[110X generate the unique subgroup of index 2 in
        [23X{\rm GL}_n(q)[123X, often denoted [23X\frac{1}{2} {\rm GL}_n(q)[123X.[133X
  
  [33X[0;0YThe construction is taken from [Tay87].[133X
  
  
  [1X5.4 [33X[0;0YSizes of classical groups[133X[101X
  
  [33X[0;0YThis  section  provides functions to compute the orders of various classical
  groups over finite fields, using the information collected in [BHR13].[133X
  
  [1X5.4-1 SizeSp[101X
  
  [33X[1;0Y[29X[2XSizeSp[102X( [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of  the group [10XSp[110X( [3Xn[103X , [3Xq[103X ), according to [BHR13, Theorem
            1.6.22].[133X
  
  [1X5.4-2 SizePSp[101X
  
  [33X[1;0Y[29X[2XSizePSp[102X( [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of  the  group [10XPSp[110X( [3Xn[103X , [3Xq[103X ), according to [BHR13, Table
            1.3].[133X
  
  [1X5.4-3 SizeSU[101X
  
  [33X[1;0Y[29X[2XSizeSU[102X( [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of  the group [10XSU[110X( [3Xn[103X , [3Xq[103X ), according to [BHR13, Theorem
            1.6.22].[133X
  
  [1X5.4-4 SizePSU[101X
  
  [33X[1;0Y[29X[2XSizePSU[102X( [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of  the  group [10XPSU[110X( [3Xn[103X , [3Xq[103X ), according to [BHR13, Table
            1.3].[133X
  
  [1X5.4-5 SizeGU[101X
  
  [33X[1;0Y[29X[2XSizeGU[102X( [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of  the  group  [10XGU[110X( [3Xn[103X , [3Xq[103X ), according to [BHR13, Table
            1.3].[133X
  
  [1X5.4-6 SizeGO[101X
  
  [33X[1;0Y[29X[2XSizeGO[102X( [3Xepsilon[103X, [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of the group [10XGO[110X( [3Xepsilon[103X, [3Xn[103X , [3Xq[103X ), according to [BHR13,
            Theorem 1.6.22].[133X
  
  [1X5.4-7 SizeSO[101X
  
  [33X[1;0Y[29X[2XSizeSO[102X( [3Xepsilon[103X, [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of the group [10XSO[110X( [3Xepsilon[103X, [3Xn[103X , [3Xq[103X ), according to [BHR13,
            Table 1.3].[133X
  
  [1X5.4-8 SizeOmega[101X
  
  [33X[1;0Y[29X[2XSizeOmega[102X( [3Xepsilon[103X, [3Xn[103X, [3Xq[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ythe  size  of  the  group  [10XOmega[110X(  [3Xepsilon[103X,  [3Xn[103X , [3Xq[103X ), according to
            [BHR13, Table 1.3].[133X
  
