Path algebra elements#

AUTHORS:

Simon King (2015-08)

class sage.quivers.algebra_elements.PathAlgebraElement#

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

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)]

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

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

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)#

Return the coefficient of a monomial.

INPUT:

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

coefficients()#

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]

degree()#

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

is_homogeneous()#

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

monomial_coefficients()#

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)]

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

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

monomials()#

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

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

support_of_term()#

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

terms()#

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]

sage.quivers.algebra_elements.path_algebra_element_unpickle(P, data)#

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