Revision history [back]
 | 1 | initial version |
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 version that reports candidates for each element u of U:
n = 3
M = matrix(n,n, [1, 1, 1, -1, 1, 1, -1, -1, 1])
List_S=[M^0,M^1,M^2]
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)
for u in U:
Y = X.span(mat_to_vector(t) for t in List_S + [u])
CAND = { mat_to_vector(w) for w in U if w!=u and mat_to_vector(w) in Y }
B = { matrix(ZZ,n,n,u,immutable=True) for u in CAND }
show("B=",len(B))
Running it, you'll see
'U=' 1020
'B=' 5
'B=' 5
'B=' 3
'B=' 5
...
That is, if you take U[0] as A1, you'll have only 5 candidates for A2, A3, A4. If you take U[1] as A1, you'll have only again 5 candidates, if you take U[2] as A1 you'll get only 3 candidates, etc.
| | 2 | No.2 Revision |
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 version that reports candidates for each element constructs solutions:u of U:
n = 3
M = matrix(n,n, k = 4 # number of matrices in the required linear combinations
#M = matrix(3,3, [1, 1, 1, -1, 1, 1, -1, -1, 1])
List_S=[M^0,M^1,M^2]
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)
QQ^(n^2)
result = set()
for u in U:
Combinations(U,k-d):
Y = X.span(mat_to_vector(t) for t in List_S + [u]) u)
CAND = { mat_to_vector(w) [ w for w in U if w!=u w not in u and mat_to_vector(w) in Y }
B = { matrix(ZZ,n,n,u,immutable=True) for ]
for v in Combinations(CAND,d):
if sum(u) + sum(v) == M:
result.add( frozenset( Matrix(w,immutable=True) for w in u in CAND }
show("B=",len(B))
+ v ) )
show(list(map(list,result)))
Running it, you'll see
'U=' 1020
'B=' 5
'B=' 5
'B=' 3
'B=' 5
...
That is, if you take U[0] as A1, you'll have only 5 candidates for A2, A3, A4. If you take U[1] as A1, you'll have only again 5 candidates, if you take U[2] as A1 you'll get only 3 candidates, etc.
| | 3 | No.3 Revision |
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:solutions for any matrix M:
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 = QQ^(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:
result.add( sol = frozenset( Matrix(w,immutable=True) for w in u + v ) )
if sol not in result:
Z = X.span(mat_to_vector(t) for t in u+v)
if all( mat_to_vector(w[0]*w[1]) in Z for w in Permutations(sol,2) ): # this check is still necessary
result.add( sol )
show(list(map(list,result)))
| | 4 | No.4 Revision |
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:
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 = QQ^(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)
if all( mat_to_vector(w[0]*w[1]) in Z for w in Permutations(sol,2) ): # this check is still necessary
necessary check
result.add( sol )
show(list(map(list,result)))
| | 5 | No.5 Revision |
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:
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 = QQ^(n^2)
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)
if all( mat_to_vector(w[0]*w[1]) in Z for w in Permutations(sol,2) ): # necessary check
result.add( sol )
show(list(map(list,result)))
| | 6 | No.6 Revision |
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 Permutations(sol,2) ): # necessary check
itertools.product(sol,repeat=2) ):
result.add( sol )
show(list(map(list,result)))
