## Linear Combination

### Definitions

A linear combination in mathematics is an expression constructed from a set of terms by multiplying
each term by a constant and adding the results.

Example of a linear combination:

a · x + b · y is a linear combination of x and y with a and b constants.

Generally;

p = λ_{1} · x_{1} + λ_{2} ·
x_{2} … λ_{n} · x_{n}

p is the scalar product of the values x_{1}, x_{2} … x_{n} and
λ_{1}, λ_{2} … λ_{n} are called scalars.

In most applications x_{1}, x_{2} … x_{n} are vectors and
the lambdas are
integers or real numbers. (For those, who prefer it mor formally: x_{1}, x_{2} …
x_{n} ∈ V and V is a vector space, and
λ_{1}, λ_{2} … λ_{n} ∈ K with K being a field)

### Linear Combinations in Python

The vector y = (3.21, 1.77, 3.65) can be easily written as a linear combination of the unit vectors (0,0,1), (0,1,0) and (1,0,0):(3.21, 1.77, 3.65) = 3.21 · (1,0,0) + 1.77 (0,1,0) + 3.65 · (0,0,1)

We can do the calculation with Python, using the module numpy:

>>> import numpy as np >>> x = np.array([[0,0,1],[0,1,0],[1,0,0]]) >>> y = ([3.65,1.55,3.42]) >>> scalars = np.linalg.solve(x,y) >>> scalars array([ 3.42, 1.55, 3.65]) >>>The previous example was very easy, because we could work out the result in our head. What about writing our vector y = (3.21, 1.77, 3.65) as a linear combination of the vectors (0,1,1), (1,1,0) and (1,0,1)? It looks like this in Python:

>>> import numpy as np >>> x = np.array([[0,1,1],[1,1,0],[1,0,1]]) >>> y = ([3.65,1.55,3.42]) >>> scalars = np.linalg.solve(x,y) >>> scalars array([ 0.66, 0.89, 2.76]) >>>

### Another Example

Any integer between -40 and 40 can be written as a linear combination of 1,3,9,27 with scalars being elements of the set {-1,0,1}.For example:

7 = 1 · 1 + (-1) · 3 + 1 · 9 + 0 · 27

We can calculate these scalars with Python. First we need a generator generating all the possible scalar combinations. If you have problems in understanding the concept of a generator, we recommend the chapter "Iterators and Generators" of our tutorial.

def factors_set(): factors_set = ( (i,j,k,l) for i in [-1,0,1] for j in [-1,0,1] for k in [-1,0,1] for l in [-1,0,1]) for factor in factors_set: yield factor

We will use the memoize() technique (see chapter "Memoization and Decorators" of our tutorial) to memorize previous results:

def memoize(f): results = {} def helper(n): if n not in results: results[n] = f(n) return results[n] return helper

Finally, in our function linear_combination() we check every scalar tuple, if it can create the value n:

@memoize def linear_combination(n): """ returns the tuple (i,j,k,l) satisfying n = i*1 + j*3 + k*9 + l*27 """ weighs = (1,3,9,27) for factors in factors_set(): sum = 0 for i in range(len(factors)): sum += factors[i] * weighs[i] if sum == n: return factors

Putting it all together results in the following script:

def factors_set(): factors_set = ( (i,j,k,l) for i in [-1,0,1] for j in [-1,0,1] for k in [-1,0,1] for l in [-1,0,1]) for factor in factors_set: yield factor def memoize(f): results = {} def helper(n): if n not in results: results[n] = f(n) return results[n] return helper @memoize def linear_combination(n): """ returns the tuple (i,j,k,l) satisfying n = i*1 + j*3 + k*9 + l*27 """ weighs = (1,3,9,27) for factors in factors_set(): sum = 0 for i in range(len(factors)): sum += factors[i] * weighs[i] if sum == n: return factors # calculate the linear combinations of the first 10 positive integers: for i in range(1,11): print(linear_combination(i))

Calling this program returns the following results:

(1, 0, 0, 0) (-1, 1, 0, 0) (0, 1, 0, 0) (1, 1, 0, 0) (-1, -1, 1, 0) (0, -1, 1, 0) (1, -1, 1, 0) (-1, 0, 1, 0) (0, 0, 1, 0) (1, 0, 1, 0)