Can't find error in my code

sgmth
31 ●2 ●7 ●16

Please refer to my question at https://ask.sagemath.org/question/638...

According to the suggestion given in the end by Max Alekseyev I have made a complete code. Here I am showing only the initial part , as problem lies in it . I don't know what I am missing or what mistake I have made.

M = matrix(3,3, [1, 1, 1, -1, 1, 1, -1, -1, 1])
List_S=[M^0,M^1,M^2]
n = 3
V = GF(2)^(n^2)
VL1=V.list()[1:]    
# Removing the all-zero list because not needed for our purpose
VL2=VL1[:-1]      
#Removing the all-ones list because not needed for our purpose
P=[]
for v in VL2:    
        P.append(matrix(ZZ,n,n,v))  
 #Forming n by n matrices from  list in  VL2. Contains all 0,1 matrices.                                               
 N=[]
for p in P:
       k=-p
       N.append(k)
 #Forming n by n matrices from P by taking their negative. Contains all 0,-1 matrices 
U = []
for a in P:
       U.append(a)
for b in N:
      U.append(b)    
#Taking union of P and N   
show("U=",len(U))
def mat_to_vector(m):
      temp = []
      for i in range(m.ncols()):
               for j in range(m.nrows()):
                      temp.append(m[i][j])
      return(vector(temp))
  #Defining a function which converts matrix to vector
CAND=[]
for i in range(len(U)):
       List_U=[U[i]]
       List_SU=List_S+List_U
       W=U[:]                 
       W.remove(W[i])         
       T=tuple(List_SU)
       X = ZZ^(n^2)
       Y = X.span(mat_to_vector(T[i]) for i in range(len(T))) 
       for w in W:
              if mat_to_vector(w)  in Y:
                      CAND.append(mat_to_vector(w)) 
       VTM=[matrix(ZZ,n,n,u) for u in CAND]
       for b in VTM:
             b.set_immutable()
       B = set(VTM)
show("B=",len(B))

According to the suggestion, len(B) should come out to be less than len(U). But it is coming out to be same as len(U). Kindly find the error.

Comments

Can you explain what your code does, what are B and U and why length of B should be smaller than that of U?

Max Alekseyev ( 2 years ago )

Btw,

for a in P:
       U.append(a)

can be simplified to U.extend(P).

Max Alekseyev ( 2 years ago )

Commented the code, to make it clear. First, formed (in P) all possible 0,1 matrices(excluding all zero and all ones matrices). Took their negatives(in N) and took U to be union of P and N, to get all possible 0,1 and 0,-1 matrices(len(U)=1020) . The candidates(pl. see the previous link) for A2,A3,A4 should come from U only. In List_SU taking A1 to be U[i] and running i over the range(len(U)) we are going over all 0,1 and 0,-1 matrices A1. W being a copy of U, removed this U[i] and checked which of the remaining 1019 elements in W are in the span of T(=tuple(List_SU)). The corresponding matrices VTM would be be the candidates for A2,A3,A4. To remove repetions in VTM formed its set B. But len(B) is also ...(more)

sgmth ( 2 years ago )

add a comment

answered 2 years ago

Max Alekseyev

6922 ●9 ●52 ●161

updated 2 years ago

The error is in combining candidates for different U[i] in the same list CAND. They should processed independently and mixing these candidates together does not make sense. Also, your code is quite messy and not Pythonic. Here is cleaned and extended version that constructs solutions for any matrix M:

import itertools

k = 4   # number of matrices in the required linear combinations

#M = matrix(3,3, [1, 1, 1, -1, 1, 1, -1, -1, 1])
M = matrix(2,2,[1,1,1,-1])
n = M.nrows()
d = M.minpoly().degree()

assert k >= d

List_S=[ M^i for i in range(d)]
VL2 = (GF(2)^(n^2)).list()[1:-1]
# Removing the all-zero and all-one lists because not needed for our purpose

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

N = [-p for p in P]
#Forming n by n matrices from P by taking their negative. Contains all 0,-1 matrices 

U = P + N
#Taking concatenation of P and N   

show("U=",len(U))

def mat_to_vector(m):
    return vector( sum(map(list,m.rows()), []), immutable=True )
#Defining a function which converts matrix to vector

X = ZZ^(n^2)
result = set()

for u in Combinations(U,k-d):
    Y = X.span(mat_to_vector(t) for t in List_S + u) 
    CAND = [ w for w in U if w not in u and mat_to_vector(w) in Y ]
    for v in Combinations(CAND,d):
        if sum(u) + sum(v) == M:
            sol = frozenset( Matrix(w,immutable=True) for w in u + v )   # a candidate solution as a set
            if sol not in result:
                Z = X.span(mat_to_vector(t) for t in u+v)
                # the following check is still required
                if all( mat_to_vector(w[0]*w[1]) in Z for w in itertools.product(sol,repeat=2) ):
                    result.add( sol )

show(list(map(list,result)))

link

Comments

Had processed them individually only, but didn't get all combinations.See below(So wrongly thought perhaps your suggestion points otherwise and hence had done that ).

For simplicity let us take M=matrix(2,2,[1,1,1,-1]) and n=2 in my code . (As it will take me time to make changes to extend your code kindly bear with my messy code for the time being) Kindly replace the portion in my code after the line "Y=...." with the following:

   ICAND=[]
   for w in W:
             if mat_to_vector(w)  in Y:                      
                     ICAND.append(mat_to_vector(w)) 

   VTM=[matrix(ZZ,n,n,u) for u in ICAND]

   Z=Combinations(VTM,3)
   for t in Z:
        if sum(t)+U[i]==M:
            show("Sum_Comb=",t+[U[i])

sgmth ( 2 years ago )

Note that , to get the "final required combinations" , for the candidates obtained in VTM we have to check following two things:

(i) Which 3 combinations of them summing up with U[i] would give M.

(ii) Out of those obtained in (i) for which of them, all products AiAj are a linear combination of A1,A2,A3,A4.

Now in the code, I have checked (i) only, but even output of (i) fails to show for example the following valid "final required combination"

  {  [1 0]      [0 1]     [0 0]     [ 0  0]
     [0 0] ,    [0 0]  ,  [1 0] ,   [ 0 -1]  }

sgmth ( 2 years ago )

@sgmth: Number of elements to add to List_S should be equal to the difference between the length of a linear required combination (k in my code) and the degree of minimal polynomial (d) of matrix M. For your 2x2 matrix, this difference is 2. Also, since we used only necessary condition, each candidate solution $A_1,A_2,A_3,A_4$ will further need to be tested on whether $A_iA_j$ is in the span $\langle A_1,A_2,A_3,A_4\rangle$ . I've updated my code to produce solutions for any given matrix based on this approach.

Max Alekseyev ( 2 years ago )

Thanks a lot. Appreciate your time and effort, and the detailed explanation. Works fine for n=2. Have run for n=3 and k=5 , four hours back but still processing. I guess because of the combinatorial nature, nothing further much can be done to speed up . Thanks again.

sgmth ( 2 years ago )

There is definitely space for further improvement.

Max Alekseyev ( 2 years ago )

see more comments

Can't find error in my code

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Can't find error in my code savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Can't find error in my code