计算符号二元矩阵的共轭或逆的单个元素

Question

我试图获得矩阵A的共轭A_adj的单个元素，两者都需要是符号表达式，其中符号x_i是二进制的，矩阵A是对称的和稀疏的。Python的sympy可以很好地解决小问题:

from sympy import zeros, symbols
size = 4
A = zeros(size,size)
x_i = [x for x in symbols(f'x0:{size}')]
for i in range(size-1):
A[i,i] += 0.5*x_i[i]
A[i+1,i+1] += 0.5*x_i[i]
A[i,i+1] = A[i+1,i] = -0.3*(i+1)*x_i[i]
A_adj_0 = A[1:,1:].det()
A_adj_0

这计算了协因子矩阵的第一个元素A_adj_0(这是相应的次元)，并正确地给出了0.125x_0x_1x_2 - 0.28x_2x_2^2 - 0.055x_1^2x_2 - 0.28x_1x_2^2，这是我需要的表达式，但有两个问题:

1. 这对于较大的矩阵是完全不可行的(我需要sizes的~100)。
2. x_i是二进制变量(即0或1)，sympy似乎没有办法简化二进制变量的表达式，即简化多项式x_i^n = x_i。

第一个问题可以通过求解线性方程组Ay = b来部分解决，其中b被设置为第一个基向量[1, 0, 0, 0]，使得y是A逆的第一列。y的第一项是A逆的第一个元素:

b = zeros(size,1)
b[0] = 1
y = A.LUsolve(b)
s = {x_i[i]: 1 for i in range(size)}
print(y[0].subs(s) * A.subs(s).det())
print(A_adj_0.subs(s))

这里的问题是y的第一个元素的表达式非常复杂，即使在使用simplify()等之后也是如此。这将是一个非常简单的表达式，它简化了上面第2点提到的二进制表达式。这是一种更快的方法，但对于更大的矩阵仍然不可行。

这可以归结为我的实际问题:

是否有一种有效的方法来计算一个稀疏和对称符号矩阵的共轭的单个元素，其中符号是二进制值?

我也可以使用其他软件。

附录1:
似乎可以通过简单的自定义替换来简化sympy中的二进制表达式，这是我没有意识到的:

A_subs = A_adj_0
for i in range(size):
A_subs = A_subs.subs(x_i[i]*x_i[i], x_i[i])
A_subs

Answer 1

您应该确保在sympy中使用Rational而不是float，因此S(1)/2或Rational(1, 2)而不是0.5。

在sympy中有一个新的(未记录的，目前是内部的)矩阵实现，称为DomainMatrix。对于这样的问题，它可能会快得多，并且总是以完全展开的形式产生多项式结果。我希望它能更快地解决这类问题，但它似乎仍然相当慢，因为它内部不是稀疏的(到目前为止——这可能会在下一个版本中改变)，而且它没有利用二进制值符号的简化。它可以在GF(2)上工作，但不能与假定在GF(2)中的符号一起工作，这是不同的。

如果有帮助的话，下面是你在sympy 1.7.1中使用它的方式:

from sympy import zeros, symbols, Rational
from sympy.polys.domainmatrix import DomainMatrix

size = 10
A = zeros(size,size)
x_i = [x for x in symbols(f'x0:{size}')]
for i in range(size-1):
A[i,i] += Rational(1, 2)*x_i[i]
A[i+1,i+1] += Rational(1, 2)*x_i[i]
A[i,i+1] = A[i+1,i] = -Rational(3, 10)*(i+1)*x_i[i]
# Convert to DomainMatrix:
dM = DomainMatrix.from_list_sympy(size-1, size-1, A[1:, 1:].tolist())
# Compute determinant and convert back to normal sympy expression:
# Could also use dM.det().as_expr() although it might be slower
A_adj_0 = dM.charpoly()[-1].as_expr()
# Reduce powers:
A_adj_0 = A_adj_0.replace(lambda e: e.is_Pow, lambda e: e.args[0])
print(A_adj_0)