42. Linear Combinations in Python
By Bernd Klein. Last modified: 03 Feb 2025.
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 · x1 + λ2 · x2 … λn · xn
p is the scalar product of the values x1, x2 … xn and
λ1, λ2 … λn are called scalars.
In most applications x1, x2 … xn are vectors and the lambdas are integers or real numbers. (For those, who prefer it more formally:
x1, x2 … xn ∈ V and V is a vector space, and
λ1, λ2 … λn ∈ K with K being a field)
Live Python training
Enjoying this page? We offer live Python training courses covering the content of this site.
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
OUTPUT:
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
OUTPUT:
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():
for i in [-1, 0, 1]:
for j in [-1,0,1]:
for k in [-1,0,1]:
for l in [-1,0,1]:
yield (i, j, k, l)
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():
for i in [-1, 0, 1]:
for j in [-1, 0, 1]:
for k in [-1, 0, 1]:
for l in [-1, 0, 1]:
yield (i, j, k, l)
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))
OUTPUT:
(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)
Live Python training
Enjoying this page? We offer live Python training courses covering the content of this site.
Upcoming online Courses
10 Mar 2025 to 14 Mar 2025
07 Apr 2025 to 11 Apr 2025
23 Jun 2025 to 27 Jun 2025
28 Jul 2025 to 01 Aug 2025
12 Mar 2025 to 14 Mar 2025
09 Apr 2025 to 11 Apr 2025
04 Jun 2025 to 06 Jun 2025
30 Jul 2025 to 01 Aug 2025
Efficient Data Analysis with Pandas
10 Mar 2025 to 11 Mar 2025
07 Apr 2025 to 08 Apr 2025
02 Jun 2025 to 03 Jun 2025
23 Jun 2025 to 24 Jun 2025
28 Jul 2025 to 29 Jul 2025
09 Apr 2025 to 11 Apr 2025
04 Jun 2025 to 06 Jun 2025