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


In the test suite, we skip the associativity test, as in this example the paths used for testing can’t 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()
Join of Category of monoids and Category of infinite enumerated sets
sage: TestSuite(M).run()

Element

alias of QuiverPath

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)

Return the path algebra of the underlying quiver.

INPUT:

• k – a commutative ring

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

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


TESTS:

We check a single edge with a multi-character label:

sage: Q = DiGraph([[1,2,'abc']])
sage: PQ = Q.path_semigroup()
sage: PQ.all_paths(1,2)
[abc]


An example with multiple edges:

sage: Q = DiGraph([[1,2,'abc'], [1,2,'def']])
sage: PQ = Q.path_semigroup()
sage: PQ.all_paths(1,2)
[abc, def]

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):
...
NotImplementedError: infinite list

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()[1]
e_2
sage: P.5
c
sage: P.gens()[5]
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]


TEST:

sage: Q = DiGraph({1:{1:['a','b', 'c', 'd']}})
sage: P = Q.path_semigroup()
sage: list(P.iter_paths_by_length_and_startpoint(2,1))
[a*a,
a*b,
a*c,
a*d,
b*a,
b*b,
b*c,
b*d,
c*a,
c*b,
c*c,
c*d,
d*a,
d*b,
d*c,
d*d]
sage: len(list(P.iter_paths_by_length_and_startpoint(2,1)))
16

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

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

EXAMPLES:

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

representation(k, *args, **kwds)

Return a representation of the quiver.

For more information see the QuiverRep documentation.

TESTS:

sage: Q = DiGraph({1:{3:['a']}, 2:{3:['b']}}).path_semigroup()
sage: spaces = {1: QQ^2, 2: QQ^3, 3: QQ^2}
sage: maps = {(1, 3, 'a'): (QQ^2).Hom(QQ^2).identity(), (2, 3, 'b'): [[1, 0], [0, 0], [0, 0]]}
sage: M = Q.representation(QQ, spaces, maps)
sage: M
Representation with dimension vector (2, 3, 2)

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


Quiver Morphisms

#### Next topic

Quiver Representations