|
University of Bonn -> Department of Computer Science -> Chair V | ||
CS-Reports 1996 | Copyright 1996 University of Bonn, Department of Computer Science, 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
Deutsch |
University of Bonn -> Department of Computer Science -> Chair V |