Path algebra elements¶
AUTHORS:
 Simon King (201508)

class
sage.quivers.algebra_elements.
PathAlgebraElement
¶ Bases:
sage.structure.element.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*yz+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*yz+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 32bit operating system; using 64bit on the same machine, the letterplace implementation has not become faster, but the timing for path algebra elements has improved by about 20%:
sage: timeit('pF^5+3*pF^3') # not tested 1 loops, best of 3: 338 ms per loop sage: timeit('pP^5+3*pP^3') # not tested 100 loops, best of 3: 2.55 ms per loop sage: timeit('pF2^7') # not tested 10000 loops, best of 3: 513 ms per loop sage: timeit('pL2^7') # not tested 125 loops, best of 3: 1.99 ms per loop sage: timeit('pP2^7') # not tested 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
()¶ Returns 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
()¶ Returns 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
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

sort_by_vertices
()¶ Return a list of triples
(element, v1, v2)
, whereelement
is an element whose monomials all have initial vertexv1
and terminal vertexv2
, so that the sum of elements isself
.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

support
()¶ Returns 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
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
()¶ Returns 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