Path Algebras#

class sage.quivers.algebra.PathAlgebra(k, P, order='negdegrevlex')[source]#

Bases: CombinatorialFreeModule

Create the path algebra of a quiver over a given field.

Given a quiver \(Q\) and a field \(k\), the path algebra \(kQ\) is defined as follows. As a vector space it has basis the set of all paths in \(Q\). Multiplication is defined on this basis and extended bilinearly. If \(p\) is a path with terminal vertex \(t\) and \(q\) is a path with initial vertex \(i\) then the product \(p*q\) is defined to be the composition of the paths \(p\) and \(q\) if \(t = i\) and \(0\) otherwise.

INPUT:

  • k – field (or commutative ring), the base field of the path algebra

  • P – the path semigroup of a quiver \(Q\)

  • order – optional string, one of “negdegrevlex” (default), “degrevlex”, “negdeglex” or “deglex”, defining the monomial order to be used.

OUTPUT:

  • the path algebra \(kP\) with the given monomial order

Note

Monomial orders that are not degree orders are not supported.

EXAMPLES:

sage: P = DiGraph({1:{2:['a']}, 2:{3:['b']}}).path_semigroup()
sage: A = P.algebra(GF(7))
sage: A
Path algebra of Multi-digraph on 3 vertices over Finite Field of size 7
sage: A.variable_names()
('e_1', 'e_2', 'e_3', 'a', 'b')

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b']}}).path_semigroup()
>>> A = P.algebra(GF(Integer(7)))
>>> A
Path algebra of Multi-digraph on 3 vertices over Finite Field of size 7
>>> A.variable_names()
('e_1', 'e_2', 'e_3', 'a', 'b')

Note that path algebras are uniquely defined by their quiver, field and monomial order:

sage: A is P.algebra(GF(7))
True
sage: A is P.algebra(GF(7), order="degrevlex")
False
sage: A is P.algebra(RR)
False
sage: A is DiGraph({1:{2:['a']}}).path_semigroup().algebra(GF(7))
False

>>> from sage.all import *
>>> A is P.algebra(GF(Integer(7)))
True
>>> A is P.algebra(GF(Integer(7)), order="degrevlex")
False
>>> A is P.algebra(RR)
False
>>> A is DiGraph({Integer(1):{Integer(2):['a']}}).path_semigroup().algebra(GF(Integer(7)))
False

The path algebra of an acyclic quiver has a finite basis:

sage: A.dimension()
6
sage: list(A.basis())
[e_1, e_2, e_3, a, b, a*b]

>>> from sage.all import *
>>> A.dimension()
6
>>> list(A.basis())
[e_1, e_2, e_3, a, b, a*b]

The path algebra can create elements from paths or from elements of the base ring:

sage: A(5)
5*e_1 + 5*e_2 + 5*e_3
sage: S = A.semigroup()
sage: S
Partial semigroup formed by the directed paths of Multi-digraph on 3 vertices
sage: p = S([(1, 2, 'a')])
sage: r = S([(2, 3, 'b')])
sage: e2 = S([(2, 2)])
sage: x = A(p) + A(e2)
sage: x
a + e_2
sage: y = A(p) + A(r)
sage: y
a + b

>>> from sage.all import *
>>> A(Integer(5))
5*e_1 + 5*e_2 + 5*e_3
>>> S = A.semigroup()
>>> S
Partial semigroup formed by the directed paths of Multi-digraph on 3 vertices
>>> p = S([(Integer(1), Integer(2), 'a')])
>>> r = S([(Integer(2), Integer(3), 'b')])
>>> e2 = S([(Integer(2), Integer(2))])
>>> x = A(p) + A(e2)
>>> x
a + e_2
>>> y = A(p) + A(r)
>>> y
a + b

Path algebras are graded algebras. The grading is given by assigning to each basis element the length of the path corresponding to that basis element:

sage: x.is_homogeneous()
False
sage: x.degree()
Traceback (most recent call last):
...
ValueError: element is not homogeneous
sage: y.is_homogeneous()
True
sage: y.degree()
1
sage: A[1]
Free module spanned by [a, b] over Finite Field of size 7
sage: A[2]
Free module spanned by [a*b] over Finite Field of size 7

>>> from sage.all import *
>>> x.is_homogeneous()
False
>>> x.degree()
Traceback (most recent call last):
...
ValueError: element is not homogeneous
>>> y.is_homogeneous()
True
>>> y.degree()
1
>>> A[Integer(1)]
Free module spanned by [a, b] over Finite Field of size 7
>>> A[Integer(2)]
Free module spanned by [a*b] over Finite Field of size 7
Element[source]#

alias of PathAlgebraElement

arrows()[source]#

Return the arrows of this algebra (corresponding to edges of the underlying quiver).

EXAMPLES:

sage: P = DiGraph({1:{2:['a']}, 2:{3:['b', 'c']}, 4:{}}).path_semigroup()
sage: A = P.algebra(GF(5))
sage: A.arrows()
(a, b, c)

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b', 'c']}, Integer(4):{}}).path_semigroup()
>>> A = P.algebra(GF(Integer(5)))
>>> A.arrows()
(a, b, c)
degree_on_basis(x)[source]#

Return x.degree().

This function is here to make some methods work that are inherited from CombinatorialFreeModule.

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 = a+2*b+3*c*e-a*d+5*e_0+3*e_2
sage: X
5*e_0 + a - a*d + 2*b + 3*e_2
sage: X.homogeneous_component(0)   # indirect doctest
5*e_0 + 3*e_2
sage: X.homogeneous_component(1)
a + 2*b
sage: X.homogeneous_component(2)
-a*d
sage: X.homogeneous_component(3)
0

>>> 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*e-a*d+Integer(5)*e_0+Integer(3)*e_2
>>> X
5*e_0 + a - a*d + 2*b + 3*e_2
>>> X.homogeneous_component(Integer(0))   # indirect doctest
5*e_0 + 3*e_2
>>> X.homogeneous_component(Integer(1))
a + 2*b
>>> X.homogeneous_component(Integer(2))
-a*d
>>> X.homogeneous_component(Integer(3))
0
gen(i)[source]#

Return the \(i\)-th generator of this algebra.

This is an idempotent (corresponding to a trivial path at a vertex) if \(i < n\) (where \(n\) is the number of vertices of the quiver), and a single-edge path otherwise.

EXAMPLES:

sage: P = DiGraph({1:{2:['a']}, 2:{3:['b', 'c']}, 4:{}}).path_semigroup()
sage: A = P.algebra(GF(5))
sage: A.gens()
(e_1, e_2, e_3, e_4, a, b, c)
sage: A.gen(2)
e_3
sage: A.gen(5)
b

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b', 'c']}, Integer(4):{}}).path_semigroup()
>>> A = P.algebra(GF(Integer(5)))
>>> A.gens()
(e_1, e_2, e_3, e_4, a, b, c)
>>> A.gen(Integer(2))
e_3
>>> A.gen(Integer(5))
b
gens()[source]#

Return the generators of this algebra (idempotents and arrows).

EXAMPLES:

sage: P = DiGraph({1:{2:['a']}, 2:{3:['b', 'c']}, 4:{}}).path_semigroup()
sage: A = P.algebra(GF(5))
sage: A.variable_names()
('e_1', 'e_2', 'e_3', 'e_4', 'a', 'b', 'c')
sage: A.gens()
(e_1, e_2, e_3, e_4, a, b, c)

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b', 'c']}, Integer(4):{}}).path_semigroup()
>>> A = P.algebra(GF(Integer(5)))
>>> A.variable_names()
('e_1', 'e_2', 'e_3', 'e_4', 'a', 'b', 'c')
>>> A.gens()
(e_1, e_2, e_3, e_4, a, b, c)
homogeneous_component(n)[source]#

Return the \(n\)-th homogeneous piece of the path algebra.

INPUT:

  • n – integer

OUTPUT:

EXAMPLES:

sage: P = DiGraph({1:{2:['a'], 3:['b']}, 2:{4:['c']}, 3:{4:['d']}}).path_semigroup()
sage: A = P.algebra(GF(7))
sage: A.homogeneous_component(2)
Free module spanned by [a*c, b*d] over Finite Field of size 7

sage: D = DiGraph({1: {2: 'a'}, 2: {3: 'b'}, 3: {1: 'c'}})
sage: P = D.path_semigroup()
sage: A = P.algebra(ZZ)
sage: A.homogeneous_component(3)
Free module spanned by [a*b*c, b*c*a, c*a*b] over Integer Ring

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a'], Integer(3):['b']}, Integer(2):{Integer(4):['c']}, Integer(3):{Integer(4):['d']}}).path_semigroup()
>>> A = P.algebra(GF(Integer(7)))
>>> A.homogeneous_component(Integer(2))
Free module spanned by [a*c, b*d] over Finite Field of size 7

>>> D = DiGraph({Integer(1): {Integer(2): 'a'}, Integer(2): {Integer(3): 'b'}, Integer(3): {Integer(1): 'c'}})
>>> P = D.path_semigroup()
>>> A = P.algebra(ZZ)
>>> A.homogeneous_component(Integer(3))
Free module spanned by [a*b*c, b*c*a, c*a*b] over Integer Ring
homogeneous_components()[source]#

Return the non-zero homogeneous components of self.

EXAMPLES:

sage: Q = DiGraph([[1,2,'a'],[2,3,'b'],[3,4,'c']])
sage: PQ = Q.path_semigroup()
sage: A = PQ.algebra(GF(7))
sage: A.homogeneous_components()
[Free module spanned by [e_1, e_2, e_3, e_4] over Finite Field of size 7,
 Free module spanned by [a, b, c] over Finite Field of size 7,
 Free module spanned by [a*b, b*c] over Finite Field of size 7,
 Free module spanned by [a*b*c] over Finite Field of size 7]

>>> from sage.all import *
>>> Q = DiGraph([[Integer(1),Integer(2),'a'],[Integer(2),Integer(3),'b'],[Integer(3),Integer(4),'c']])
>>> PQ = Q.path_semigroup()
>>> A = PQ.algebra(GF(Integer(7)))
>>> A.homogeneous_components()
[Free module spanned by [e_1, e_2, e_3, e_4] over Finite Field of size 7,
 Free module spanned by [a, b, c] over Finite Field of size 7,
 Free module spanned by [a*b, b*c] over Finite Field of size 7,
 Free module spanned by [a*b*c] over Finite Field of size 7]

Warning

Backward incompatible change: since Issue #12630 and until Issue #8678, this feature was implemented under the syntax list(A) by means of A.__iter__. This was incorrect since A.__iter__, when defined for a parent, should iterate through the elements of \(A\).

idempotents()[source]#

Return the idempotents of this algebra (corresponding to vertices of the underlying quiver).

EXAMPLES:

sage: P = DiGraph({1:{2:['a']}, 2:{3:['b', 'c']}, 4:{}}).path_semigroup()
sage: A = P.algebra(GF(5))
sage: A.idempotents()
(e_1, e_2, e_3, e_4)

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b', 'c']}, Integer(4):{}}).path_semigroup()
>>> A = P.algebra(GF(Integer(5)))
>>> A.idempotents()
(e_1, e_2, e_3, e_4)
linear_combination(iter_of_elements_coeff, factor_on_left=True)[source]#

Return the linear combination \(\lambda_1 v_1 + \cdots + \lambda_k v_k\) (resp. the linear combination \(v_1 \lambda_1 + \cdots + v_k \lambda_k\)) where iter_of_elements_coeff iterates through the sequence \(((v_1, \lambda_1), ..., (v_k, \lambda_k))\).

INPUT:

  • iter_of_elements_coeff – iterator of pairs (element, coeff) with element in self and coeff in self.base_ring()

  • factor_on_left – (optional) if True, the coefficients are multiplied from the left if False, the coefficients are multiplied from the right

Note

It overrides a method inherited from CombinatorialFreeModule, which relies on a private attribute of elements—an implementation detail that is simply not available for PathAlgebraElement.

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: A.linear_combination([(a, 1), (b, 2), (c*e, 3),
....:                       (a*d, -1), (e_0, 5), (e_2, 3)])
5*e_0 + a - a*d + 2*b + 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
>>> A.linear_combination([(a, Integer(1)), (b, Integer(2)), (c*e, Integer(3)),
...                       (a*d, -Integer(1)), (e_0, Integer(5)), (e_2, Integer(3))])
5*e_0 + a - a*d + 2*b + 3*e_2
ngens()[source]#

Number of generators of this algebra.

EXAMPLES:

sage: P = DiGraph({1:{2:['a']}, 2:{3:['b', 'c']}, 4:{}}).path_semigroup()
sage: A = P.algebra(GF(5))
sage: A.ngens()
7

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b', 'c']}, Integer(4):{}}).path_semigroup()
>>> A = P.algebra(GF(Integer(5)))
>>> A.ngens()
7
one()[source]#

Return the multiplicative identity element.

The multiplicative identity of a path algebra is the sum of the basis elements corresponding to the trivial paths at each vertex.

EXAMPLES:

sage: A = DiGraph({1:{2:['a']}, 2:{3:['b']}}).path_semigroup().algebra(QQ)
sage: A.one()
e_1 + e_2 + e_3

>>> from sage.all import *
>>> A = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b']}}).path_semigroup().algebra(QQ)
>>> A.one()
e_1 + e_2 + e_3
order_string()[source]#

Return the string that defines the monomial order of this algebra.

EXAMPLES:

sage: P1 = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: P2 = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order="degrevlex")
sage: P3 = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order="negdeglex")
sage: P4 = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'), order="deglex")
sage: P1.order_string()
'negdegrevlex'
sage: P2.order_string()
'degrevlex'
sage: P3.order_string()
'negdeglex'
sage: P4.order_string()
'deglex'

>>> from sage.all import *
>>> P1 = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'))
>>> P2 = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order="degrevlex")
>>> P3 = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order="negdeglex")
>>> P4 = DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'), order="deglex")
>>> P1.order_string()
'negdegrevlex'
>>> P2.order_string()
'degrevlex'
>>> P3.order_string()
'negdeglex'
>>> P4.order_string()
'deglex'
quiver()[source]#

Return the quiver from which the algebra self was formed.

OUTPUT:

  • DiGraph, the quiver of the algebra

EXAMPLES:

sage: P = DiGraph({1:{2:['a', 'b']}}).path_semigroup()
sage: A = P.algebra(GF(3))
sage: A.quiver() is P.quiver()
True

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a', 'b']}}).path_semigroup()
>>> A = P.algebra(GF(Integer(3)))
>>> A.quiver() is P.quiver()
True
semigroup()[source]#

Return the (partial) semigroup from which the algebra self was constructed.

Note

The partial semigroup is formed by the paths of a quiver, multiplied by concatenation. If the quiver has more than a single vertex, then multiplication in the path semigroup is not always defined.

OUTPUT:

  • the path semigroup from which self was formed (a partial semigroup)

EXAMPLES:

sage: P = DiGraph({1:{2:['a', 'b']}}).path_semigroup()
sage: A = P.algebra(GF(3))
sage: A.semigroup() is P
True

>>> from sage.all import *
>>> P = DiGraph({Integer(1):{Integer(2):['a', 'b']}}).path_semigroup()
>>> A = P.algebra(GF(Integer(3)))
>>> A.semigroup() is P
True
sum(iter_of_elements)[source]#

Return the sum of all elements in iter_of_elements

INPUT:

  • iter_of_elements: iterator of elements of self

Note

It overrides a method inherited from CombinatorialFreeModule, which relies on a private attribute of elements—an implementation detail that is simply not available for PathAlgebraElement.

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: A.sum((a, 2*b, 3*c*e, -a*d, 5*e_0, 3*e_2))
5*e_0 + a - a*d + 2*b + 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
>>> A.sum((a, Integer(2)*b, Integer(3)*c*e, -a*d, Integer(5)*e_0, Integer(3)*e_2))
5*e_0 + a - a*d + 2*b + 3*e_2