This article is cited in
3 papers
On the complexity of the “wild” matrix problems and of the isomorphism of algebras and of graphs
D. Yu. Grigor'ev
Abstract:
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).
UDC:
519.5+512.46