Multiplicative equations over commuting matrices
Multiplicative equations over commuting matrices
复制标题
交换矩阵上的乘法方程
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
E. Luks
中科院分区：
文献类型：
--
作者：
L. Babai;R. Beals;Jin;G. Ivanyos;E. Luks
我们考虑方程和推广的可解性，其中 A{sub i} 和 B 是给定代数数域 F 上的交换矩阵。在半群隶属问题中，变量 x{sub i} 被约束为非负整数。虽然这个问题对于变量 k 来说是 NP 完全的，但如果 k 是固定的，我们给出一个多项式时间算法。在群成员问题中，假设矩阵是可逆的，并且变量 x{sub i} 可以取负值。在这种情况下，我们给出变量 k 的多项式时间算法，并给出所有解集的显式描述（作为仿射格）。葛国强最近解决了 1 x 1 矩阵的特殊情况；我们非常依赖他的结果。
We consider the solvability of the equation and generalizations, where the A{sub i} and B are given commuting matrices over an algebraic number field F. In the semigroup membership problem, the variables x{sub i} are constrained to be nonnegative integers. While this problem is NP-complete for variable k, we give a polynomial time algorithm if k is fixed. In the group membership problem, the matrices are assumed to be invertible, and the variables x{sub i} may take on negative values. In this case we give a polynomial time algorithm for variable k and give an explicit description of the set of all solutions (as an affine lattice). The special case of 1 x 1 matrices was recently solved by Guoqiang Ge; we heavily rely on his results.