6 Linear machines and elements
  
  Linear  machines are a special class of FR machines, in which the stateset Q
  and  the  alphabet X are vector spaces over a field Bbbk, and the transition
  map  phi:  Qotimes  X->  Xotimes  Q is a linear map; furthermore, there is a
  functional pi:Q->Bbbk called the output.
  
  As  before,  a  choice  of initial state qin Q induces a linear map q:T(X)->
  T(X),  where  T(X)=bigoplus X^otimes n is the tensor algebra generated by X.
  This  map  is  defined  as  follows: given x=x_1otimesdotsotimes x_nin T(X),
  rewrite  qotimes  x  as  a sum of expressions of the form yotimes r with yin
  T(X) and rin Q; then q, by definition, maps x to the sum of the pi(r)y.
  
  There are two sorts of linear machines: vector machines, for which the state
  space  is  a  finite-dimensional  vector  space  over  a  field; and algebra
  machines,  for  which  the  state space is a free algebra in a finite set of
  variables.
  
  In  a  vector machine, the transition and output maps are stored as a matrix
  and  a  vector respectively. Minimization algorithms are implemented, as for
  Mealy machines.
  
  In an algebra machine, the transition and output maps are stored as words in
  the algebra. These machines are natural extensions of group/monoid/semigroup
  machines.
  
  Linear elements are given by a linear machine and an initial state. They can
  be  added  and  multiplied,  and  act on the tensor algebra of the alphabet,
  admitting natural representations as matrices.
  
  
  6.1 Methods and operations for LinearFRMachines and LinearFRElements
  
  6.1-1 VectorMachine
  
  > VectorMachine( domain, transitions, output ) ____________________operation
  > VectorElement( domain, transitions, output, init ) ______________operation
  > VectorMachineNC( fam, transitions, output ) _____________________operation
  > VectorElementNC( fam, transitions, output, init ) _______________operation
  Returns:  A new vector machine/element.
  
  This function constructs a new linear machine or element, of vector type.
  
  transitions is a matrix of matrices; for a,b indices of basis vectors of the
  alphabet,  transitions[a][b]  is  a  square  matrix indexed by the stateset,
  which  is  the transition to be effected on the stateset upon the output a->
  b.
  
  output and init are vectors in the stateset.
  
  In  the  "NC"  version,  no  tests are performed to check that the arguments
  contain  values  within bounds, or even of the right type (beyond the simple
  checking performed by GAP's method selection algorithms). The first argument
  should  be the family of the resulting object. These "NC" methods are mainly
  used internally by the package.
  
  ---------------------------  Example  ----------------------------
    gap> M := VectorMachine(Rationals,[[[[1]],[[2]]],[[[3]],[[4]]]],[1]);
    <Linear machine on alphabet Rationals^2 with 1-dimensional stateset>
    gap> Display(M);
     Rationals | 1 | 2 |
    -----------+---+---+
             1 | 1 | 2 |
    -----------+---+---+
             2 | 3 | 4 |
    -----------+---+---+
    Output: 1
    gap> A := VectorElement(Rationals,[[[[1]],[[2]]],[[[3]],[[4]]]],[1],[1]);
    <Linear element on alphabet Rationals^2 with 1-dimensional stateset>
    gap> Display(Activity(A,2));
    [ [   1,   2,   2,   4 ],
      [   3,   4,   6,   8 ],
      [   3,   6,   4,   8 ],
      [   9,  12,  12,  16 ] ]
    gap> DecompositionOfFRElement(A);
    [ [ <Linear element on alphabet Rationals^2 with 1-dimensional stateset>,
          <Linear element on alphabet Rationals^2 with 1-dimensional stateset> ],
      [ <Linear element on alphabet Rationals^2 with 1-dimensional stateset>,
          <Linear element on alphabet Rationals^2 with 1-dimensional stateset> ] ]
    gap> last=[[A,2*A],[3*A,4*A]];
    true
  ------------------------------------------------------------------
  
  6.1-2 AlgebraMachine
  
  > AlgebraMachine( [domain, ]ring, transitions, output ) ___________operation
  > AlgebraElement( [domain, ]ring, transitions, output, init ) _____operation
  > AlgebraMachineNC( fam, ring, transitions, output ) ______________operation
  > AlgebraElementNC( fam, ring, transitions, output, init ) ________operation
  Returns:  A new algebra machine/element.
  
  This function constructs a new linear machine or element, of algebra type.
  
  ring  is  a  free  associative  algebra,  optionally with one. domain is the
  vector  space  on  which  the  alphabet is defined. If absent, this argument
  defaults to the LeftActingDomain (Reference: LeftActingDomain) of ring.
  
  transitions  is a list of matrices; for each generator number i of ring, the
  matrix  transitions[i], with entries in ring, describes the decomposition of
  generator i as a matrix.
  
  output is a vector over domain, and init is a vector over ring.
  
  In  the  "NC"  version,  no  tests are performed to check that the arguments
  contain  values  within bounds, or even of the right type (beyond the simple
  checking performed by GAP's method selection algorithms). The first argument
  should  be the family of the resulting object. These "NC" methods are mainly
  used internally by the package.
  
  ---------------------------  Example  ----------------------------
    gap> F := FreeAssociativeAlgebraWithOne(Rationals,1);;
    gap> A := AlgebraMachine(F,[[[F.1,F.1^2+F.1],[One(F),Zero(F)]]],[1]);
    <Linear machine on alphabet Rationals^2 with generators [ (1)*x.1 ]>
    gap> Display(A);
     Rationals |     1     |     2     |
    -----------+-----------+-----------+
             1 |       x.1 | x.1+x.1^2 |
    -----------+-----------+-----------+
             2 |         1 |         0 |
    -----------+-----------+-----------+
    Output: 1
    gap> M := AlgebraElement(F,[[[F.1,F.1^2+F.1],[One(F),Zero(F)]]],[1],F.1);
    <Rationals^2|(1)*x.1>
    gap> Display(Activity(M,2));
    [ [  1,  2,  4,  4 ],
      [  1,  0,  2,  2 ],
      [  1,  0,  0,  0 ],
      [  0,  1,  0,  0 ] ]
  ------------------------------------------------------------------
  
  6.1-3 Transition
  
  > Transition( m, s, a, b ) ________________________________________operation
  Returns:  An element of m's stateset.
  
  This  function  returns  the  state reached by m when started in state s and
  performing output a-> b.
  
  ---------------------------  Example  ----------------------------
    gap> M := AsVectorMachine(Rationals,FRMachine(GuptaSidkiGroup.2));
    <Linear machine on alphabet Rationals^3 with 4-dimensional stateset>
    gap> Transition(M,[1,0,0,0],[1,0,0],[1,0,0]);
    [ 0, 1, 0, 0 ]
    gap> Transition(M,[1,0,0,0],[0,1,0],[0,1,0]);
    [ 0, 0, 1, 0 ]
    gap> Transition(M,[1,0,0,0],[0,0,1],[0,0,1]);
    [ 1, 0, 0, 0 ]
    gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);
    <Linear element on alphabet Rationals^3 with 4-dimensional stateset>
    gap> Transition(A,[1,0,0],[1,0,0]);
    [ 0, 1, 0, 0 ]
  ------------------------------------------------------------------
  
  6.1-4 Transitions
  
  > Transitions( m, s, a ) __________________________________________operation
  Returns:  An vector of elements of m's stateset.
  
  This  function  returns  the  state reached by m when started in state s and
  receiving  input a. The output is a vector, indexed by the alphabet's basis,
  of output states.
  
  ---------------------------  Example  ----------------------------
    gap> M := AsVectorMachine(Rationals,FRMachine(GuptaSidkiGroup.2));
    <Linear machine on alphabet Rationals^3 with 4-dimensional stateset>
    gap> Transitions(M,[1,0,0,0],[1,0,0]);
    [ [ 0, 1, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ] ]
    gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);
    <Linear element on alphabet Rationals^3 with 4-dimensional stateset>
    gap> Transitions(A,[1,0,0]);
    [ [ 0, 1, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ] ]
  ------------------------------------------------------------------
  
  6.1-5 NestedMatrixState
  
  > NestedMatrixState( e, i, j ) ____________________________________operation
  > NestedMatrixCoefficient( e, i, j ) ______________________________operation
  Returns:  A coefficent of an iterated decomposition of e.
  
  The  first  form  returns  the entry at position (i,j) of e's decomposition.
  Both of i,j are lists. The second form returns the output of the state.
  
  In           particular,          NestedMatrixState(e,[],[])=e,          and
  Activity(e,1)[i][j]=NestedMatrixCoefficient(e,[i],[j]),                  and
  DecompositionOfFRElement(e,1)[i][j]=NestedMatrixState(e,[i],[j]).
  
  ---------------------------  Example  ----------------------------
    gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);;
    gap> A=NestedMatrixState(A,[3,3],[3,3]);
    true
    gap> IsOne(NestedMatrixState(A,[3,3,3,3,1,1],[3,3,3,3,1,2]));
    true
    gap> List([1..3],i->List([1..3],j->NestedMatrixCoefficient(A,[i],[j])))=Activity(A,1);
    true
  ------------------------------------------------------------------
  
  6.1-6 ActivitySparse
  
  > ActivitySparse( m, i ) __________________________________________operation
  Returns:  A sparse matrix.
  
  Activity(m,i) returns an n^ix n^i matrix describing the action on the i-fold
  tensor  power  of the alphabet. This matrix can also be returned as a sparse
  matrix,  and this is performed by this command. A sparse matrix is described
  as  a list of expressions of the form [[i,j],c], representing the elementary
  matrix  with  entry c at position (i,j). The activity matrix is then the sum
  of these elementary matrices.
  
  ---------------------------  Example  ----------------------------
    gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);;
    gap> Display(Activity(A,2));
    [ [  0,  1,  0,  0,  0,  0,  0,  0,  0 ],
      [  0,  0,  1,  0,  0,  0,  0,  0,  0 ],
      [  1,  0,  0,  0,  0,  0,  0,  0,  0 ],
      [  0,  0,  0,  0,  0,  1,  0,  0,  0 ],
      [  0,  0,  0,  1,  0,  0,  0,  0,  0 ],
      [  0,  0,  0,  0,  1,  0,  0,  0,  0 ],
      [  0,  0,  0,  0,  0,  0,  1,  0,  0 ],
      [  0,  0,  0,  0,  0,  0,  0,  1,  0 ],
      [  0,  0,  0,  0,  0,  0,  0,  0,  1 ] ]
    gap> ActivitySparse(A,2);
    [ [ [ 1, 2 ], 1 ], [ [ 2, 3 ], 1 ], [ [ 3, 1 ], 1 ], [ [ 4, 6 ], 1 ],
    [ [ 5, 4 ], 1 ], [ [ 6, 5 ], 1 ], [ [ 7, 7 ], 1 ], [ [ 8, 8 ], 1 ],
    [ [ 9, 9 ], 1 ] ]
  ------------------------------------------------------------------
  
  6.1-7 Activities
  
  > Activities( m, i ) ______________________________________________operation
  Returns:  Activities of m on the first i levels.
  
  Activity(m,i) returns an n^ix n^i matrix describing the action on the i-fold
  tensor     power     of     the     alphabet.     This    command    returns
  List([0..i-1],j->Activity(m,j)).
  
  ---------------------------  Example  ----------------------------
    gap> A := AsVectorElement(Rationals,GrigorchukGroup.2);;
    gap> Activities(A,3);
    [ [ [ 1 ] ],
      [ [ 1, 0 ], [ 0, 1 ] ],
      [ [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ] ]
  ------------------------------------------------------------------
  
  6.1-8 IsConvergent
  
  > IsConvergent( e ) ________________________________________________property
  Returns:  Whether the linear element e is convergent.
  
  A  linear  element  is convergent if its state at position (1,1) is equal to
  itself.
  
  ---------------------------  Example  ----------------------------
    gap> n := 3;;
    gap> shift := VectorElement(CyclotomicField(n), [[[[1,0],[0,0]],
         [[0,0],[0,1]]],[[[0,1],[0,0]],[[1,0],[0,0]]]],[1,E(n)],[1,0]);
    <Linear element on alphabet CF(3)^2 with 2-dimensional stateset>
    gap> IsConvergent(shift);
    true
    gap> Display(Activity(shift,2));
    [ [     1,     0,     0,     0 ],
      [  E(3),     1,     0,     0 ],
      [     0,  E(3),     1,     0 ],
      [     0,     0,  E(3),     1 ] ]
    gap> Display(Activity(shift,3));
    [ [     1,     0,     0,     0,     0,     0,     0,     0 ],
      [  E(3),     1,     0,     0,     0,     0,     0,     0 ],
      [     0,  E(3),     1,     0,     0,     0,     0,     0 ],
      [     0,     0,  E(3),     1,     0,     0,     0,     0 ],
      [     0,     0,     0,  E(3),     1,     0,     0,     0 ],
      [     0,     0,     0,     0,  E(3),     1,     0,     0 ],
      [     0,     0,     0,     0,     0,  E(3),     1,     0 ],
      [     0,     0,     0,     0,     0,     0,  E(3),     1 ] ]
  ------------------------------------------------------------------
  
  6.1-9 TransposedFRElement
  
  > TransposedFRElement( e ) ________________________________________operation
  > IsSymmetricFRElement( e ) ________________________________________property
  > IsAntisymmetricFRElement( e ) ____________________________________property
  > IsLowerTriangularFRElement( e ) __________________________________property
  > IsUpperTriangularFRElement( e ) __________________________________property
  > IsDiagonalFRElement( e ) _________________________________________property
  Returns:  The elementary matrix operation/property.
  
  Since  linear  FR elements may be interpreted as infinite matrices, it makes
  sense  to  transpose  them,  test  whether they're symmetric, antisymmetric,
  diagonal, or triangular.
  
  ---------------------------  Example  ----------------------------
    gap> n := 3;;
    gap> shift := VectorElement(CyclotomicField(n), [[[[1,0],[0,0]],
         [[0,0],[0,1]]],[[[0,1],[0,0]],[[1,0],[0,0]]]],[1,E(n)],[1,0]);
    <Linear element on alphabet CF(3)^2 with 2-dimensional stateset>
    gap> Display(Activity(shift,2));
    [ [     1,     0,     0,     0 ],
      [  E(3),     1,     0,     0 ],
      [     0,  E(3),     1,     0 ],
      [     0,     0,  E(3),     1 ] ]
    gap> Display(Activity(TransposedFRElement(shift),2));
    [ [     1,  E(3),     0,     0 ],
      [     0,     1,  E(3),     0 ],
      [     0,     0,     1,  E(3) ],
      [     0,     0,     0,     1 ] ]
    gap> IsSymmetricFRElement(shift);
    false
    gap> IsSymmetricFRElement(shift+TransposedFRElement(shift));
    true
    gap> IsLowerTriangularFRElement(shift);
    true
    gap> IsUpperTriangularFRElement(shift);
    false
  ------------------------------------------------------------------
  
  6.1-10 LDUDecompositionFRElement
  
  > LDUDecompositionFRElement( e ) __________________________________operation
  Returns:  A factorization e=LDU.
  
  Given  a  linear element e, this command attempts to find a decomposition of
  the  form  e=LDU, where L is lower triangular, D is diagonal, and U is upper
  triangular (see IsLowerTriangularFRElement (6.1-9) etc.).
  
  The  result  is returned thas a list with entries L,D,U. Note that it is not
  guaranteed to succeed. For more examples, see Section 10.4.
  
  ---------------------------  Example  ----------------------------
    gap> List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));;
    gap> A := GuessVectorElement(last);
    <Linear element on alphabet GaussianRationals^2 with 2-dimensional stateset>
    gap> LDU := LDUDecompositionFRElement(A);
    [ <Linear element on alphabet GaussianRationals^2 with 4-dimensional stateset>,
      <Linear element on alphabet GaussianRationals^2 with 3-dimensional stateset>,
      <Linear element on alphabet GaussianRationals^2 with 4-dimensional stateset> ]
    gap> IsLowerTriangularFRElement(LDU[1]); IsDiagonalFRElement(LDU[2]);
    true
    true
    gap> TransposedFRElement(LDU[1])=LDU[3];
    true
    gap> Product(LDU)=A;
    true
  ------------------------------------------------------------------
  
  6.1-11 GuessVectorElement
  
  > GuessVectorElement( m ) __________________________________________function
  Returns:  A vector element that acts like m.
  
  The  arguments to this function include a matrix or list of matrices, and an
  optional ring. The return value is a vector element, over the ring if it was
  specified, that acts like the sequence of matrices.
  
  If  a  single  matrix  is  specified,  then  it  is  assumed  to represent a
  convergent element (see IsConvergent (6.1-8)).
  
  This  function  returns  fail  if  it  believes that it does not have enough
  information to make a reasonable guess.
  
  ---------------------------  Example  ----------------------------
    gap> n := 3;;
    gap> shift := VectorElement(CyclotomicField(n), [[[[1,0],[0,0]],
         [[0,0],[0,1]]],[[[0,1],[0,0]],,[[1,0],[0,0]]]],[1,E(n)],[1,0]);;
    <Linear element on alphabet CF(3)^2 with 2-dimensional stateset>
    gap> GuessVectorElement(Activity(shift,3)); last=shift;
    <Linear element on alphabet CF(3)^2 with 2-dimensional stateset>
    true
    gap> GuessVectorElement(Inverse(Activity(shift,4)));
    fail
    gap> GuessVectorElement(Inverse(Activity(shift,5)));
    <Linear element on alphabet CF(3)^2 with 4-dimensional stateset>
    gap> IsOne(last*shift);
    true
  ------------------------------------------------------------------
  
  6.1-12 AsLinearMachine
  
  > AsLinearMachine( r, m ) _________________________________________operation
  > AsLinearElement( r, m ) _________________________________________operation
  Returns:  The linear machine/element associated with m.
  
  This   command  accepts  a  domain  and  an  ordinary  machine/element,  and
  constructs  the  corresponding  linear machine/element, defined by extending
  linearly the action on [1..d] to an action on r^d.
  
  If  m is a Mealy machine/element, the result is a vector machine/element. If
  m  is  a  group/monoid/semigroup  machine/element,  the result is an algebra
  machine/element.  To  obtain explicitly a vector or algebra machine/element,
  see AsVectorMachine (6.1-13) and AsAlgebraMachine (6.1-14).
  
  ---------------------------  Example  ----------------------------
    gap> Display(I4Machine);
       |  1     2
    ---+-----+-----+
     a | c,2   c,1
     b | a,1   b,1
     c | c,1   c,2
    ---+-----+-----+
    gap> A := AsLinearMachine(Rationals,I4Machine);
    <Linear machine on alphabet Rationals^2 with 3-dimensional stateset>
    Correspondence(A);
    [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ]
    gap> Display(A);
     Rationals |   1   |   2   |
    -----------+-------+-------+
             1 | 0 0 0 | 0 0 1 |
               | 1 0 0 | 0 0 0 |
               | 0 0 1 | 0 0 0 |
    -----------+-------+-------+
             2 | 0 0 1 | 0 0 0 |
               | 0 1 0 | 0 0 0 |
               | 0 0 0 | 0 0 1 |
    -----------+-------+-------+
    Output: 1 1 1
    gap> B := AsLinearMachine(Rationals,AsMonoidFRMachine(I4Machine));
    <Linear machine on alphabet Rationals^2 with generators [ (1)*m1, (1)*m2 ]>
    gap> Correspondence(B);
    MappingByFunction( <free monoid on the generators [ m1, m2 ]>,
    <algebra-with-one over Rationals, with 2 generators>, function( w ) ... end )
    gap> Display(B);
     Rationals | 1  | 2  |
    -----------+----+----+
             1 |  0 |  1 |
               | m1 |  0 |
    -----------+----+----+
             2 |  1 |  0 |
               | m2 |  0 |
    -----------+----+----+
    Output: 1 1
    gap> AsLinearElement(Rationals,I4Monoid.1)*AsLinearElement(Rationals,I4Monoid.2);
    <Linear element on alphabet Rationals^2 with 4-dimensional stateset>
    gap> last=AsLinearElement(Rationals,I4Monoid.1*I4Monoid.2);
    true  
  ------------------------------------------------------------------
  
  6.1-13 AsVectorMachine
  
  > AsVectorMachine( r, m ) _________________________________________operation
  > AsVectorElement( r, m ) _________________________________________operation
  Returns:  The vector machine/element associated with m.
  
  This   command  accepts  a  domain  and  an  ordinary  machine/element,  and
  constructs  the  corresponding  linear machine/element, defined by extending
  linearly  the  action  on  [1..d]  to  an action on r^d. For this command to
  succeed,  the  machine/element  m  must  be  finite  state. For examples see
  AsLinearMachine (6.1-12).
  
  6.1-14 AsAlgebraMachine
  
  > AsAlgebraMachine( r, m ) ________________________________________operation
  > AsAlgebraElement( r, m ) ________________________________________operation
  Returns:  The algebra machine/element associated with m.
  
  This   command  accepts  a  domain  and  an  ordinary  machine/element,  and
  constructs  the  corresponding  linear machine/element, defined by extending
  linearly  the  action  on  [1..d]  to  an  action  on  r^d. For examples see
  AsLinearMachine (6.1-12).
  
  6.1-15 AsVectorMachine
  
  > AsVectorMachine( m ) ____________________________________________operation
  > AsVectorElement( m ) ____________________________________________operation
  Returns:  The machine/element m in vector form.
  
  This  command accepts a linear machine, and converts it to vector form. This
  command is not guaranteed to terminate.
  
  ---------------------------  Example  ----------------------------
    gap> A := AsLinearElement(Rationals,I4Monoid.1);
    <Linear element on alphabet Rationals^2 with 2-dimensional stateset>
    gap> B := AsAlgebraElement(A);
    <Rationals^2|(1)*x.1>
    gap> C := AsVectorElement(B);
    gap> A=B; B=C;
    true
    true
  ------------------------------------------------------------------
  
  6.1-16 AsAlgebraMachine
  
  > AsAlgebraMachine( m ) ___________________________________________operation
  > AsAlgebraElement( m ) ___________________________________________operation
  Returns:  The machine/element m in algebra form.
  
  This command accepts a linear machine, and converts it to algebra form.
  
  ---------------------------  Example  ----------------------------
    gap> A := AsLinearElement(Rationals,I4Monoid.1);
    <Linear element on alphabet Rationals^2 with 2-dimensional stateset>
    gap> AsAlgebraElement(A)=AsAlgebraElement(Rationals,I4Monoid.1);
    true
    gap> A=AsAlgebraElement(A);
    true
  ------------------------------------------------------------------