Write a procedure in python to find all linear combinations of a list of vectors

GWA 0
Viewed 40

I am having Linear Algebra Classes in College right now, and my professor decided to use the Coding the Matrix book to teach. However this book has a lot of python included, but I am not used to this language and I am struggling very much with the exercises that I have to make. Below I included the question and the closest solution that I have approached.

Problem 3.8.3: Write a procedure GF2_span with the following spec:
• input: a set D of labels and a list L of vectors over GF(2) with label-set D
• output: the list of all linear combinations of the vectors in L
(Hint: use a loop (or recursion) and a comprehension. Be sure to test your procedure on examples where L is an empty list.)

What I did by now:

def GF2_span(D,L):
    return [(x*y) for (x,y) in zip(D,L)]

However, this solution only gives me only one linear combination, but the question asks for all linear combinations.

The monitor of the class said that I am supposed to use a recursion. But since I am not aware of this kind of data structure, it is really difficult to me.

linear-algebra vector python
1 Answers

One of the nice things of python is that you can write things very close to its definition.

Assuming your vectors are equipped with the addition operator, i.e. you can do (v1 + v2)

Every linear combination will either include L[i] or not, we can user itertools.product to generate the indicator of every subset of L, then.

def GF2_span(D,L):
    dim_L = len(L[0])
    return [sum(li for ci,li in zip(C, L) if ci == 1) 
               for C in itertools.product([0,1], repeat=len(L)]

Alternatively, if the vectors support scalar multiplication is to write


def GF2_span(D,L):
    return [sum(ci * li for ci,li in zip(C, L)) 
               for C in itertools.product([0,1], repeat=len(L)]
usertYuR0
Related