CODEWITHSUNDEEP
pythonmatrixsage
Bobert
Bobert

Reputation: 31

How to create a matrix from a generating set

I am trying to form a matrix using a generating set of some vectors (v1, v2, v3), where each element represents binary data.

I want the code to use the vectors in the set and create a matrix with the zero vector, each of the row vectors, and the combinations v1+v2, v1+v3, v2+v3 and v1+v2+v3, ie. all the possible linear combinations with 0 and 1 as coefficients.

I've tried using for loops, but I end up with repeats. I've also been able to do it by doing each of the operations but this isn't feasible for generating sets with many vectors.

import numpy as np
A = np.matrix([[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1]])

I want to create a new matrix made from all possible linear combinations of the row vectors from the above matrix A.

The output should contain the following:

[0,0,0,0,0,0,0,0], 
[1,1,1,1,0,0,0,0], 
[0,0,1,1,1,1,0,0], 
[0,0,0,0,1,1,1,1], 
[1,1,0,0,1,1,0,0], 
[0,0,1,1,0,0,1,1],
[1,1,1,1,1,1,1,1], 
[1,1,0,0,0,0,1,1]

Upvotes: 1

Views: 375

Answers (2)

pault
pault

Reputation: 43524

The way I look at this problem is that you have a set of coefficients:

coeffs = [0, 1]

The goal is to get all combinations of the coefficients multiplied by the vectors. Mathematically, you want to apply the following coefficients to your vectors:

from itertools import chain, combinations_with_replacement, permuations
import numpy as np

A = np.matrix([[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1]])

N = len(A)
all_coeffs = (
    chain.from_iterable(
        list(set(permutations(x, N))) for x in combinations_with_replacement(coeffs, N)
    )
)
print(list(all_coeffs))
#[(0, 0, 0),
# (1, 0, 0),
# (0, 1, 0),
# (0, 0, 1),
# (0, 1, 1),
# (1, 1, 0),
# (1, 0, 1),
# (1, 1, 1)]

So you need to take the dot product of each of the coefficients with each of the rows in A, and then "sum" the result. Since you're working with binary numbers, the addition operation can be achieved using the xor operator. Finally you can concatenate the results together.

Putting this all together:

from functools import reduce
from operator import xor

N = len(A)
mat = np.concatenate(
    [
        reduce(xor, (a*b for a, b in zip(c, A)))
        for c in (
            chain.from_iterable(
                list(set(permutations(x, N))) for x in 
                combinations_with_replacement(coeffs, N)
            )
        )
    ]
)
print(mat)
#[[0 0 0 0 0 0 0 0]
# [1 1 1 1 0 0 0 0]
# [0 0 1 1 1 1 0 0]
# [0 0 0 0 1 1 1 1]
# [0 0 1 1 0 0 1 1]
# [1 1 0 0 1 1 0 0]
# [1 1 1 1 1 1 1 1]
# [1 1 0 0 0 0 1 1]]

Upvotes: 0

ashish-ucsb
ashish-ucsb

Reputation: 101

I think this is what you want.

import numpy as np
from itertools import combinations

v = np.array([[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1]]) # v1, v2, v3

l = [] # creating a list of possible combinations [(0, 1), (0, 2), (1, 2), (0, 1, 2)]
for j in range(2, v.shape[0]+1):
    comb = combinations(np.arange(v.shape[0]), j)  
    for i in list(comb): 
        l.append(i)

final = np.zeros((len(l), v.shape[1]))  # creating final matrix 

for i in range(len(l)): # filling final matrix based on combinations
    for j in (l[i]):
        final[i] += v[j]

final = np.concatenate((np.zeros((1,v.shape[1])), v, final%2), axis=0)

#array([[0., 0., 0., 0., 0., 0., 0., 0.],
#       [1., 1., 1., 1., 0., 0., 0., 0.],
#       [0., 0., 1., 1., 1., 1., 0., 0.],
#       [0., 0., 0., 0., 1., 1., 1., 1.],
#       [1., 1., 0., 0., 1., 1., 0., 0.],
#       [1., 1., 1., 1., 1., 1., 1., 1.],
#       [0., 0., 1., 1., 0., 0., 1., 1.],
#       [1., 1., 0., 0., 0., 0., 1., 1.]])

Upvotes: 1

Related Questions