Skip to content

02 — Quivers and relations

The mathematics

A quiver Q is a finite directed multigraph: a set of vertices Q_0 and a set of arrows Q_1, each arrow with a source and target vertex. Paths compose, and kQ is the path algebra. An admissible ideal I is generated by relations (linear combinations of parallel paths), and kQ/I is the bound quiver algebra. The library must decide one thing before it can do any homology: is kQ/I finite-dimensional? For a monomial ideal (generated by single paths) this is decidable exactly — kQ/I has a basis of the paths that avoid every forbidden path as a subword, and there are finitely many iff no such path can be extended forever.

How it is represented

A quiver is a class Quiver (combinat/quiver.py). It stores:

  • vertices — a list (ordered sequence) of vertex labels; labels may be any hashable value, typically integers [1, 2, 3];
  • arrows — a dict (lookup table) mapping each arrow's name to a tuple (source, target). So arrows = {"a": (1, 2), "b": (2, 1)} is the arrow a: 1 -> 2 and b: 2 -> 1. Arrow names must be identifiers (letters, digits, underscore) because they will appear verbatim inside relation strings.

A path is a tuple of arrow names, and — this is the load-bearing convention — read left to right: ("a", "b") means first traverse a, then b, so it is legal only when target(a) == source(b). This is the Assem–Simson–Skowroński convention. It matters because it fixes the meaning of every product in the algebra: a*b is "a then b", and in the multiplication table the first factor acts on the left. Get the convention backwards and every structure constant transposes. The methods word_source, word_target, and compose_ok (which checks target(a) == source(b) for every consecutive pair) enforce it.

A relation is parsed from a human string into a frozen (immutable) record Relation (combinat/relations.py) with three fields: terms, source, target. terms is a tuple of (coefficient, word) pairs — the coefficient is an exact Fraction, the word is a path tuple. A relation is monomial exactly when it has a single term.

How the computation runs

Parsing a relation string

parse_relation(s, quiver) turns e.g. "a*b - 2*c" into a Relation:

  1. _split_terms breaks the string at +/- signs into terms, keeping each sign attached: "a*b - 2*c" -> ["a*b", "-2*c"].
  2. _parse_term reads each term left to right. Factors are separated by *. A leading numeric factor is a coefficient and must come first ("2*a*b", never "a*2*b"); it is read by the exact rational parser, so "0.5*a" raises ExactnessError rather than being mistaken for an arrow. The form x^3 expands to three copies of the arrow x. Each remaining factor must be a known arrow name.
  3. The resulting word is checked with compose_ok; a non-composable path names the exact offending junction ("target(a) = 2 but source(b) = 3").
  4. Like terms are combined and zero-sum words dropped; a relation that cancels to nothing raises RelationError ("identically zero"). Finally all terms must be parallel — share one source and one target — or it is refused.

The finiteness certificate

Quiver.algebra(relations, field) parses the relations, and if they are all monomial hands off to build_monomial_algebra (Chapter 03), whose first job is deciding finiteness. This is the interesting algorithm (core/monomial.py).

The forbidden words are the relation paths. irreducible_paths(quiver, forbidden) builds a finite-state automaton whose states are pairs (vertex, window), where window is the last r-1 arrows traversed (r = length of the longest forbidden word). From a state you may follow an arrow out of that vertex unless doing so completes a forbidden word as a suffix. _automaton explores all reachable states (a breadth-first search using a deque, a double-ended queue). The reachable states and their labelled transitions form a directed graph.

Now the dichotomy:

  • _find_cycle runs a depth-first search over that state graph. If it finds a directed cycle, there are irreducible paths of every length along it, so kQ/I is infinite-dimensional — and the code raises NotFiniteDimensionalError naming the offending arrow cycle explicitly ("irreducible paths grow forever along the cycle x -> y -> x"), with a hint to add a relation killing a power of it.
  • If there is no cycle, the graph is a finite DAG (directed acyclic graph); the code enumerates every irreducible word by walking it, and returns them sorted by (length, word). That finite list is the certificate of finite-dimensionality, and it becomes the path basis of the algebra.

This is exact and loud: it never silently truncates. Either you get a finite basis or you get told precisely which cycle defeats you.

A worked micro-example — k[x]/(x^3)

Take Q with one vertex 1 and one loop x: 1 -> 1, relation "x^3".

  • Parsing "x^3" gives the monomial Relation with the single term (Fraction(1), ("x", "x", "x")), source 1, target 1. It is monomial (one term).
  • The forbidden word is ("x", "x", "x"), so r = 3 and the window keeps the last 2 arrows. From state (1, ()) you may take x to (1, ("x",)), then x to (1, ("x","x")); from there a third x would complete xxx and is refused. So the reachable non-trivial words are ("x",) and ("x","x") — the automaton has no cycle.
  • irreducible_paths therefore returns [("x",), ("x","x")]. Together with the trivial path at vertex 1 this gives the basis {1, x, x^2} — dimension 3, as expected.

If you had given no relation, _find_cycle would find the loop x -> x and raise NotFiniteDimensionalError — k[x] is infinite-dimensional, said out loud.

Where to look in the code

concept file function / class
quiver, arrows dict, path composition combinat/quiver.py Quiver, compose_ok, word_source, word_target
entry point kQ/I -> algebra combinat/quiver.py Quiver.algebra
relation parsing combinat/relations.py parse_relation, _parse_term, _split_terms, Relation
forbidden-word automaton core/monomial.py _automaton
infinite-cycle detector core/monomial.py _find_cycle, irreducible_paths
finiteness exception errors.py NotFiniteDimensionalError, RelationError