9
$\begingroup$

We have a finite dimensional representation of a finite quiver over, say, the rationals. Is there an algorithm known to decompose this representation into its irreducible components?

A related question: we have two (finite-dimensional) representations of a finite quiver. Is there an algorithm to check if one is a summand of the other?

Thanks a lot for hints and pointers!

Improve this question
$\endgroup$
4
  • $\begingroup$ Well, unless you make some restriction on the shape of the quiver, the term "quiver representation" is just as general as "representation of an associative algebra". If you work over a finite field, your quiver is finite (resp. your algebra is finitely generated) and your modules are of finite dimension, then MAGMA can do a lot of those computations (e.g. indecomposable direct summands, composition series, isomorphism checking...). $\endgroup$
    – Florian Eisele
    Commented Feb 10, 2012 at 17:28
  • 1
    $\begingroup$ The first question is ambiguous. Do you want to find to find the composition facors of a representation or the decomposition into indecomposables. In any case, if you are working with finite dimensional representations over a field then the answer to all these questions is: Yes, an algorithm exists. $\endgroup$
    – Bruce Westbury
    Commented Feb 10, 2012 at 19:34
  • $\begingroup$ Thanks for the comments. I was thinking of the case where everything is finite and we are in characteristic 0. $\endgroup$
    – Christian Stump
    Commented Feb 11, 2012 at 11:20
  • $\begingroup$ The GAP package QPA ( math.ntnu.no/~oyvinso/QPA) can actually do this (decomposition into indecomposables and testing isomorphism) for finite fields at the moment and it is planned to extent this to finite field extensions over Q. $\endgroup$
    – Mare
    Commented Jan 12, 2017 at 14:10

1 Answer 1

Reset to default
8
$\begingroup$

If you want to decompose a finite-dimensional representation over, say, $\mathbb{Q}$ into its indecomposables over, say, $\overline{\mathbb{Q}}$, there is not only an algorithm but an efficient one (at least theoretically efficient: polynomial-time). See

Chistov, A., Ivanyos, G. and Karpkinski, M. Polynomial Time Algorithms for Modules over Finite Dimensional Algebras, ISSAC 1997.

It works more generally over finite fields, and the real or algebraic closures of number fields.

Not only that, but they also show how to test efficiently if two such representations are equivalent. These two pieces together answer your second question (when is one rep, say $R_1$, contained as a summand in another $R_2$): decompose both into indecomposables, then see if every indecomposable in $R_1$ appears in $R_2$ with greater or equal multiplicity (test each indecomposable of $R_1$ for equivalence to each indecomposable in $R_2$).

Update: Brooksbank and Luks (J. Algebra 2008, or freely available author's copy) provide another algorithm for these problems that is apparently efficient in both theory (polynomial-time) and practice (based on experiments in MAGMA). (This is all over finite-dimensional algebras; the OQ didn't specify whether the quiver could have directed cycles or not...)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .