On the complexity of the ``wild'' matrix problems and of the isomorphism of algebras and of graphs

D. Yu. Grigor'ev

Zapiski Nauchnykh Seminarov POMI, Theoretical application of methods of mathematical logic. Part III, Tome 105 (1981), pp. 10-17

Résumé

Polynomial time recogaizibility of the isomorphism of semisimple algebras over an algebraically closed field is shown. Also it is proved that graph isomorphism is $p$-equivalent to the problem of isomorphism of algebras $A$ (over an algebraically closed field $F$) having the property that $R^2=0$ and the factor-algebra $A/R$ is commutative, where $R$ is Jacobson radical of $A$. One reduction, i.e. a construction of an algebra (with the above properties) for each graph such that the isomorphism of any two graphs is equivalent to the isomorphism of the corresponding algebras, is known (see e.g. [10]). We show how to reduce isomorphism of such algebras to isomorphism of graphs supplied with the weights on their edges. Let $A$ be an algebra with the properties stated earlier. Then $A/R=F\otimes\dots\otimes F$ is a direct sum of $n$ copies of $F$. We choose some elements $\ell_1,\dots,\ell_n$ of $A$ which are mapped into the identity elements of the copies of $F$ in the direct sum $F\otimes\dots\otimes F$, correspondingly, under the canonical epimorphism $A\to A/R$. We define the graph $G_A$ with $n$, vertices and with weight $\dim_pe_i\operatorname{Re}_j$ on each edge $(i,j)$ for all $1\le i$, $j\le n$. Then $A$ is isomorphic to $B$ iff $G_A$ is isomorphic to $G_B$. The graph $G_A$ can be constructed in polynomial time from $A$. In addition we mention some open problems concerning the complexity of recognition of isomorphism of algebras, determination of radical and the complexity of solution of the standard “wild” matrix problem: does there exist a polynomial time algorithm to determine, given two pairs of integer matrices $(A,B)$ and $(C,D)$ whether there exists a nonsingular (rational) matrix $X$ such that $XAX^{-1}=C$, $XBX^{-1}=D$? It is known (see e.g. [1], [2]) that a lot of matrix problems and the problems of recognizing of isomorphism of modules over some algebras can be reduced to the standard “wild” matrix problem (and these reductions are $p$-reductions).