Revision history [back]

Given a square matrix M, to find (say) five sets of, (say) 4 matrices A1,A2,A3,A4 such that

(i) each Ai is a unique 0,1 or 0,-1 matrix

(ii) each Ai is not - all zeroes or all ones or all minus ones matrix(that is, matrices with all entries same are not allowed)

(iii) M= A1+A2+A3+A4

(iv) Each matrix product AiAj (i,j=1,2,3,4)is a linear combination of A1,A2,A3,A4 with integer coefficients.

This is the same problem which was discussed in :

https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/

But there we wanted “all possible combinations” satisfying the required conditions. There we basically discussed the process for first getting all combinations satisfying (iii) and then checked condition(iv). But for 3rd order and above no output even after one week.

So thought that rather than first collecting all combinations satisfying(iii) it would be better to check (iv) alongside individually and after say, five outputs , the program ends, as even this much would also help me for my work . I have made the following code:

#Given Matrix 
 M = matrix(2,2, [1, 2, 2, -1])
 show("M=",M)
 n = int(input("Enter the order of the matrix M : "))

 T = Tuples((0,1),(n^2))


 #Removing all-zero and all-one tuples as not needed for our case"
 R=T.list()[1:-1]

 #Forming n by n matrices from  list in R. Contains all {0,1 }matrices.
 P = []
 for v in R:    
       P.append(matrix(ZZ,n,n,v))

 #Forming all n by n , {0,-1} matrices.    
 N=[]
 for a in P:
      b=-a
 N.append(b)   

 test_sum = int(input("In how many matrices you want to break M :"))

 num_nonneg = int(input("How many matrices with non-negative entries you want :"))
 num_nonpos = (test_sum)-(num_nonneg)           

 nonneg_comb = Combinations(P, num_nonneg)
 nonpos_comb = Combinations(N, num_nonpos )

#Defining a function which converts matrix to vector

def mat_to_vector(m):
        return vector( sum(map(list,m.rows()), []), immutable=True )

Counter=0
X = ZZ^(n^2)

for a in nonneg_comb:
      for b in nonpos_comb:
      flag=0
      V = X.span(mat_to_vector((a+b)[i]) for i in range(len((a+b))))
      for i in range(test_sum):
            for j in range(test_sum):   

                if( (sum(a+b)!=M) or  (mat_to_vector((a+b)[i]*(a+b)[j]) not  in V)):
                flag=1

    if(flag==0):

                Counter+=1
                show("(",Counter,").",  a+b)  

    if Counter==5:
         break;

But this is also time taking. So, wanted to know how it can be speeded up or how the code given by Max Alekseyev in the above link can accordingly be edited.

Given a square matrix M, to find (say) five sets of, (say) 4 matrices A1,A2,A3,A4 such that

(i) each Ai is a unique 0,1 or 0,-1 matrix

(ii) each Ai is not - all zeroes or all ones or all minus ones matrix(that is, matrices with all entries same are not allowed)

(iii) M= A1+A2+A3+A4

(iv) Each matrix product AiAj (i,j=1,2,3,4)is a linear combination of A1,A2,A3,A4 with integer coefficients.

This is the same problem which was discussed in :

https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/

But there we wanted “all possible combinations” satisfying the required conditions. There we basically discussed the process for first getting all combinations satisfying (iii) and then checked condition(iv). But for 3rd order and above no output even after one week.

So thought that rather than first collecting all combinations satisfying(iii) it would be better to check (iv) alongside individually and after say, five outputs , the program ends, as even this much would also help me for my work . I have made the following code:

#Given Matrix 
 M = matrix(2,2, [1, 2, 2, -1])
 show("M=",M)
 n = int(input("Enter the order of the matrix M : "))

 T = Tuples((0,1),(n^2))


 #Removing all-zero and all-one tuples as not needed for our case"
 R=T.list()[1:-1]

 #Forming n by n matrices from  list in R. Contains all {0,1 }matrices.
 P = []
 for v in R:    
       P.append(matrix(ZZ,n,n,v))

 #Forming all n by n , {0,-1} matrices.    
 N=[]
 for a in P:
      b=-a
 N.append(b)   

 test_sum = int(input("In how many matrices you want to break M :"))

 num_nonneg = int(input("How many matrices with non-negative entries you want :"))
 num_nonpos = (test_sum)-(num_nonneg)           

 nonneg_comb = Combinations(P, num_nonneg)
 nonpos_comb = Combinations(N, num_nonpos )

#Defining a function which converts matrix to vector

def mat_to_vector(m):
        return vector( sum(map(list,m.rows()), []), immutable=True )

Counter=0
X = ZZ^(n^2)

for a in nonneg_comb:
      for b in nonpos_comb:
      flag=0
      V = X.span(mat_to_vector((a+b)[i]) for i in range(len((a+b))))
      for i in range(test_sum):
            for j in range(test_sum):   

                if( (sum(a+b)!=M) or  (mat_to_vector((a+b)[i]*(a+b)[j]) not  in V)):
                flag=1

    if(flag==0):

                Counter+=1
                show("(",Counter,").",  a+b)  

    if Counter==5:
         break;

But this is also time taking. taking for higher orders. So, wanted to know how it can be speeded up or how the code given by Max Alekseyev in the above link can accordingly be edited.