Invariant modules#
- class sage.modules.with_basis.invariant.FiniteDimensionalInvariantModule(M, S, action=<built-in function mul>, side='left', *args, **kwargs)#
Bases:
SubmoduleWithBasis
The invariant submodule under a semigroup action.
When a semigroup \(S\) acts on a module \(M\), the invariant module is the set of elements \(m \in M\) such that \(s \cdot m = m\) for all \(s \in S\):
\[M^S := \{m \in M : s \cdot m = m,\, \forall s \in S \}.\]INPUT:
M
– a module in the category ofFiniteDimensionalModulesWithBasis
S
– a semigroup in the category ofFinitelyGeneratedSemigroups
action
– (default:operator.mul
) the action ofS
onM
side
– (default:'left'
) the side on whichS
acts
EXAMPLES:
First, we create the invariant defined by the cyclic group action on the free module with basis \(\{1,2,3\}\):
sage: G = CyclicPermutationGroup(3) sage: M = CombinatorialFreeModule(QQ, [1,2,3], prefix='M') sage: action = lambda g, m: M.monomial(g(m)) # cyclically permute coordinates
In order to give the module an action of
G
, we create aRepresentation
:sage: from sage.modules.with_basis.representation import Representation sage: R = Representation(G, M, action) sage: I = R.invariant_module()
Then we can lift the basis from the invariant to the original module:
sage: [I.lift(b) for b in I.basis()] [M[1] + M[2] + M[3]]
The we could also have the action be a right-action, instead of the default left-action:
sage: def rt_action(g, m): return M.monomial(g(m)) # cyclically permute coordinates sage: R = Representation(G, M, rt_action, side='right') # same as last but on right sage: g = G.an_element(); g (1,2,3) sage: r = R.an_element(); r 2*M[1] + 2*M[2] + 3*M[3] sage: R.side() 'right'
So now we can see that multiplication with
g
on the right sendsM[1]
toM[2]
and so on:sage: r * g 3*M[1] + 2*M[2] + 2*M[3] sage: I = R.invariant_module() sage: [I.lift(b) for b in I.basis()] [M[1] + M[2] + M[3]]
Now we will take the regular representation of the symmetric group on three elements to be the module, and compute its invariant submodule:
sage: G = SymmetricGroup(3) sage: R = G.regular_representation(QQ) sage: I = R.invariant_module() sage: [I.lift(b).to_vector() for b in I.basis()] [(1, 1, 1, 1, 1, 1)]
We can also check the scalar multiplication by elements of the base ring (for this example, the rational field):
sage: [I.lift(3*b).to_vector() for b in I.basis()] [(3, 3, 3, 3, 3, 3)]
A more subtle example is the invariant submodule of a skew-commutative module, for example the exterior algebra \(E[x_0,x_1,x_2]\) generated by three elements:
sage: G = CyclicPermutationGroup(3) sage: M = algebras.Exterior(QQ, 'x', 3) sage: def cyclic_ext_action(g, m): ....: # cyclically permute generators ....: return M.prod([M.monomial(FrozenBitset([g(j+1)-1])) for j in m])
If you care about being able to exploit the algebra structure of the exterior algebra (i.e. if you want to multiply elements together), you should make sure the representation knows it is also an algebra with the semigroup action being by algebra endomorphisms:
sage: cat = Algebras(QQ).WithBasis().FiniteDimensional() sage: R = Representation(G, M, cyclic_ext_action, category=cat) sage: I = R.invariant_module()
We can express the basis in the ambient algebra (\(E[x_0,x_1,x_2]\)):
sage: [I.lift(b) for b in I.basis()] [1, x0 + x1 + x2, x0*x1 - x0*x2 + x1*x2, x0*x1*x2]
or we can express the basis intrinsicallly to the invariant
I
:sage: B = I.basis() sage: m = 3*B[0] + 2*B[1] + 7*B[3]
This lifts to the exterior algebra:
sage: I.lift(m) 3 + 2*x0 + 7*x0*x1*x2 + 2*x1 + 2*x2
We can also check using the invariant element
m
that arithmetic works:sage: m^2 9*B[0] + 12*B[1] + 42*B[3] sage: m+m 6*B[0] + 4*B[1] + 14*B[3]
To see the actual elements expressed in the exterior algebra, we lift them again:
sage: I.lift(m+m) 6 + 4*x0 + 14*x0*x1*x2 + 4*x1 + 4*x2 sage: 7*m 21*B[0] + 14*B[1] + 49*B[3] sage: I.lift(7*m) 21 + 14*x0 + 49*x0*x1*x2 + 14*x1 + 14*x2
The classic example of an invariant module is the module of symmetric functions, which is the invariant module of polynomials whose variables are acted upon by permutation. We can create a module isomorphic to the homogeneous component of a a polynomial ring in \(n\) variable of a fixed degree \(d\) by looking at weak compositions of \(d\) of length \(n\), which we consider as the exponent vector. For example, \(x^2yz \in \QQ[x,y,z]\) would have the exponent vector \((2,1,1)\). The vector \((2,1,1)\) is a weak composition of \(4\), with length \(3\), and so we can think of it as being in the degree-\(4\) homogeneous component of a polynomial ring in three variables:
sage: C = IntegerVectors(4, length=3, min_part=0) # representing degree-4 monomials sage: M = CombinatorialFreeModule(QQ, C) # isomorphic to deg-4 homog. polynomials sage: G = SymmetricGroup(3) sage: def perm_action(g,x): return M.monomial(C(g(list(x)))) sage: perm_action(G((1,2,3)), C([4,3,2])) B[[3, 2, 4]] sage: R = Representation(G, M, perm_action) sage: I = R.invariant_module() sage: [I.lift(b) for b in I.basis()] [B[[0, 0, 4]] + B[[0, 4, 0]] + B[[4, 0, 0]], B[[0, 1, 3]] + B[[0, 3, 1]] + B[[1, 0, 3]] + B[[1, 3, 0]] + B[[3, 0, 1]] + B[[3, 1, 0]], B[[0, 2, 2]] + B[[2, 0, 2]] + B[[2, 2, 0]], B[[1, 1, 2]] + B[[1, 2, 1]] + B[[2, 1, 1]]]
These are the monomial symmetric functions, which are a well-known basis for the symmetric functions. For comparison:
sage: Sym = SymmetricFunctions(QQ) sage: m = Sym.monomial() sage: [m[mu].expand(3) for mu in Partitions(4)] [x0^4 + x1^4 + x2^4, x0^3*x1 + x0*x1^3 + x0^3*x2 + x1^3*x2 + x0*x2^3 + x1*x2^3, x0^2*x1^2 + x0^2*x2^2 + x1^2*x2^2, x0^2*x1*x2 + x0*x1^2*x2 + x0*x1*x2^2, 0]
Note
The current implementation works when \(S\) is a finitely-generated semigroup, and when \(M\) is a finite-dimensional free module with a distinguished basis.
Todo
Extend this to have multiple actions, including actions on both sides.
Todo
Extend when \(M\) does not have a basis and \(S\) is a permutation group using:
- class Element#
Bases:
IndexedFreeModuleElement
- construction()#
Return the functorial construction of
self
.EXAMPLES:
sage: G = CyclicPermutationGroup(3) sage: R = G.regular_representation(); R Left Regular Representation of Cyclic group of order 3 as a permutation group over Integer Ring sage: I = R.invariant_module() sage: I.construction() (EquivariantSubobjectConstructionFunctor, Left Regular Representation of Cyclic group of order 3 as a permutation group over Integer Ring)
- semigroup()#
Return the semigroup \(S\) whose action
self
is invariant under.EXAMPLES:
sage: G = SymmetricGroup(3) sage: M = CombinatorialFreeModule(QQ, [1,2,3], prefix='M') sage: def action(g,x): return M.monomial(g(x)) sage: I = M.invariant_module(G, action_on_basis=action) sage: I.semigroup() Symmetric group of order 3! as a permutation group
- semigroup_representation()#
Return the ambient space of
self
.EXAMPLES:
sage: X = CombinatorialFreeModule(QQ, range(3)); x = X.basis() sage: Y = X.submodule((x[0]-x[1], x[1]-x[2])) sage: Y.ambient() is X True
- class sage.modules.with_basis.invariant.FiniteDimensionalTwistedInvariantModule(M, G, chi, action=<built-in function mul>, side='left', **kwargs)#
Bases:
SubmoduleWithBasis
Construct the \(\chi\)-twisted invariant submodule of \(M\).
When a group \(G\) acts on a module \(M\), the \(\chi\)-twisted invariant submodule of \(M\) is the isotypic component of the representation \(M\) corresponding to the irreducible character \(\chi\).
For more information, see [Sta1979].
INPUT:
M
– a module in the category ofFiniteDimensionalModulesWithBasis
and whose base ring contains all the values passed tochi
and \(1/|G|\)G
– a finitely generated groupchi
– list/tuple of the character values of the irreducible representation onto which you want to project. The order of values of \(chi\) must agree with the order ofG.conjugacy_classes()
action
– (default:operator.mul
) the action ofG
onM
side
– (default:'left'
) the side on whichG
acts
Warning
The current implementation does not check if
chi
is irreducible. Passing character values of non-irreducible representations may lead to mathematically incorrect results.EXAMPLES:
Suppose that the symmetric group \(S_3\) acts on a four dimensional vector space by permuting the first three coordinates only:
sage: M = CombinatorialFreeModule(QQ, [1,2,3,4], prefix='M') sage: G = SymmetricGroup(3) sage: action = lambda g,x: M.term(g(x))
The trivial representation corresponds to the usual invariant module, so trying to create the twisted invariant module when there is no twist returns a
FiniteDimensionalInvariantModule
:sage: chi = ClassFunction(G, (1,1,1)) sage: T = M.twisted_invariant_module(G, chi, action_on_basis=action) sage: type(T) <class 'sage.modules.with_basis.invariant.FiniteDimensionalInvariantModule_with_category'>
In this case, there are two copies of the trivial representation, one coming from the first three coordinates and the other coming from the fact that \(S_3\) does not touch the fourth coordinate:
sage: T.basis() Finite family {0: B[0], 1: B[1]} sage: [T.lift(b) for b in T.basis()] [M[1] + M[2] + M[3], M[4]]
The character values of the standard representation are \(2,0,-1\):
sage: chi = ClassFunction(G, [2,0,-1]) sage: T = M.twisted_invariant_module(G, chi, action_on_basis=action) sage: type(T) <class 'sage.modules.with_basis.invariant.FiniteDimensionalTwistedInvariantModule_with_category'> sage: T.basis() Finite family {0: B[0], 1: B[1]} sage: [T.lift(b) for b in T.basis()] [M[1] - M[3], M[2] - M[3]]
The permutation representation is the direct sum of the standard representation with the trivial representation, and the action on the basis element
B[4]
is itself a copy of the trivial representation, so the sign representation does not appear in the decomposition:sage: T = M.twisted_invariant_module(G, [1,-1,1], action_on_basis=action) sage: T.basis() Finite family {}
We can also get two copies of the standard representation by looking at two copies of the permutation representation, found by reduction modulo three on the indices of a six-dimensional module:
sage: M = CombinatorialFreeModule(QQ, [0,1,2,3,4,5], prefix='M') sage: action = lambda g,x: M.term(g(x%3 + 1)-1 + (x>=3)*3) sage: T = M.twisted_invariant_module(G, [2,0,-1], action_on_basis=action) sage: T.basis() Finite family {0: B[0], 1: B[1], 2: B[2], 3: B[3]} sage: [T.lift(b) for b in T.basis()] [M[0] - M[2], M[1] - M[2], M[3] - M[5], M[4] - M[5]] sage: T = M.twisted_invariant_module(G, [1,1,1], action_on_basis=action) sage: T.basis() Finite family {0: B[0], 1: B[1]} sage: [T.lift(b) for b in T.basis()] [M[0] + M[1] + M[2], M[3] + M[4] + M[5]]
There are still no copies of the sign representation:
sage: T = M.twisted_invariant_module(G, [1,-1,1], action_on_basis=action) sage: T.basis() Finite family {}
The trivial representation also contains no copies of the sign representation:
sage: R = G.trivial_representation(QQ) sage: T = R.twisted_invariant_module([1,-1,1]) sage: T.basis() Finite family {}
The regular representation contains two copies of the standard representation and one copy each of the trivial and the sign:
sage: R = G.regular_representation(QQ) sage: std = R.twisted_invariant_module([2,0,-1]) sage: std.basis() Finite family {0: B[0], 1: B[1], 2: B[2], 3: B[3]} sage: [std.lift(b) for b in std.basis()] [() - (1,2,3), -(1,2,3) + (1,3,2), (2,3) - (1,2), -(1,2) + (1,3)] sage: triv = R.twisted_invariant_module([1,1,1]) sage: triv.basis() Finite family {0: B[0]} sage: [triv.lift(b) for b in triv.basis()] [() + (2,3) + (1,2) + (1,2,3) + (1,3,2) + (1,3)] sage: sgn = R.twisted_invariant_module([1,-1,1]) sage: sgn.basis() Finite family {0: B[0]} sage: [sgn.lift(b) for b in sgn.basis()] [() - (2,3) - (1,2) + (1,2,3) + (1,3,2) - (1,3)]
For the next example, we construct a twisted invariant by the character for the 2 dimensional representation of \(S_3\) on the natural action on the exterior algebra. While \(S_3\) acts by automorphisms, the twisted invariants do not form an algebra in this case:
sage: G = SymmetricGroup(3); G.rename('S3') sage: E = algebras.Exterior(QQ, 'x', 3); E.rename('E') sage: def action(g,m): return E.prod([E.monomial(FrozenBitset([g(j+1)-1])) for j in m]) sage: from sage.modules.with_basis.representation import Representation sage: EA = Representation(G, E, action, category=Algebras(QQ).WithBasis().FiniteDimensional()) sage: T = EA.twisted_invariant_module([2,0,-1]) sage: t = T.an_element(); t 2*B[0] + 2*B[1] + 3*B[2]
We can still get meaningful information about the product by taking the product in the ambient space:
sage: T.lift(t) * T.lift(t) -36*x0*x1*x2
We can see this does not lie in this twisted invariant algebra:
sage: T.retract(T.lift(t) * T.lift(t)) Traceback (most recent call last): ... ValueError: -36*x0*x1*x2 is not in the image sage: [T.lift(b) for b in T.basis()] [x0 - x2, x1 - x2, x0*x1 - x1*x2, x0*x2 + x1*x2]
It happens to be in the trivial isotypic component (equivalently in the usual invariant algebra) but Sage does not know this.
sage: G.rename(); E.rename() # reset the names
Todo
Replace
G
byS
inFinitelyGeneratedSemigroups
Allow for
chi
to be aRepresentation
Add check for irreducibility of
chi
- class Element#
Bases:
IndexedFreeModuleElement
- project(x)#
Project
x
in the ambient module ontoself
.EXAMPLES:
The standard representation is the orthogonal complement of the trivial representation inside of the permutation representation, so the basis for the trivial representation projects to \(0\):
sage: M = CombinatorialFreeModule(QQ, [1,2,3]); M.rename('M') sage: B = M.basis() sage: G = SymmetricGroup(3); G.rename('S3') sage: def action(g,x): return M.term(g(x)) sage: T = M.twisted_invariant_module(G, [2,0,-1], action_on_basis=action) sage: m = B[1] + B[2] + B[3] sage: parent(m) M sage: t = T.project(m); t 0 sage: parent(t) Twist of (S3)-invariant submodule of M by character [2, 0, -1] sage: G.rename(); M.rename() # reset names
- project_ambient(x)#
Project
x
in the ambient representation onto the submodule of the ambient representation to whichself
is isomorphic as a module.Note
The image of
self.project_ambient
is not inself
but rather is inself.ambient()
.EXAMPLES:
sage: M = CombinatorialFreeModule(QQ, [1,2,3]); M.rename('M') sage: B = M.basis() sage: G = SymmetricGroup(3); G.rename('S3') sage: def action(g,x): return M.term(g(x)) sage: T = M.twisted_invariant_module(G, [2,0,-1], action_on_basis=action)
To compare with
self.project
, we can inspect the parents. The image ofself.project
is inself
, while the image ofself.project_ambient
is inself._ambient
:sage: t = T.project(B[1] + B[2] + B[3]); t 0 sage: parent(t) Twist of (S3)-invariant submodule of M by character [2, 0, -1] sage: s = T.project_ambient(B[1] + B[2] + B[3]); s 0 sage: parent(s) Representation of S3 indexed by {1, 2, 3} over Rational Field
Note that because of the construction of
T
,self._ambient
is an instance ofRepresentation
, but you still may pass elements ofM
, which is an instance ofCombinatorialFreeModule
, because the underlyingRepresentation
is built off ofM
and we can cannonically construct elements of theRepresentation
from elements ofM
.sage: G.rename(); M.rename() # reset names
- projection_matrix()#
Return the matrix defining the projection map from the ambient representation onto
self
.EXAMPLES:
sage: M = CombinatorialFreeModule(QQ, [1,2,3]) sage: def action(g,x): return(M.term(g(x))) sage: G = SymmetricGroup(3)
If the matrix \(A\) has columns form a basis for the subspace onto which we are trying to project, then we can find the projection matrix via the formula \(P = A (A^T A)^{-1} A^T\). Recall that the standard representation twisted invariant has basis
(B[1] - B[3], B[2] - B[3])
, hence:sage: A = Matrix([[1,0],[0,1],[-1,-1]]) sage: P = A*(A.transpose()*A).inverse()*A.transpose() sage: T = M.twisted_invariant_module(G, [2,0,-1], action_on_basis=action) sage: P == T.projection_matrix() True
Moreover, since there is no component of the sign representation in this representation, the projection matrix is just the zero matrix:
sage: T = M.twisted_invariant_module(G, [1,-1,1], action_on_basis=action) sage: T.projection_matrix() [0 0 0] [0 0 0] [0 0 0]