Computing a single element of the adjugate or inverse of a symbolic binary matrix

Question

I'm trying to get a single element of an adjugate A_adj of a matrix A, both of which need to be symbolic expressions, where the symbols x_i are binary and the matrix A is symmetric and sparse. Python's sympy works great for small problems:

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

This calculates the first element A_adj_0 of the cofactor matrix (which is the corresponding minor) and correctly gives me 0.125x_0x_1x_2 - 0.28x_2x_2^2 - 0.055x_1^2x_2 - 0.28x_1x_2^2, which is the expression I need, but there are two issues:

1. This is completely unfeasible for larger matrices (I need this for sizes of ~100).
2. The x_i are binary variables (i.e. either 0 or 1) and there seems to be no way for sympy to simplify expressions of binary variables, i.e. simplifying polynomials x_i^n = x_i.

The first issue can be partly addressed by instead solving a linear equation system Ay = b, where b is set to the first basis vector [1, 0, 0, 0], such that y is the first column of the inverse of A. The first entry of y is the first element of the inverse of 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))

The problem here is that the expression for the first element of y is extremely complicated, even after using simplify() and so on. It would be a very simple expression with simplification of binary expressions as mentioned in point 2 above. It's a faster method, but still unfeasible for larger matrices.

This boils down to my actual question:

Is there an efficient way to compute a single element of the adjugate of a sparse and symmetric symbolic matrix, where the symbols are binary values?

I'm open to using other software as well.

Addendum 1:
It seems simplifying binary expressions in sympy is possible with a simple custom substitution which I wasn't aware of:

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

question from:https://stackoverflow.com/questions/65882151/computing-a-single-element-of-the-adjugate-or-inverse-of-a-symbolic-binary-matri

Answer 1

You should make sure to use Rational rather than floats in sympy so S(1)/2 or Rational(1, 2) rather than 0.5.

There is a new (undocumented and for the moment internal) implementation of matrices in sympy called DomainMatrix. It is likely to be a lot faster for a problem like this and always produces polynomial results in a fully expanded form. I expect that it will be much faster for this kind of problem but it still seems to be fairly slow for this because is is not sparse internally (yet - that will probably change in the next release) and it does not take advantage of the simplification from the symbols being binary-valued. It can be made to work over GF(2) but not with symbols that are assumed to be in GF(2) which is something different.

In case it is helpful though this is how you would use it in 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)