On Mon, Sep 19, 2011 at 12:23:06PM +0200, Jeroen Demeyer wrote:
> I only found sage/categories/finite_dimensional_algebras_with_basis.py
> which is just a category with essentially no code.
I noticed you found #11111 in the mean time. Help on finalizing this
patch is most welcome :-)
> Have finite-dimensional algebras (over QQ, say) been implemented in
> Sage? I mean an implementation where you can give any
> multiplication table and compute with the algebra.
This should only take a few lines to implement. That being said, it is
an often requested feature, so it would be worthwhile to have a nice
and easy front end like:
sage: A = AlgebraFromStructureCoefficients(QQ, [1,2,3], ...
multiplication_table)
Basically, the only thing to do is to decide on the exact format for
inputing the multiplication table.
You may want to look at #11111, e.g. by installing the sage-combinat
queue:
> sage -combinat install
The example of finite dimensional algebra with basis does just this,
with an hard coded multiplication table:
sage: C = AlgebrasWithBasis(QQ).FiniteDimensional().example()
sage: C??
> Or to give such an algebra as a sub-algebra of a matrix algebra
> (first computing the sub-algebra generated by given matrices...).
> I am considering to give "implement [1] in Sage" as a master thesis
> project (there exists a Magma implementation). This would require such
> functionality (or such functionality would be part of the project).
+1!
Having a fast implementation of this feature has been on our
dream/todo list ever since we switched from MuPAD.
So far we have been using GAP:
sage: C = AlgebrasWithBasis(QQ).FiniteDimensional().example()
sage: M = MatrixSpace(QQ,2)
sage: s = M([[0,1],[1,0]])
sage: pi = M([[0,1],[0,1]])
sage: A = gap.Subalgebra(gap.MatrixAlgebra(QQ,2), [s,pi]); A
Algebra( Rationals, [ [ [ 0, 1 ], [ 1, 0 ] ], [ [ 0, 1 ], [ 0, 1 ] ] ] )
sage: A.Dimension()
3
I have attached a quick implementation which calls GAP to compute the
algebra closure, and then allows for computing with elements within
Sage (joint with Nicolas Borie; no sage-combinat patch needed). We
basically wanted to see how the category infrastructure for
subquotients would deal with that. Feel free to ask further questions
/ recycle / ...
As William said, a native Sage implementation would be useful in order
to work with any coefficient ring, but also any ambient algebra.
Besides, the underlying tools required to get this specific feature
would be of general use.
Here is a suggestion of implementation plan:
- Low level kernel: implement efficient "mutable" subspaces. That is
we want the usual subspaces:
sage: V = QQ^20
sage: v1 = ...
sage: v2 = ...
sage: S = V.subspace([v1,v2])
with the ability to progressively enlarge *in place* the subspace
by throwing in new vectors:
sage: S.add(v3)
True
(the return value tells whether v3 was actually added or whether it
already belonged to that subspace)
Nicolas B. (in CC) has been using the usual subspaces of FreeModule
for this, and ran into memory issues. This essentially because the
addition of each single vector required the creation of a new
subspace (he could reproduce the exact issue if asked for). At the
end, he implemented his own progressive Gauss elimination ...
Besides, one would want this feature to be available for all vector
spaces in Sage: FreeModule, MatrixSpace, CombinatorialFreeModule,
but also all polynomial rings and such.
- Implement generically (in ModulesWithBasis) a method:
sage: S = V.module_closure([v1,...], operators)
which returns the smallest subspace S of V containing the vectors
[v1,...], and closed upon the action of the linear operators in
``operators``.
- Use it to implement (in AlgebrasWithBasis) a method:
sage: V.algebra_closure([v1,...])
by using the `x -> x*v1` as linear operators.
- Make sure that all sage vector spaces and algebras are in the
appropriate categories!
We had module_closure and algebra_closure in MuPAD. For examples of
use, you may want to browse through the Sage demo at the end of [1]
(don't worry about the maths there; all you need to know to get a
feeling of what's going on is that a Kac algebra is an algebra with
some extra operations).
Cheers,
Nicolas
[1] http://fr.arxiv.org/abs/0812.3044v3
PS: Nicolas is finishing his PhD dissertation right now; he might be
slow answering!
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
#
#
# Matrix Algebra....
#
#
import copy
from sage.misc.cachefunc import cached_method
from sage.combinat.free_module import CombinatorialFreeModule
from sage.categories.finite_dimensional_algebras_with_basis import FiniteDimensionalAlgebrasWithBasis
from sage.interfaces.gap import gap
from sage.sets.integer_range import IntegerRange
from sage.rings.integer_ring import ZZ
class MatrixSubalgebra(CombinatorialFreeModule):
r"""
A Data structure class for algebra of matrices defined by generator
EXAMPLES::
sage: M = MatrixSpace(QQ,2)
sage: s = M([[0,1],[1,0]])
sage: pi = M([[0,1],[0,1]])
sage: A = MatrixSubalgebra((s,pi))
sage: A.dimension()
3
sage: x = A.an_element()
sage: x
B[1] + 2*B[2] + 4*B[3]
sage: x^2
6*B[1] + 12*B[2] + 19*B[3]
sage: TestSuite(A).run()
"""
@staticmethod
def __classcall__(cls, gens):
gens = tuple(copy.copy(m) for m in gens)
for g in gens:
g.set_immutable()
return super(MatrixSubalgebra, cls).__classcall__(cls, gens)
def __init__(self, gens):
r"""
``gens`` : a list of squares matrices of the same size and base ring
"""
self._gens = gens
first = gens[0]
dim = first.ncols()
base_ring = first.parent().base_ring()
self._ambient = gap.Subalgebra(gap.MatrixAlgebra(base_ring, dim), gens)
CombinatorialFreeModule.__init__(self, base_ring, IntegerRange(ZZ(1), ZZ(self._ambient.Dimension()+1)),
category=FiniteDimensionalAlgebrasWithBasis(base_ring).IsomorphicObjects())
def _repr_(self):
r"""
"""
return "Algebra of Matrices generated by %s"%(self._gens,)
# def dimension(self):
# r"""
# """
# return ZZ(self.ambient().Dimension())
def ambient(self):
r"""
"""
return self._ambient
@cached_method
def lift_on_basis(self, i):
assert i in self.basis().keys()
return self.ambient().Basis()[i]
# Except for the .Zero(), this could be handled by the ModulesWithBasis().SubQuotients() category
def lift(self, x):
r"""
return the element representing ``x`` in the Gap version of ``self``.
"""
assert x in self
basis = self.ambient().Basis()
if x.is_zero():
return self.ambient().Zero()
else:
return gap.Sum([c*basis[i] for i,c in x])
def retract(self, M):
r"""
"""
coord = gap.Coefficients(self.ambient().Basis(), M)
return self.sum_of_terms( (i, coord[i].sage()) for i in self.basis().keys() )
# Except for the .One(), this could be handled by the Monoids().SubQuotients() category
def one(self):
r"""
"""
return self.retract(self.ambient().One())
# This should ideally be provided by the AlgebrasWithBasis().SubQuotients() category
@cached_method
def product_on_basis(self, i, j):
return self.retract(self.lift_on_basis(i) * self.lift_on_basis(j))
