# Revision history [back]

I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some modifications (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some modifications (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:

import iprocessing as mp

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
a, b = comb
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some modifications more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:

import iprocessing as mp

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
a, b = comb
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:

import iprocessing as mp

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
a, b = comb
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


Here is the new code:

import multiprocessing as mp
import itertools

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination of positive and negative matrices
def check_combination(a, b):
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:

import iprocessing multiprocessing as mp
import itertools

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
a, b = comb
check_combination(a, b):
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
show("(", Counter, ").", a+b)  # Pass a and b as arguments to show
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


Here is the new code:

import multiprocessing as mp
import itertools

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination of positive and negative matrices
def check_combination(a, b):
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:

import multiprocessing as mp
import itertools

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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

# Add check to make sure num_nonpos is non-negative
if num_nonpos < 0:
num_nonpos = 0
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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination of positive and negative matrices
def check_combination(a, b):
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
show("(", Counter, ").", a+b)  # Pass a and b as arguments to show
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:

import multiprocessing as mp
import itertools

# Given Matrix
M #M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -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 = [matrix(ZZ, n, n, v) for v in R]

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

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

# Add check to make sure num_nonpos is non-negative
if num_nonpos < 0:
num_nonpos = 0
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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Define a function to check a single combination Iterate over all combinations of positive and negative matrices
def check_combination(a, b):
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
show("(", Counter, ").", a+b)  # Pass a and b as arguments to show
return True
return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
if result:
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break



I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:

# 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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:

import itertools

# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break


My final iteration, using the 'parallel' module:

import itertools
from sage.parallel.decorate import parallel

# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -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 = [matrix(ZZ, n, n, v) for v in R]

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

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)

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

# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]

# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)

# Initialize counter
Counter = 0

# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)

for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break


Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:

@parallel(ncpus=4)
def process_combinations(



You can give this a go, too.