# Path algebra elements#

AUTHORS:

• Simon King (2015-08)

class sage.quivers.algebra_elements.PathAlgebraElement#

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

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.

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().parent() is P
True
```
sort_by_vertices()#

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 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 for c in y.sort_by_vertices()) == y
True
```
support()#

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.

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().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
```