Path algebra elements

AUTHORS:

  • Simon King (2015-08)

class sage.quivers.algebra_elements.PathAlgebraElement[source]

Bases: RingElement

Elements of a PathAlgebra.

Note

Upon creation of a path algebra, one can choose among several monomial orders, which are all positive or negative degree orders. Monomial orders that are not degree orders are not supported.

EXAMPLES:

After creating a path algebra and getting hold of its generators, one can create elements just as usual:

sage: A = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup().algebra(ZZ)
sage: A.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: x = a+2*b+3*c+5*e_0+3*e_2
sage: x
5*e_0 + a + 2*b + 3*c + 3*e_2

>>> from sage.all import *
>>> A = DiGraph({Integer(0):{Integer(1):['a'], Integer(2):['b']}, Integer(1):{Integer(0):['c'], Integer(1):['d']}, Integer(2):{Integer(0):['e'],Integer(2):['f']}}).path_semigroup().algebra(ZZ)
>>> A.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
>>> x = a+Integer(2)*b+Integer(3)*c+Integer(5)*e_0+Integer(3)*e_2
>>> x
5*e_0 + a + 2*b + 3*c + 3*e_2

The path algebra decomposes as a direct sum according to start- and endpoints:

sage: x.sort_by_vertices()
[(5*e_0, 0, 0),
 (a, 0, 1),
 (2*b, 0, 2),
 (3*c, 1, 0),
 (3*e_2, 2, 2)]
sage: (x^3+x^2).sort_by_vertices()
[(150*e_0 + 33*a*c, 0, 0),
 (30*a + 3*a*c*a, 0, 1),
 (114*b + 6*a*c*b, 0, 2),
 (90*c + 9*c*a*c, 1, 0),
 (18*c*a, 1, 1),
 (54*c*b, 1, 2),
 (36*e_2, 2, 2)]

>>> from sage.all import *
>>> x.sort_by_vertices()
[(5*e_0, 0, 0),
 (a, 0, 1),
 (2*b, 0, 2),
 (3*c, 1, 0),
 (3*e_2, 2, 2)]
>>> (x**Integer(3)+x**Integer(2)).sort_by_vertices()
[(150*e_0 + 33*a*c, 0, 0),
 (30*a + 3*a*c*a, 0, 1),
 (114*b + 6*a*c*b, 0, 2),
 (90*c + 9*c*a*c, 1, 0),
 (18*c*a, 1, 1),
 (54*c*b, 1, 2),
 (36*e_2, 2, 2)]

For a consistency test, we create a path algebra that is isomorphic to a free associative algebra, and compare arithmetic with two other implementations of free algebras (note that the letterplace implementation only allows weighted homogeneous elements):

sage: F.<x,y,z> = FreeAlgebra(GF(25,'t'))
sage: pF = x+y*z*x+2*y-z+1
sage: pF2 = x^4+x*y*x*z+2*z^2*x*y
sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: pP = sage_eval('x+y*z*x+2*y-z+1', P.gens_dict())
sage: pP^5+3*pP^3 == sage_eval(repr(pF^5+3*pF^3), P.gens_dict())
True
sage: L.<x,y,z> = FreeAlgebra(GF(25,'t'), implementation='letterplace')
sage: pL2 = x^4+x*y*x*z+2*z^2*x*y
sage: pP2 = sage_eval('x^4+x*y*x*z+2*z^2*x*y', P.gens_dict())
sage: pP2^7 == sage_eval(repr(pF2^7), P.gens_dict())
True
sage: pP2^7 == sage_eval(repr(pL2^7), P.gens_dict())
True

>>> from sage.all import *
>>> F = FreeAlgebra(GF(Integer(25),'t'), names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> pF = x+y*z*x+Integer(2)*y-z+Integer(1)
>>> pF2 = x**Integer(4)+x*y*x*z+Integer(2)*z**Integer(2)*x*y
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'))
>>> pP = sage_eval('x+y*z*x+2*y-z+1', P.gens_dict())
>>> pP**Integer(5)+Integer(3)*pP**Integer(3) == sage_eval(repr(pF**Integer(5)+Integer(3)*pF**Integer(3)), P.gens_dict())
True
>>> L = FreeAlgebra(GF(Integer(25),'t'), implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = L._first_ngens(3)
>>> pL2 = x**Integer(4)+x*y*x*z+Integer(2)*z**Integer(2)*x*y
>>> pP2 = sage_eval('x^4+x*y*x*z+2*z^2*x*y', P.gens_dict())
>>> pP2**Integer(7) == sage_eval(repr(pF2**Integer(7)), P.gens_dict())
True
>>> pP2**Integer(7) == sage_eval(repr(pL2**Integer(7)), P.gens_dict())
True

When the Cython implementation of path algebra elements was introduced, it was faster than both the default implementation and the letterplace implementation of free algebras. The following timings where obtained with a 32-bit operating system; using 64-bit on the same machine, the letterplace implementation has not become faster, but the timing for path algebra elements has improved by about 20%:

sage: # not tested
sage: timeit('pF^5+3*pF^3')
1 loops, best of 3: 338 ms per loop
sage: timeit('pP^5+3*pP^3')
100 loops, best of 3: 2.55 ms per loop
sage: timeit('pF2^7')
10000 loops, best of 3: 513 ms per loop
sage: timeit('pL2^7')
125 loops, best of 3: 1.99 ms per loop
sage: timeit('pP2^7')
10000 loops, best of 3: 1.54 ms per loop

>>> from sage.all import *
>>> # not tested
>>> timeit('pF^5+3*pF^3')
1 loops, best of 3: 338 ms per loop
>>> timeit('pP^5+3*pP^3')
100 loops, best of 3: 2.55 ms per loop
>>> timeit('pF2^7')
10000 loops, best of 3: 513 ms per loop
>>> timeit('pL2^7')
125 loops, best of 3: 1.99 ms per loop
>>> timeit('pP2^7')
10000 loops, best of 3: 1.54 ms per loop

So, if one is merely interested in basic arithmetic operations for free associative algebras, it could make sense to model the free associative algebra as a path algebra. However, standard basis computations are not available for path algebras, yet. Hence, to implement computations in graded quotients of free algebras, the letterplace implementation currently is the only option.

coefficient(P)[source]

Return the coefficient of a monomial.

INPUT:

  • P – an element of the underlying partial semigroup

OUTPUT:

The coefficient of the given semigroup element in self, or zero if it does not appear.

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order='degrevlex')
sage: P.inject_variables()
Defining e_1, x, y, z
sage: p = (x+2*z+1)^3
sage: p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
sage: p.coefficient(sage_eval('x*x*z', P.semigroup().gens_dict()))
2
sage: p.coefficient(sage_eval('z*x*x*x', P.semigroup().gens_dict()))
0

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order='degrevlex')
>>> P.inject_variables()
Defining e_1, x, y, z
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
>>> p.coefficient(sage_eval('x*x*z', P.semigroup().gens_dict()))
2
>>> p.coefficient(sage_eval('z*x*x*x', P.semigroup().gens_dict()))
0
coefficients()[source]

Return the list of coefficients.

Note

The order in which the coefficients are returned corresponds to the order in which the terms are printed. That is not the same as the order given by the monomial order, since the terms are first ordered according to initial and terminal vertices, before applying the monomial order of the path algebra.

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order='degrevlex')
sage: P.inject_variables()
Defining e_1, x, y, z
sage: p = (x+2*z+1)^3
sage: p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
sage: p.coefficients()
[3, 4, 4, 2, 4, 2, 2, 1, 2, 1, 1, 3, 1, 3, 1]

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order='degrevlex')
>>> P.inject_variables()
Defining e_1, x, y, z
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
>>> p.coefficients()
[3, 4, 4, 2, 4, 2, 2, 1, 2, 1, 1, 3, 1, 3, 1]
degree()[source]

Return the degree, provided the element is homogeneous.

An error is raised if the element is not homogeneous.

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: P.inject_variables()
Defining e_1, x, y, z
sage: q = (x+y+2*z)^3
sage: q.degree()
3
sage: p = (x+2*z+1)^3
sage: p.degree()
Traceback (most recent call last):
...
ValueError: element is not homogeneous

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'))
>>> P.inject_variables()
Defining e_1, x, y, z
>>> q = (x+y+Integer(2)*z)**Integer(3)
>>> q.degree()
3
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> p.degree()
Traceback (most recent call last):
...
ValueError: element is not homogeneous
is_homogeneous()[source]

Tells whether this element is homogeneous.

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: P.inject_variables()
Defining e_1, x, y, z
sage: q = (x+y+2*z)^3
sage: q.is_homogeneous()
True
sage: p = (x+2*z+1)^3
sage: p.is_homogeneous()
False

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'))
>>> P.inject_variables()
Defining e_1, x, y, z
>>> q = (x+y+Integer(2)*z)**Integer(3)
>>> q.is_homogeneous()
True
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> p.is_homogeneous()
False
monomial_coefficients()[source]

Return the dictionary keyed by the monomials appearing in this element, the values being the coefficients.

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order='degrevlex')
sage: P.inject_variables()
Defining e_1, x, y, z
sage: p = (x+2*z+1)^3
sage: sorted(p.monomial_coefficients().items())
[(x*x*x, 1),
 (z*x*x, 2),
 (x*z*x, 2),
 (z*z*x, 4),
 (x*x*z, 2),
 (z*x*z, 4),
 (x*z*z, 4),
 (z*z*z, 3),
 (x*x, 3),
 (z*x, 1),
 (x*z, 1),
 (z*z, 2),
 (x, 3),
 (z, 1),
 (e_1, 1)]

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order='degrevlex')
>>> P.inject_variables()
Defining e_1, x, y, z
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> sorted(p.monomial_coefficients().items())
[(x*x*x, 1),
 (z*x*x, 2),
 (x*z*x, 2),
 (z*z*x, 4),
 (x*x*z, 2),
 (z*x*z, 4),
 (x*z*z, 4),
 (z*z*z, 3),
 (x*x, 3),
 (z*x, 1),
 (x*z, 1),
 (z*z, 2),
 (x, 3),
 (z, 1),
 (e_1, 1)]

Note that the dictionary can be fed to the algebra, to reconstruct the element:

sage: P(p.monomial_coefficients()) == p
True

>>> from sage.all import *
>>> P(p.monomial_coefficients()) == p
True
monomials()[source]

Return the list of monomials appearing in this element.

Note

The order in which the monomials are returned corresponds to the order in which the element’s terms are printed. That is not the same as the order given by the monomial order, since the terms are first ordered according to initial and terminal vertices, before applying the monomial order of the path algebra.

The monomials are not elements of the underlying partial semigroup, but of the algebra.

See also

support()

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order='degrevlex')
sage: P.inject_variables()
Defining e_1, x, y, z
sage: p = (x+2*z+1)^3
sage: p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
sage: p.monomials()
[z*z*z,
 x*z*z,
 z*x*z,
 x*x*z,
 z*z*x,
 x*z*x,
 z*x*x,
 x*x*x,
 z*z,
 x*z,
 z*x,
 x*x,
 z,
 x,
 e_1]
sage: p.monomials()[1].parent() is P
True

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order='degrevlex')
>>> P.inject_variables()
Defining e_1, x, y, z
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
>>> p.monomials()
[z*z*z,
 x*z*z,
 z*x*z,
 x*x*z,
 z*z*x,
 x*z*x,
 z*x*x,
 x*x*x,
 z*z,
 x*z,
 z*x,
 x*x,
 z,
 x,
 e_1]
>>> p.monomials()[Integer(1)].parent() is P
True
sort_by_vertices()[source]

Return a list of triples (element, v1, v2), where element is an element whose monomials all have initial vertex v1 and terminal vertex v2, so that the sum of elements is self.

EXAMPLES:

sage: A1 = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup().algebra(ZZ.quo(15))
sage: A1.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: x = (b*e*b*e+4*b+e_0)^2
sage: y = (a*c*b+1)^3
sage: x.sort_by_vertices()
[(e_0 + 2*b*e*b*e + b*e*b*e*b*e*b*e, 0, 0), (4*b + 4*b*e*b*e*b, 0, 2)]
sage: sum(c[0] for c in x.sort_by_vertices()) == x
True
sage: y.sort_by_vertices()
[(e_0, 0, 0), (3*a*c*b, 0, 2), (e_1, 1, 1), (e_2, 2, 2)]
sage: sum(c[0] for c in y.sort_by_vertices()) == y
True

>>> from sage.all import *
>>> A1 = DiGraph({Integer(0):{Integer(1):['a'], Integer(2):['b']}, Integer(1):{Integer(0):['c'], Integer(1):['d']}, Integer(2):{Integer(0):['e'],Integer(2):['f']}}).path_semigroup().algebra(ZZ.quo(Integer(15)))
>>> A1.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
>>> x = (b*e*b*e+Integer(4)*b+e_0)**Integer(2)
>>> y = (a*c*b+Integer(1))**Integer(3)
>>> x.sort_by_vertices()
[(e_0 + 2*b*e*b*e + b*e*b*e*b*e*b*e, 0, 0), (4*b + 4*b*e*b*e*b, 0, 2)]
>>> sum(c[Integer(0)] for c in x.sort_by_vertices()) == x
True
>>> y.sort_by_vertices()
[(e_0, 0, 0), (3*a*c*b, 0, 2), (e_1, 1, 1), (e_2, 2, 2)]
>>> sum(c[Integer(0)] for c in y.sort_by_vertices()) == y
True
support()[source]

Return the list of monomials, as elements of the underlying partial semigroup.

Note

The order in which the monomials are returned corresponds to the order in which the element’s terms are printed. That is not the same as the order given by the monomial order, since the terms are first ordered according to initial and terminal vertices, before applying the monomial order of the path algebra.

See also

monomials()

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order='degrevlex')
sage: P.inject_variables()
Defining e_1, x, y, z
sage: p = (x+2*z+1)^3
sage: p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
sage: p.support()
[z*z*z,
 x*z*z,
 z*x*z,
 x*x*z,
 z*z*x,
 x*z*x,
 z*x*x,
 x*x*x,
 z*z,
 x*z,
 z*x,
 x*x,
 z,
 x,
 e_1]
sage: p.support()[1].parent() is P.semigroup()
True

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order='degrevlex')
>>> P.inject_variables()
Defining e_1, x, y, z
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
>>> p.support()
[z*z*z,
 x*z*z,
 z*x*z,
 x*x*z,
 z*z*x,
 x*z*x,
 z*x*x,
 x*x*x,
 z*z,
 x*z,
 z*x,
 x*x,
 z,
 x,
 e_1]
>>> p.support()[Integer(1)].parent() is P.semigroup()
True
support_of_term()[source]

If self consists of a single term, return the corresponding element of the underlying path semigroup.

EXAMPLES:

sage: A = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup().algebra(ZZ)
sage: A.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: x = 4*a*d*c*b*e
sage: x.support_of_term()
a*d*c*b*e
sage: x.support_of_term().parent() is A.semigroup()
True
sage: (x + f).support_of_term()
Traceback (most recent call last):
...
ValueError: 4*a*d*c*b*e + f is not a single term

>>> from sage.all import *
>>> A = DiGraph({Integer(0):{Integer(1):['a'], Integer(2):['b']}, Integer(1):{Integer(0):['c'], Integer(1):['d']}, Integer(2):{Integer(0):['e'],Integer(2):['f']}}).path_semigroup().algebra(ZZ)
>>> A.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
>>> x = Integer(4)*a*d*c*b*e
>>> x.support_of_term()
a*d*c*b*e
>>> x.support_of_term().parent() is A.semigroup()
True
>>> (x + f).support_of_term()
Traceback (most recent call last):
...
ValueError: 4*a*d*c*b*e + f is not a single term
terms()[source]

Return the list of terms.

Note

The order in which the terms are returned corresponds to the order in which they are printed. That is not the same as the order given by the monomial order, since the terms are first ordered according to initial and terminal vertices, before applying the monomial order of the path algebra.

EXAMPLES:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order='degrevlex')
sage: P.inject_variables()
Defining e_1, x, y, z
sage: p = (x+2*z+1)^3
sage: p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
sage: p.terms()
[3*z*z*z,
 4*x*z*z,
 4*z*x*z,
 2*x*x*z,
 4*z*z*x,
 2*x*z*x,
 2*z*x*x,
 x*x*x,
 2*z*z,
 x*z,
 z*x,
 3*x*x,
 z,
 3*x,
 e_1]

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order='degrevlex')
>>> P.inject_variables()
Defining e_1, x, y, z
>>> p = (x+Integer(2)*z+Integer(1))**Integer(3)
>>> p
3*z*z*z + 4*x*z*z + 4*z*x*z + 2*x*x*z + 4*z*z*x + 2*x*z*x + 2*z*x*x + x*x*x + 2*z*z + x*z + z*x + 3*x*x + z + 3*x + e_1
>>> p.terms()
[3*z*z*z,
 4*x*z*z,
 4*z*x*z,
 2*x*x*z,
 4*z*z*x,
 2*x*z*x,
 2*z*x*x,
 x*x*x,
 2*z*z,
 x*z,
 z*x,
 3*x*x,
 z,
 3*x,
 e_1]
sage.quivers.algebra_elements.path_algebra_element_unpickle(P, data)[source]

Auxiliary function for unpickling.

EXAMPLES:

sage: A = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup().algebra(ZZ.quo(15), order='negdeglex')
sage: A.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: X = a+2*b+3*c+5*e_0+3*e_2
sage: loads(dumps(X)) == X    # indirect doctest
True

>>> from sage.all import *
>>> A = DiGraph({Integer(0):{Integer(1):['a'], Integer(2):['b']}, Integer(1):{Integer(0):['c'], Integer(1):['d']}, Integer(2):{Integer(0):['e'],Integer(2):['f']}}).path_semigroup().algebra(ZZ.quo(Integer(15)), order='negdeglex')
>>> A.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
>>> X = a+Integer(2)*b+Integer(3)*c+Integer(5)*e_0+Integer(3)*e_2
>>> loads(dumps(X)) == X    # indirect doctest
True