Given a (-1,1) square matrix A, to find all possible summands A1,A2,A3…..such that:
(i)each Ai is either a (0,1) or (0,-1) matrix which add upto A forming a sort of “partition” of A .
(By “partition” I mean that if a Ai has a non-zero entry at a particular position , then other Ai’s have to have zero at that position)
(ii) their pairwise products are linear combinations of A1,A2,A3,…with integer coefficients.
Note that the same problem(without the “partition” condition) was discussed at: https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/
(That approach won’t be useful here because of “partition” condition, things have simplified)
I have written a code below(with example of a 4th order matrix).
A= matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
#Given matrix
n=4
#Enter the order of the matrix
def mat_to_vector(m):
return vector( sum(map(list,m.rows()), []), immutable=True )
#Defining a function which converts matrix to vector
def p(x):
if x==1:
return 1
else:
return 0
#Defining a function which converts any non 1 entry to 0
l=A.apply_map(p)
#applying function p on the given matrix A
MTVP=mat_to_vector(l)
def j(x):
if x==-1:
return 1
else:
return 0
#Defining a function which converts (-1) entry to 1 and non (-1) entry to 0
k=A.apply_map(j)
#applying function j on the given matrix A
MTVN=mat_to_vector(k)
VP=VectorPartitions(MTVP)
VN=VectorPartitions(MTVN)
s = 4
#("Enter no.(>1) of (0,1) matrices u want")
P=[]
for a in VP:
if len(a)==s :
P.append(a)
t = 1
#("Enter no.(>1) of (0,-1) matrices u want")
TN=[]
for a in VN:
if len(a)==t :
TN.append(a)
N = [[[(-1) * x for x in y]for y in z]for z in TN]
# Multiplication by (-1) over the List
R=[]
for a in P:
for b in N:
r=a+b
R.append(r)
M=[[matrix(n,n,v) for v in t] for t in R]
test_sum=s+t
VVV = ZZ^(n^2)
Counter=0
for test in M:
VV = VVV.submodule(mat_to_vector(test[i]) for i in range(len(test)))
flag = 0
for i in range(test_sum):
for j in range(test_sum):
if(mat_to_vector(test[i]*test[j]) not in VV):
flag = 1
if(flag==0):
Counter+=1
show("(",Counter,").",test)
print("\n")
B=matrix([mat_to_vector(test[i]) for i in range(len(test))]);B
C=B.transpose();C
for i in range(test_sum):
for j in range(test_sum):
b=vector(mat_to_vector(test[i]*test[j]))
show('A',i+1, 'A',j+1, '=', C.solve_right(b))
#Showing the respective coefficients of A1,A2,A3....in the matrix products
How to improve upon it to make it run faster for higher orders?
