Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
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 with a
partial binary operation
,
which is written infix as a
sign and satisfies associativity in
the following sense: If
,
and
are three elements of
,
and if one of the products
and
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()
alias of QuiverPath
Return the indecomposable injective module over at the
given vertex vertex.
This module is literally indecomposable only when is a field.
INPUT:
OUTPUT:
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
Return the indecomposable projective module over at the given
vertex vertex.
This module is literally indecomposable only when is a field.
INPUT:
OUTPUT:
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
Return the simple module over at the given vertex
vertex.
This module is literally simple only when is a field.
INPUT:
OUTPUT:
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
Return the path algebra of the underlying quiver.
INPUT:
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
List of all paths between a pair of vertices (start, end).
INPUT:
OUTPUT:
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']], multiedges=True)
sage: PQ = Q.path_semigroup()
sage: PQ.all_paths(1,2)
[abc, def]
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)
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
Return a free module of rank over kP, where
is
self. (In other words, the regular representation.)
INPUT:
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)
Return generator number .
INPUT:
OUTPUT:
An idempotent, if 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
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
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)
Return the indecomposable injective module over at the
given vertex vertex.
This module is literally indecomposable only when is a field.
INPUT:
OUTPUT:
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
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
An iterator over quiver paths with a fixed length and end point.
INPUT:
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]
An iterator over quiver paths with a fixed length and start point.
INPUT:
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
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
Return the indecomposable projective module over at the given
vertex vertex.
This module is literally indecomposable only when is a field.
INPUT:
OUTPUT:
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
Return the underlying quiver (i.e., digraph) of this path semigroup.
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
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)
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
Return the simple module over at the given vertex
vertex.
This module is literally simple only when is a field.
INPUT:
OUTPUT:
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