LinearFRMachines and LinearFRElements
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: Q\otimes X\to X\otimes Q\) is a linear map; furthermore, there is a functional \(\pi:Q\to\Bbbk\) called the output.
As before, a choice of initial state \(q\in Q\) induces a linear map \(q:T(X)\to 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_1\otimes\dots\otimes x_n\in T(X)\), rewrite \(q\otimes x\) as a sum of expressions of the form \(y\otimes r\) with \(y\in T(X)\) and \(r\in 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.
LinearFRMachines and LinearFRElements‣ VectorMachine( domain, transitions, output ) | ( operation ) |
‣ VectorElement( domain, transitions, output, init ) | ( operation ) |
‣ VectorMachineNC( fam, transitions, output ) | ( operation ) |
‣ VectorElementNC( fam, transitions, output, init, category ) | ( 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\to b\).
The optional last argument category specifies a category (IsAssociativeElement (Reference: IsAssociativeElement), IsJacobianElement (Reference: IsJacobianElement),...) to which the new element should belong.
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.
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
‣ AssociativeObject( x ) | ( operation ) |
Returns: An associative object related to x.
If x belongs to a family that admits a non-associative and an associative product, and the product of x is non-associative, this function returns the object corresponding to x, but with associative product.
A typical example is that x is a derivation of a vector space. The product of derivations is \(a\circ b-b\circ a\), and is not associative; but derivations are endomorphisms of the vector space, and as such can be composed associatively.
gap> A := VectorElement(Rationals,[[[[0]],[[1]]],[[[1]],[[0]]]],[1],[1],IsJacobianElement); <Linear element on alphabet Rationals^2 with 1-dimensional stateset-> gap> A^2; <Zero linear element on alphabet Rationals^2-> gap> AssociativeObject(A)^2; <Identity linear element on alphabet Rationals^2>
‣ 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.
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 ] ]
‣ 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\to b\).
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 ]
‣ 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.
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 ] ]
‣ 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, e=NestedMatrixState(e,[],[]), and
Activity(e,1)[i][j]=NestedMatrixCoefficient(e,[i],[j]), and
DecompositionOfFRElement(e,1)[i][j]=NestedMatrixState(e,[i],[j]).
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
‣ ActivitySparse( m, i ) | ( operation ) |
Returns: A sparse matrix.
Activity(m,i) returns an \(n^i\times 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.
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 ] ]
‣ Activities( m, i ) | ( operation ) |
Returns: Activities of m on the first i levels.
Activity(m,i) returns an \(n^i\times 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)).
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 ] ] ]
‣ 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.
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 ] ]
‣ 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.
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
‣ 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-10) 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 9.4.
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
‣ 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-9)).
This function returns fail if it believes that it does not have enough information to make a reasonable guess.
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
‣ 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-14) and AsAlgebraMachine (6.1-15).
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
‣ 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-13).
‣ 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-13).
‣ 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.
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
‣ 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.
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
generated by GAPDoc2HTML