Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1997 Copyright 1997 University of Bonn, Department of Computer Science, Abt. V

Polynomial Time Algorithms for Modules over Finite Dimensional Algebras
Alexander Evdokimov, Marek Karpinski
[Download PostScript] [Download PDF]

We present polynomial time algorithms for some fundamental tasks from representation theory of finite dimensional algebras. These involve testing (and constructing) isomorphisms of modules as well as expressing of modules as direct sums of indecomposable modules. Over number fields the latter task seems to be difficult, therefore we restrict our attention to decomposition over finite fields and over the algebraic or real closure of number fields. The module isomorphism problem can be reformulated as follows. Let $A_1,\ldots ,A_m$ and $A_1^\prime,\ldots ,A_m^\prime$ be two families of $n\!\times\! n$--matrices with entries from the field $K$. The task is to find a nonsingular $n\!\times\! n$--matrix $X$ with entries from $K$ such that $XA_iX^{-1}=A_i^\prime$ for all $1\le i\le m$ (if such a matrix exists). In the case when $K$ is the field of the real algebraic numbers, we propose a method for the variant where the matrix $X$ is required to be orthogonal.

Last Change: 08/18/99 at 13:00:38
University of Bonn -> Department of Computer Science -> Chair V