# Path Semigroups¶

class sage.quivers.path_semigroup.PathSemigroup(Q)

The partial semigroup that is given by the directed paths of a quiver, subject to concatenation.

See representation for a definition of this semigroup and of the notion of a path in a quiver.

Note that a partial semigroup here is defined as a set $$G$$ with a partial binary operation $$G \times G \to G \cup \{\mbox{None}\}$$, which is written infix as a $$*$$ sign and satisfies associativity in the following sense: If $$a$$, $$b$$ and $$c$$ are three elements of $$G$$, and if one of the products $$(a*b)*c$$ and $$a*(b*c)$$ exists, then so does the other and the two products are equal. A partial semigroup is not required to have a neutral element (and this one usually has no such element).

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}})
sage: S = Q.path_semigroup()
sage: S
Partial semigroup formed by the directed paths of Multi-digraph on 3 vertices
sage: S.variable_names()
('e_1', 'e_2', 'e_3', 'a', 'b', 'c', 'd')
sage: S.gens()
(e_1, e_2, e_3, a, b, c, d)
sage: S.category()
Category of finite enumerated semigroups


In the test suite, we skip the associativity test, as in this example the paths used for testing cannot be concatenated:

sage: TestSuite(S).run(skip=['_test_associativity'])


If there is only a single vertex, the partial semigroup is a monoid. If the underlying quiver has cycles or loops, then the (partial) semigroup only is an infinite enumerated set. This time, there is no need to skip tests:

sage: Q = DiGraph({1:{1:['a', 'b', 'c', 'd']}})
sage: M = Q.path_semigroup()
sage: M
Monoid formed by the directed paths of Looped multi-digraph on 1 vertex
sage: M.category()
Category of infinite enumerated monoids
sage: TestSuite(M).run()

Element
I(k, vertex)

Return the indecomposable injective module over $$k$$ at the given vertex vertex.

This module is literally indecomposable only when $$k$$ is a field.

INPUT:

• $$k$$ – ring, the base ring of the representation

• vertex – integer, a vertex of the quiver

OUTPUT:

• QuiverRep, the indecomposable injective module at vertex vertex with base ring $$k$$

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['c','d']}}).path_semigroup()
sage: I2 = Q.I(GF(3), 2)
sage: Q.I(ZZ, 3).dimension_vector()
(4, 2, 1)
sage: Q.I(ZZ, 1).dimension_vector()
(1, 0, 0)


The vertex given must be a vertex of the quiver:

sage: Q.I(QQ, 4)
Traceback (most recent call last):
...
ValueError: must specify a valid vertex of the quiver

P(k, vertex)

Return the indecomposable projective module over $$k$$ at the given vertex vertex.

This module is literally indecomposable only when $$k$$ is a field.

INPUT:

• $$k$$ – ring, the base ring of the representation

• vertex – integer, a vertex of the quiver

OUTPUT:

• QuiverRep, the indecomposable projective module at vertex with base ring $$k$$

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['c','d']}}).path_semigroup()
sage: P2 = Q.P(GF(3), 2)
sage: Q.P(ZZ, 3).dimension_vector()
(0, 0, 1)
sage: Q.P(ZZ, 1).dimension_vector()
(1, 2, 4)


The vertex given must be a vertex of the quiver:

sage: Q.P(QQ, 4)
Traceback (most recent call last):
...
ValueError: must specify a valid vertex of the quiver

S(k, vertex)

Return the simple module over $$k$$ at the given vertex vertex.

This module is literally simple only when $$k$$ is a field.

INPUT:

• $$k$$ – ring, the base ring of the representation

• vertex – integer, a vertex of the quiver

OUTPUT:

• QuiverRep, the simple module at vertex with base ring $$k$$

EXAMPLES:

sage: P = DiGraph({1:{2:['a','b']}, 2:{3:['c','d']}}).path_semigroup()
sage: S1 = P.S(GF(3), 1)
sage: P.S(ZZ, 3).dimension_vector()
(0, 0, 1)
sage: P.S(ZZ, 1).dimension_vector()
(1, 0, 0)


The vertex given must be a vertex of the quiver:

sage: P.S(QQ, 4)
Traceback (most recent call last):
...
ValueError: must specify a valid vertex of the quiver

algebra(k, order='negdegrevlex')

Return the path algebra of the underlying quiver.

INPUT:

• k – a commutative ring

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

Note

Monomial orders that are not degree orders are not supported.

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['d']}, 3:{1:['c']}})
sage: P = Q.path_semigroup()
sage: P.algebra(GF(3))
Path algebra of Multi-digraph on 3 vertices over Finite Field of size 3


Now some example with different monomial orderings:

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: sage_eval('(x+2*z+1)^3', P1.gens_dict())
e_1 + z + 3*x + 2*z*z + x*z + z*x + 3*x*x + 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
sage: sage_eval('(x+2*z+1)^3', P2.gens_dict())
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: sage_eval('(x+2*z+1)^3', P3.gens_dict())
e_1 + z + 3*x + 2*z*z + z*x + x*z + 3*x*x + 3*z*z*z + 4*z*z*x + 4*z*x*z + 2*z*x*x + 4*x*z*z + 2*x*z*x + 2*x*x*z + x*x*x
sage: sage_eval('(x+2*z+1)^3', P4.gens_dict())
3*z*z*z + 4*z*z*x + 4*z*x*z + 2*z*x*x + 4*x*z*z + 2*x*z*x + 2*x*x*z + x*x*x + 2*z*z + z*x + x*z + 3*x*x + z + 3*x + e_1

all_paths(start=None, end=None)

List of all paths between a pair of vertices (start, end).

INPUT:

• start – integer or None (default: None); the initial vertex of the paths in the output; if None is given then the initial vertex is arbitrary.

• end – integer or None (default: None); the terminal vertex of the paths in the output; if None is given then the terminal vertex is arbitrary

OUTPUT:

• list of paths, excluding the invalid path

Todo

This currently does not work for quivers with cycles, even if there are only finitely many paths from start to end.

Note

If there are multiple edges between two vertices, the method sage.graphs.digraph.all_paths() will not differentiate between them. But this method, which is not for digraphs but for their path semigroup associated with them, will.

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}})
sage: F = Q.path_semigroup()
sage: F.all_paths(1, 3)
[a*d, b*d, c]


If start=end then we expect only the trivial path at that vertex:

sage: F.all_paths(1, 1)
[e_1]


The empty list is returned if there are no paths between the given vertices:

sage: F.all_paths(3, 1)
[]


If end=None then all edge paths beginning at start are returned, including the trivial path:

sage: F.all_paths(2)
[e_2, d]


If start=None then all edge paths ending at end are returned, including the trivial path. Note that the two edges from vertex 1 to vertex 2 count as two different edge paths:

sage: F.all_paths(None, 2)
[a, b, e_2]
sage: F.all_paths(end=2)
[a, b, e_2]


If start=end=None then all edge paths are returned, including trivial paths:

sage: F.all_paths()
[e_1, a, b, a*d, b*d, c, e_2, d, e_3]


The vertex given must be a vertex of the quiver:

sage: F.all_paths(1, 4)
Traceback (most recent call last):
...
ValueError: the end vertex 4 is not a vertex of the quiver


If the underlying quiver is cyclic, a ValueError is raised:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}})
sage: F = Q.path_semigroup()
sage: F.all_paths()
Traceback (most recent call last):
...
ValueError: the underlying quiver has cycles, thus, there may be an infinity of directed paths

arrows()

Return the elements corresponding to edges of the underlying quiver.

EXAMPLES:

sage: P = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}}).path_semigroup()
sage: P.arrows()
(a, b, c, d)

cardinality()

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}})
sage: F = Q.path_semigroup()
sage: F.cardinality()
9
sage: A = F.algebra(QQ)
sage: list(A.basis())
[e_1, e_2, e_3, a, b, c, d, a*d, b*d]
sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}})
sage: F = Q.path_semigroup()
sage: F.cardinality()
+Infinity
sage: A = F.algebra(QQ)
sage: list(A.basis())
Traceback (most recent call last):
...
ValueError: the underlying quiver has cycles, thus, there may be an infinity of directed paths

free_module(k)

Return a free module of rank $$1$$ over kP, where $$P$$ is self. (In other words, the regular representation.)

INPUT:

• k – ring, the base ring of the representation.

OUTPUT:

EXAMPLES:

sage: Q = DiGraph({1:{2:['a', 'b'], 3: ['c', 'd']}, 2:{3:['e']}}).path_semigroup()
sage: Q.free_module(GF(3)).dimension_vector()
(1, 3, 6)

gen(i)

Return generator number $$i$$.

INPUT:

• i – integer

OUTPUT:

An idempotent, if $$i$$ is smaller than the number of vertices, or an arrow otherwise.

EXAMPLES:

sage: P = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}}).path_semigroup()
sage: P.1         # indirect doctest
e_2
sage: P.idempotents()
e_2
sage: P.5
c
sage: P.gens()
c

gens()

Return the tuple of generators.

Note

This coincides with the sum of the output of idempotents() and arrows().

EXAMPLES:

sage: P = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}}).path_semigroup()
sage: P.gens()
(e_1, e_2, e_3, a, b, c, d)
sage: P.gens() == P.idempotents() + P.arrows()
True

idempotents()

Return the idempotents corresponding to the vertices of the underlying quiver.

EXAMPLES:

sage: P = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}}).path_semigroup()
sage: P.idempotents()
(e_1, e_2, e_3)

injective(k, vertex)

Return the indecomposable injective module over $$k$$ at the given vertex vertex.

This module is literally indecomposable only when $$k$$ is a field.

INPUT:

• $$k$$ – ring, the base ring of the representation

• vertex – integer, a vertex of the quiver

OUTPUT:

• QuiverRep, the indecomposable injective module at vertex vertex with base ring $$k$$

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['c','d']}}).path_semigroup()
sage: I2 = Q.I(GF(3), 2)
sage: Q.I(ZZ, 3).dimension_vector()
(4, 2, 1)
sage: Q.I(ZZ, 1).dimension_vector()
(1, 0, 0)


The vertex given must be a vertex of the quiver:

sage: Q.I(QQ, 4)
Traceback (most recent call last):
...
ValueError: must specify a valid vertex of the quiver

is_finite()

This partial semigroup is finite if and only if the underlying quiver is acyclic.

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}})
sage: Q.path_semigroup().is_finite()
True
sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}})
sage: Q.path_semigroup().is_finite()
False

iter_paths_by_length_and_endpoint(d, v)

An iterator over quiver paths with a fixed length and end point.

INPUT:

• d – an integer, the path length

• v – a vertex, end point of the paths

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['d']}, 3:{1:['c']}})
sage: F = Q.path_semigroup()
sage: F.is_finite()
False
sage: list(F.iter_paths_by_length_and_endpoint(4,1))
[c*a*d*c, c*b*d*c]
sage: list(F.iter_paths_by_length_and_endpoint(5,1))
[d*c*a*d*c, d*c*b*d*c]
sage: list(F.iter_paths_by_length_and_endpoint(5,2))
[c*a*d*c*a, c*b*d*c*a, c*a*d*c*b, c*b*d*c*b]

iter_paths_by_length_and_startpoint(d, v)

An iterator over quiver paths with a fixed length and start point.

INPUT:

• d – an integer, the path length

• v – a vertex, start point of the paths

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['d']}, 3:{1:['c']}})
sage: P = Q.path_semigroup()
sage: P.is_finite()
False
sage: list(P.iter_paths_by_length_and_startpoint(4,1))
[a*d*c*a, a*d*c*b, b*d*c*a, b*d*c*b]
sage: list(P.iter_paths_by_length_and_startpoint(5,1))
[a*d*c*a*d, a*d*c*b*d, b*d*c*a*d, b*d*c*b*d]
sage: list(P.iter_paths_by_length_and_startpoint(5,2))
[d*c*a*d*c, d*c*b*d*c]

ngens()

Return the number of generators (arrows() and idempotents()).

EXAMPLES:

sage: F = DiGraph({1:{2:['a','b'], 3:['c']}, 3:{1:['d']}}).path_semigroup()
sage: F.ngens()
7

projective(k, vertex)

Return the indecomposable projective module over $$k$$ at the given vertex vertex.

This module is literally indecomposable only when $$k$$ is a field.

INPUT:

• $$k$$ – ring, the base ring of the representation

• vertex – integer, a vertex of the quiver

OUTPUT:

• QuiverRep, the indecomposable projective module at vertex with base ring $$k$$

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['c','d']}}).path_semigroup()
sage: P2 = Q.P(GF(3), 2)
sage: Q.P(ZZ, 3).dimension_vector()
(0, 0, 1)
sage: Q.P(ZZ, 1).dimension_vector()
(1, 2, 4)


The vertex given must be a vertex of the quiver:

sage: Q.P(QQ, 4)
Traceback (most recent call last):
...
ValueError: must specify a valid vertex of the quiver

quiver()

Return the underlying quiver (i.e., digraph) of this path semigroup.

Note

The returned digraph always is an immutable copy of the originally given digraph that is made weighted.

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['d']}, 3:{1:['c']}},
....:             weighted=False)
sage: F = Q.path_semigroup()
sage: F.quiver() == Q
False
sage: Q.weighted(True)
sage: F.quiver() == Q
True

representation(k, *args, **kwds)

Return a representation of the quiver.

For more information see the QuiverRep documentation.

reverse()

The path semigroup of the reverse quiver.

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['d']}, 3:{1:['c']}})
sage: F = Q.path_semigroup()
sage: F.reverse() is Q.reverse().path_semigroup()
True

simple(k, vertex)

Return the simple module over $$k$$ at the given vertex vertex.

This module is literally simple only when $$k$$ is a field.

INPUT:

• $$k$$ – ring, the base ring of the representation

• vertex – integer, a vertex of the quiver

OUTPUT:

• QuiverRep, the simple module at vertex with base ring $$k$$

EXAMPLES:

sage: P = DiGraph({1:{2:['a','b']}, 2:{3:['c','d']}}).path_semigroup()
sage: S1 = P.S(GF(3), 1)
sage: P.S(ZZ, 3).dimension_vector()
(0, 0, 1)
sage: P.S(ZZ, 1).dimension_vector()
(1, 0, 0)


The vertex given must be a vertex of the quiver:

sage: P.S(QQ, 4)
Traceback (most recent call last):
...
ValueError: must specify a valid vertex of the quiver