Linear combination
A few vectors are given. Which new vectors can be built from them by scaling and adding, and how do you find the amounts?
Where you are 8 in Vectors in n dimensions
Why this exists
Arnav, Ishani and Saanvi mix paint from three base paints. Each liter of a base carries a fixed amount of each pigment, so a base is a vector: (3, 1, 0) means 3 grams of red, 1 of yellow and none of white per liter. A batch of c_1 liters of base \mathbf{s}_1, c_2 of \mathbf{s}_2 and c_3 of \mathbf{s}_3 holds
grams of pigment: the adding and scaling of Adding and scaling vectors in n dimensions, used at once. Forward, finding the batch from the liters is arithmetic. Backward, finding the liters that give the pigment a color needs, if any exist, means solving equations whose unknowns are the amounts. That backward question is the one linear algebra asks more than any other.
Definition
Let \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k be vectors in \mathbb{R}^n, all with the same n, and let c_1, c_2, \dots, c_k be scalars. The vector
is the linear combination of \mathbf{v}_1, \dots, \mathbf{v}_k with weights c_1, \dots, c_k. A vector \mathbf{b} is a linear combination of \mathbf{v}_1, \dots, \mathbf{v}_k when some choice of weights makes the combination equal to \mathbf{b}.
The weights can be any real numbers, including negatives, fractions and zero; the list is finite; the result is in \mathbb{R}^n. A multiple c\mathbf{v}, a sum \mathbf{u} + \mathbf{v} (weights 1, 1) and a difference \mathbf{u} - \mathbf{v} (weights 1, -1) are all combinations. Weights all zero give \mathbf{0}, so \mathbf{0} is a combination of any list. In the plane, 3\mathbf{i} - 5\mathbf{j} (Unit vectors and i, j notation) is a combination of \mathbf{i} and \mathbf{j}.
With \mathbf{a}_1 = (1, -1, 3) and \mathbf{a}_2 = (3, 1, -2) in \mathbb{R}^3, the combination with weights 2 and -1 is
Example 2 runs the question the other way.
The standard vectors of \mathbb{R}^n are \mathbf{e}_1 = (1, 0, \dots, 0), \mathbf{e}_2 = (0, 1, 0, \dots, 0), through \mathbf{e}_n = (0, \dots, 0, 1): \mathbf{e}_i has 1 in position i and 0 elsewhere. In \mathbb{R}^2 they are \mathbf{i} and \mathbf{j}.
Intuition
In \mathbb{R}^2 a combination is a walk. Take \mathbf{v}_1 = (2, 1) and \mathbf{v}_2 = (1, 2). Copies of the two arrows laid tip to tail cover the plane with a slanted grid, and c_1\mathbf{v}_1 + c_2\mathbf{v}_2 is where you stand after c_1 steps along \mathbf{v}_1 and c_2 steps along \mathbf{v}_2. The order of the steps does not matter, because vector addition is commutative. A negative weight walks backward, and a fractional weight stops between grid lines.
The walk to \mathbf{w} = (4, 5) is one step along \mathbf{v}_1 and two along \mathbf{v}_2, so \mathbf{w} = \mathbf{v}_1 + 2\mathbf{v}_2. The walk to \mathbf{p} = (-1, 4) is two steps backward along \mathbf{v}_1, then three along \mathbf{v}_2, so \mathbf{p} = -2\mathbf{v}_1 + 3\mathbf{v}_2. The weights are the point’s address on the slanted grid, as ordinary coordinates are its address on the square grid of \mathbf{i} and \mathbf{j}.
Past three entries there is no picture, and the recipe reading takes over: the vectors are ingredients and the weights are amounts.
Results
Every vector is a combination of the standard vectors. For \mathbf{x} = (x_1, \dots, x_n) in \mathbb{R}^n,
and the entries of \mathbf{x} are the only weights that work.
Finding weights is solving a system. \mathbf{b} = c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k exactly when, for every position i = 1, \dots, n,
So \mathbf{b} is a combination of \mathbf{v}_1, \dots, \mathbf{v}_k exactly when this system of n equations in the unknowns c_1, \dots, c_k has a solution, and each solution is a list of weights. The augmented matrix of the system has columns \mathbf{v}_1, \dots, \mathbf{v}_k, \mathbf{b}, so row reduction settles any case.
A combination of combinations is a combination. If \mathbf{x} = c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k and \mathbf{y} = d_1\mathbf{v}_1 + \dots + d_k\mathbf{v}_k, then for all scalars r and s,
Why it is true
Standard vectors. Only \mathbf{e}_i has a nonzero i-th entry, so the i-th entry of c_1\mathbf{e}_1 + \dots + c_n\mathbf{e}_n is c_i. That equals x_i for every i exactly when every c_i = x_i, which proves both claims.
The system. By the definitions of scaling and adding, the i-th entry of c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k is c_1(\mathbf{v}_1)_i + \dots + c_k(\mathbf{v}_k)_i, and two vectors are equal exactly when all matching entries are.
Combinations of combinations. Distribute r and s and merge the products of scalars (properties 5 and 7 of Adding and scaling vectors in n dimensions). Reorder and regroup so the two terms in each \mathbf{v}_j sit together (properties 1 and 2), and collect each pair, rc_j\mathbf{v}_j + sd_j\mathbf{v}_j = (rc_j + sd_j)\mathbf{v}_j (property 6).
Worked examples
Computing a combination in \mathbb{R}^4
Let \mathbf{v}_1 = (2, 0, -1, 3), \mathbf{v}_2 = (1, 4, 2, -2) and \mathbf{v}_3 = (0, -3, 5, 1). Find the combination with weights 2, -1, 3.
SolutionScale each vector by its weight, then add position by position:
Is it a combination? Two answers
With \mathbf{a}_1 = (1, -1, 3) and \mathbf{a}_2 = (3, 1, -2), decide whether each vector is a linear combination of \mathbf{a}_1 and \mathbf{a}_2, and if so find the weights: (a) \mathbf{b} = (7, 1, -1); (b) \mathbf{d} = (1, 1, 1).
Solution(a) We need c_1\mathbf{a}_1 + c_2\mathbf{a}_2 = \mathbf{b}. Matching the three entries gives three equations in two unknowns:
Adding the first two eliminates c_1: 4c_2 = 8, so c_2 = 2, and the first gives c_1 = 7 - 6 = 1. These are the only values the first two equations allow, so the third must hold for them or for nothing. It holds, 3(1) - 2(2) = -1, so
with exactly one list of weights. Check: (1, -1, 3) + (6, 2, -4) = (7, 1, -1).
(b) Now the right sides are 1, 1, 1. Adding the first two gives 4c_2 = 2, so \displaystyle c_2 = \frac{1}{2} and \displaystyle c_1 = 1 - \frac{3}{2} = -\frac{1}{2}. The third equation then reads \displaystyle 3\left(-\frac{1}{2}\right) - 2\left(\frac{1}{2}\right) = -\frac{5}{2}, not 1. No weights satisfy all three, so \mathbf{d} is not a linear combination of \mathbf{a}_1 and \mathbf{a}_2.
Weights on the grid
With \mathbf{v}_1 = (2, 1) and \mathbf{v}_2 = (1, 2) from the grid figure, find the weights that write any (x, y) as c_1\mathbf{v}_1 + c_2\mathbf{v}_2, confirm the walks to \mathbf{w} and \mathbf{p}, and write \mathbf{e}_1 = (1, 0) as a combination of \mathbf{v}_1 and \mathbf{v}_2.
SolutionThe entries give 2c_1 + c_2 = x and c_1 + 2c_2 = y. Twice the first minus the second leaves 3c_1 = 2x - y; twice the second minus the first leaves 3c_2 = 2y - x. So
The elimination forced these values, and they work: \displaystyle 2c_1 + c_2 = \frac{4x - 2y + 2y - x}{3} = x, and likewise c_1 + 2c_2 = y. So each (x, y) has exactly one list of weights.
For \mathbf{w} = (4, 5): \displaystyle c_1 = \frac{8 - 5}{3} = 1 and \displaystyle c_2 = \frac{10 - 4}{3} = 2, the walk in the figure. For \mathbf{p} = (-1, 4): \displaystyle c_1 = \frac{-2 - 4}{3} = -2 and \displaystyle c_2 = \frac{8 + 1}{3} = 3. For \mathbf{e}_1:
Check: \displaystyle \left(\frac{4}{3}, \frac{2}{3}\right) - \left(\frac{1}{3}, \frac{2}{3}\right) = (1, 0). Fractional weights put \mathbf{e}_1 inside a cell of the grid.
Mixing paint
The bases hold, in grams per liter of (red, yellow, white), \mathbf{s}_1 = (3, 1, 0), \mathbf{s}_2 = (0, 2, 1) and \mathbf{s}_3 = (1, 0, 4). (a) Saanvi wants a batch holding (7, 8, 7) grams. How many liters of each base does she use? (b) Ishani wants (7, 0, 3) grams. Can it be mixed?
Solution(a) With c_1, c_2, c_3 liters the batch holds c_1\mathbf{s}_1 + c_2\mathbf{s}_2 + c_3\mathbf{s}_3 grams, since grams per liter times liters is grams. One equation per pigment, red, yellow, white:
Red gives c_3 = 7 - 3c_1 and yellow gives 2c_2 = 8 - c_1. Doubling the white equation and substituting, (8 - c_1) + 8(7 - 3c_1) = 14, so 64 - 25c_1 = 14 and c_1 = 2. Then c_2 = 3 and c_3 = 1. Check: 2(3, 1, 0) + 3(0, 2, 1) + (1, 0, 4) = (7, 8, 7). Every step was forced, so this is the only recipe.
(b) The same steps with right sides 7, 0, 3 give 2c_2 = -c_1 and -c_1 + 8(7 - 3c_1) = 6, so c_1 = 2, c_2 = -1, c_3 = 1. Check: (6, 2, 0) - (0, 2, 1) + (1, 0, 4) = (7, 0, 3). So (7, 0, 3) is a linear combination of the bases, with one list of weights, but that list calls for -1 liter of \mathbf{s}_2. Paint cannot be taken back out of a mixture, so the batch cannot be mixed. The mathematics allows every weight; the model allows only c_i \geq 0.
Many weights, or none
Let \mathbf{u} = (2, -1) and \mathbf{v} = (-4, 2). Decide whether (a) \mathbf{q} = (6, -3) and (b) \mathbf{r} = (1, 2) are combinations of \mathbf{u} and \mathbf{v}.
SolutionHere \mathbf{v} = -2\mathbf{u}, so by the result on combinations of combinations every combination is a multiple of \mathbf{u}:
All of them lie on the line through \mathbf{0} along \mathbf{u}.
(a) The entries give 2c_1 - 4c_2 = 6 and -c_1 + 2c_2 = -3, both multiples of c_1 - 2c_2 = 3. So c_2 can be any number t, with c_1 = 3 + 2t; for instance \mathbf{q} = 3\mathbf{u} = 5\mathbf{u} + \mathbf{v} = \mathbf{u} - \mathbf{v}. Check the middle one: (10, -5) + (-4, 2) = (6, -3).
(b) The entries give 2c_1 - 4c_2 = 1 and -c_1 + 2c_2 = 2, that is, \displaystyle c_1 - 2c_2 = \frac{1}{2} and c_1 - 2c_2 = -2. Both cannot hold, so \mathbf{r} is not a combination of \mathbf{u} and \mathbf{v}; in the figure it sits off the line.
A vector built from the others
Let \mathbf{v}_1 = (1, 0, 2), \mathbf{v}_2 = (0, 1, -1) and \mathbf{v}_3 = (2, 3, 1). (a) Show that \mathbf{v}_3 is a combination of \mathbf{v}_1 and \mathbf{v}_2, and deduce that every combination of all three is a combination of \mathbf{v}_1 and \mathbf{v}_2 alone. (b) Find every list of weights that writes \mathbf{y} = (3, 2, 4) as c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + c_3\mathbf{v}_3.
Solution(a) The first two entries of a\mathbf{v}_1 + b\mathbf{v}_2 are a and b, so only 2\mathbf{v}_1 + 3\mathbf{v}_2 can equal (2, 3, 1), and its third entry, 2(2) + 3(-1) = 1, matches. So \mathbf{v}_3 = 2\mathbf{v}_1 + 3\mathbf{v}_2, and substituting and collecting as in the Results,
(b) The entries give
Subtracting twice the first equation from the third leaves -c_2 - 3c_3 = -2, the second equation times -1. So the third adds nothing, and c_3 can be any number t:
With t = 0, \mathbf{y} = 3\mathbf{v}_1 + 2\mathbf{v}_2; with t = 1, \mathbf{y} = \mathbf{v}_1 - \mathbf{v}_2 + \mathbf{v}_3. Check: (1, 0, 2) - (0, 1, -1) + (2, 3, 1) = (3, 2, 4). Subtracting the two lists gives weights 2, 3, -1, and 2\mathbf{v}_1 + 3\mathbf{v}_2 - \mathbf{v}_3 = \mathbf{0} is part (a) again: a combination equal to \mathbf{0} with weights not all zero lets the weights shift without moving the result.
Boundaries
- One \mathbb{R}^n, finitely many terms. All vectors in a combination have the same number of entries, and a combination is a finite sum; infinite sums of vectors need limits.
- A model may restrict the weights. Liters of paint cannot be negative, so “can it be mixed” asks for every c_i \geq 0, a stricter question than “is it a combination” (Example 4). Whole-number weights are another restriction: on the grid of Example 3, \mathbf{e}_1 needs fractions.
- The answer belongs to the list, not to \mathbf{b} alone. Adding a vector to the list can turn “no” into “yes” (Exercise 19). Weights, when they exist, may be unique (Examples 2 to 4) or not (Examples 5 and 6); which happens is the subject of Linear independence.
Where this goes next
All the combinations of \mathbf{v}_1, \dots, \mathbf{v}_k form their span: the whole plane in Example 3, a line in Example 5. A list in which no vector is a combination of the others, unlike Example 6, is linearly independent. A matrix times a vector is the combination of the matrix’s columns with the vector’s entries as weights (Multiplying a matrix by a vector), so every linear system asks, as Example 4 did, whether one vector is a combination of others. When each vector of a space is reached exactly once, the weights become coordinates (Coordinates in a basis and change of basis), as x_1, \dots, x_n are the weights on \mathbf{e}_1, \dots, \mathbf{e}_n. Sets closed under combinations are subspaces. The whole area is mapped in Vectors in n dimensions.
Exercises
In Exercises 1 to 4, \mathbf{f} = (1, 3, -2, 0), \mathbf{g} = (2, -1, 0, 4) and \mathbf{h} = (-1, 0, 5, 1).
Computing combinations
- Find 3\mathbf{f} + 2\mathbf{g}.
- Find the combination of \mathbf{f}, \mathbf{g}, \mathbf{h} with weights 1, -1, 1.
- Find \displaystyle \frac{1}{2}\mathbf{g} - 2\mathbf{h}.
- Find the combinations of \mathbf{f}, \mathbf{g}, \mathbf{h} with weights 0, 0, 0 and with weights 0, 1, 0.
- Write (6, -1, 4) as a combination of \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3, and explain why no other weights work.
Solving for weights
In Exercises 6 and 7, \mathbf{m}_1 = (1, 2, -1) and \mathbf{m}_2 = (2, 1, 3). Decide whether the vector is a combination of \mathbf{m}_1 and \mathbf{m}_2, and if so give the weights.
- (1, 5, -6)
- (1, 5, 6)
- Write (a) (7, 4) and (b) (1, -3) as combinations of (3, 1) and (1, 2).
- Decide whether (a) (4, 6) and (b) (4, 5) are combinations of (2, 3) and (-6, -9). Where weights exist, give two different lists.
- With the bases of Example 4, Arnav wants a batch holding (6, 5, 14) grams. How many liters of each base does he use?
- With the same bases, Saanvi wants a batch holding (2, 4, 0) grams. Find the weights, and say whether the batch can be mixed.
- Write (3, 5, 6) as a combination of (1, 0, 1), (1, 1, 0) and (0, 1, 1).
- Find two different lists of weights that write (5, 1, 6) as a combination of (1, 0, 1), (0, 1, 1) and (1, 1, 2). Then show that (5, 1, 4) is not a combination of them.
- Find k so that (1, k, 4) is a combination of (1, 2, 0) and (0, 1, 2).
- If \mathbf{x} = 2\mathbf{u} - \mathbf{v} and \mathbf{y} = \mathbf{u} + 3\mathbf{v}, write 3\mathbf{x} - 2\mathbf{y} as a combination of \mathbf{u} and \mathbf{v}.
- Find the weights that write any (x, y) as a combination of (1, 1) and (1, -1), and use them for (3, 7).
Reasoning
- Without solving for weights, explain why (1, 1, 1) is not a combination of (1, -1, 0) and (0, 1, -1).
- Suppose \mathbf{b} = 2\mathbf{v}_1 - \mathbf{v}_2 and also \mathbf{b} = \mathbf{v}_1 + 3\mathbf{v}_2. Find a combination of \mathbf{v}_1 and \mathbf{v}_2 with weights not both zero that equals \mathbf{0}, and use it to write \mathbf{b} with a third list of weights.
- Give a counterexample to the claim “if \mathbf{b} is a combination of \mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, then it is a combination of \mathbf{v}_1, \mathbf{v}_2.”
- Prove that if \mathbf{u} is a combination of \mathbf{v}_1 and \mathbf{v}_2, then every combination of \mathbf{u}, \mathbf{v}_1, \mathbf{v}_2 is a combination of \mathbf{v}_1 and \mathbf{v}_2.
Answers
- (7, 7, -6, 8). Add 3\mathbf{f} = (3, 9, -6, 0) and 2\mathbf{g} = (4, -2, 0, 8).
- \mathbf{f} - \mathbf{g} + \mathbf{h} = (-2, 4, 3, -3). For example, the third entry is -2 - 0 + 5.
- \displaystyle \left(3, -\frac{1}{2}, -10, 0\right), which is \displaystyle \left(1, -\frac{1}{2}, 0, 2\right) - (-2, 0, 10, 2).
- (0, 0, 0, 0), the zero vector of \mathbb{R}^4, and \mathbf{g} = (2, -1, 0, 4).
- (6, -1, 4) = 6\mathbf{e}_1 - \mathbf{e}_2 + 4\mathbf{e}_3. The i-th entry of c_1\mathbf{e}_1 + c_2\mathbf{e}_2 + c_3\mathbf{e}_3 is c_i, so each weight must equal the matching entry.
- Yes: (1, 5, -6) = 3\mathbf{m}_1 - \mathbf{m}_2. The equations c_1 + 2c_2 = 1 and 2c_1 + c_2 = 5 force c_1 = 3, c_2 = -1, and the third holds: -3 - 3 = -6.
- No. The first two equations again force c_1 = 3, c_2 = -1, and then the third entry is -6 \neq 6.
- (a) (7, 4) = 2(3, 1) + (1, 2) (b) (1, -3) = (3, 1) - 2(1, 2). Solve 3c_1 + c_2 = x, c_1 + 2c_2 = y for each right side.
- (a) Yes: c_1 = 2 + 3t, c_2 = t for any t, such as 2, 0 and 5, 1, since every combination is (c_1 - 3c_2)(2, 3). (b) No: (4, 5) = k(2, 3) needs k = 2 from the first entry, but 3k = 6 \neq 5.
- 1 liter of \mathbf{s}_1, 2 of \mathbf{s}_2 and 3 of \mathbf{s}_3. As in Example 4, c_3 = 6 - 3c_1, 2c_2 = 5 - c_1, and the doubled white equation becomes 53 - 25c_1 = 28.
- \displaystyle c_1 = \frac{4}{5}, \displaystyle c_2 = \frac{8}{5}, \displaystyle c_3 = -\frac{2}{5}, the only weights: the doubled white equation is (4 - c_1) + 8(2 - 3c_1) = 0. The negative weight means the batch cannot be mixed from these bases.
- (3, 5, 6) = 2(1, 0, 1) + (1, 1, 0) + 4(0, 1, 1). Adding c_1 + c_2 = 3, c_2 + c_3 = 5, c_1 + c_3 = 6 gives c_1 + c_2 + c_3 = 7; subtract each equation from it.
- Weights (5 - t, 1 - t, t) for any t, such as 5, 1, 0 and 4, 0, 1: the third equation, c_1 + c_2 + 2c_3 = 6, is the sum of the first two. For (5, 1, 4) the first two still add to 6, but the third demands 4.
- k = 4. The first entry forces c_1 = 1 and the third 2c_2 = 4, so k = 2(1) + 2 = 4.
- 4\mathbf{u} - 9\mathbf{v}, from 6\mathbf{u} - 3\mathbf{v} - 2\mathbf{u} - 6\mathbf{v}.
- \displaystyle c_1 = \frac{x + y}{2} and \displaystyle c_2 = \frac{x - y}{2}, by adding and subtracting c_1 + c_2 = x and c_1 - c_2 = y. So (3, 7) = 5(1, 1) - 2(1, -1).
- Every combination c_1(1, -1, 0) + c_2(0, 1, -1) = (c_1, c_2 - c_1, -c_2) has entries with sum 0, but the entries of (1, 1, 1) have sum 3.
- Subtracting the two expressions for \mathbf{b} gives \mathbf{v}_1 - 4\mathbf{v}_2 = \mathbf{0}. Adding this to the first gives \mathbf{b} = 3\mathbf{v}_1 - 5\mathbf{v}_2.
- In \mathbb{R}^3, \mathbf{e}_3 = 0\mathbf{e}_1 + 0\mathbf{e}_2 + 1\mathbf{e}_3, but every combination of \mathbf{e}_1 and \mathbf{e}_2 has third entry 0.
- Write \mathbf{u} = a_1\mathbf{v}_1 + a_2\mathbf{v}_2. Then c\mathbf{u} + c_1\mathbf{v}_1 + c_2\mathbf{v}_2 = (ca_1 + c_1)\mathbf{v}_1 + (ca_2 + c_2)\mathbf{v}_2, by properties 5 and 7, then 1 and 2, then 6, as in Example 6.