1 | initial version |

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

2 | No.2 Revision |

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

3 | No.3 Revision |

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

4 | No.4 Revision |

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:

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

5 | No.5 Revision |

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:

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

6 | No.6 Revision |

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:

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

7 | No.7 Revision |

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

8 | No.8 Revision |

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.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.