Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1996 Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V 85152 Polynomial--time decomposition of modules over algebras and its application Alexander Christov, Marek Karpinski [Download PostScript] [Download PDF] Let $K$ be algebraically or real closed field, $\Lambda$ a finite dimensional assotiative $K$--algebra with the unity element and $V$ a finitely generated $\Lambda$--module. An algorithm of polynomial complexity is described in the paper which decomposes $V$ into the direct sum $V=\oplus_{i\in I}V_i$ of indecomposable $\Lambda$--modules $V_i$. In particular an algorithm is suggested for constructing all the projective non--isomorphic indecomposable $\Lambda$--modules. Also an algorithm of polynomial complexity is constructed which given two $\Lambda$--modules $V_1$ and $V_2$ decides whether $V_1$ is isomorphic to $V_2$ and if it is the fact constructs this isomorphism. As an application the following results are obtained. Let $A_1,\ldots ,A_m$ and $A'_1,\ldots ,A'_m$ be two families of $n\!\times\! n$--matrices with coefficients from $K$. An algorithm of polynomial complexity is described in the paper which decides whether there exists a nonsingular (respectively orthogonal) $n\!\times\! n$--matrix $S$ with coefficients from $K$ such that $SA_iS^{-1}=A'_i$ for all $1\le i\le m$ and if it is the fact this algorithm constructs such a matrix $S$. Last Change: 08/18/99 at 13:00:38  English Universität Bonn -> Institut für Informatik -> Abteilung V