Multiplicative equations over commuting matrices (Extended Abstract)
László Babai, Robert Beals, Jin Cai, Gábor Ivanyos, Eugene M. Luks · 1994
) L'aszl'o Babai 1 , Robert Beals 2 , Jin-yi Cai 3 , G'abor Ivanyos 4 , Eugene M. Luks 5 Mailing address: Robert Beals School of Mathematics Institute For Advanced Study Olden Lane Princeton, New Jersey, 08540 1 Department of Computer Science, University of Chicago, Chicago, Illinois 60637 and Eotvos University, Budapest, Hungary H-1088 2 DIMACS, Rutgers University, Piscataway, NJ 08855-1179 and Institute for Advanced Study, Princeton, NJ 08540 3 Department of Computer Science, SUNY at Buffalo, Buffalo, NY 14260 4 Computer and Automation Institute, Hungarian Academy of Sciences, P.O.Box 63, Budapest, Hungary H-1528 5 Department of Computer and Information Science, University of Oregon, Eugene, OR Abstract We consider the solvability of the equation k Y i=1 A i x i = B and generalizations, where the A i and B are given commuting matrices over an algebraic number field F . In the semigroup membership problem, the variables x i are constrained to be nonnegative i...