Skip to main content
MathOverflow

Return to Answer

Added ref to Brooksbank-Luks
Source Link
Joshua Grochow
Joshua Grochow
  • 3.2k
  • 1
  • 25
  • 37

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

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$).

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

Source Link
Joshua Grochow
Joshua Grochow
  • 3.2k
  • 1
  • 25
  • 37

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$).