Linear combinations
Linear Combinations
A linear combination is a vector built by multiplying vectors by scalars and adding the results.
If:
\[v_1, v_2, \ldots, v_m\]are vectors, and:
\[\alpha_1, \alpha_2, \ldots, \alpha_m\]are scalars, then:
\[\alpha_1v_1 + \alpha_2v_2 + \cdots + \alpha_m v_m\]is a linear combination of the vectors $v_1,\ldots,v_m$.
The numbers $\alpha_1,\ldots,\alpha_m$ are called the coefficients of the linear combination.
Example
Let:
\[v_1 = (1,0), \qquad v_2 = (1,2), \qquad v_3 = (0,2)\]and:
\[\alpha_1 = 2, \qquad \alpha_2 = 1, \qquad \alpha_3 = -1\]Then:
\[2v_1 + v_2 - v_3 = 2(1,0) + (1,2) - (0,2)\] \[= (2,0) + (1,2) - (0,2)\] \[= (3,0)\]So $(3,0)$ is a linear combination of $v_1,v_2,v_3$.
Linear Combination of Unit Vectors
The standard unit vectors in $\mathbb{R}^n$ are:
\[e_1 = (1,0,\ldots,0)\] \[e_2 = (0,1,\ldots,0)\] \[\ldots\] \[e_n = (0,0,\ldots,1)\]Every vector:
\[v = (v_1,v_2,\ldots,v_n)\]can be written as:
\[v = v_1e_1 + v_2e_2 + \cdots + v_ne_n\]Example:
\[(4,7,2) = 4(1,0,0) + 7(0,1,0) + 2(0,0,1)\]Span
The span of a set of vectors is the set of all possible linear combinations of those vectors.
If:
\[S = \{v_1,v_2,\ldots,v_m\}\]then:
\[\operatorname{span}(S) = \{\alpha_1v_1+\alpha_2v_2+\cdots+\alpha_mv_m \mid \alpha_i \in \mathbb{R}\}\]Informally:
The span is everything you can build from the given vectors.
Example of Span in $\mathbb{R}^2$
Let:
\[v_1 = (1,0), \qquad v_2 = (0,1)\]Then every vector $(a,b)$ can be written as:
\[(a,b) = a(1,0) + b(0,1)\]So:
\[\operatorname{span}\{(1,0),(0,1)\} = \mathbb{R}^2\]Linear Systems as Linear Combinations
A linear system:
\[Ax = b\]can be understood using the columns of $A$.
Let:
\[A = [A_1 \ A_2 \ \cdots \ A_n]\]where $A_1,\ldots,A_n$ are the columns of $A$.
Then:
\[Ax = b\]means:
\[x_1A_1 + x_2A_2 + \cdots + x_nA_n = b\]So solving $Ax=b$ means:
Find coefficients $x_1,\ldots,x_n$ such that $b$ is a linear combination of the columns of $A$.
OR Meaning
In operational research, linear combinations appear everywhere.
For example, suppose:
\[x_1 = \text{units of product A}\] \[x_2 = \text{units of product B}\]and the resource use per unit is:
\[A_1 = \begin{bmatrix} 2 \\ 5 \end{bmatrix}, \qquad A_2 = \begin{bmatrix} 3 \\ 1 \end{bmatrix}\]Then total resource use is:
\[x_1A_1 + x_2A_2\]That is:
\[x_1 \begin{bmatrix} 2 \\ 5 \end{bmatrix} + x_2 \begin{bmatrix} 3 \\ 1 \end{bmatrix} = \begin{bmatrix} 2x_1 + 3x_2 \\ 5x_1 + x_2 \end{bmatrix}\]Convex Combination
A convex combination is a special linear combination where:
\[\alpha_i \ge 0\]and:
\[\alpha_1 + \alpha_2 + \cdots + \alpha_m = 1\]So:
\[\alpha_1v_1 + \alpha_2v_2 + \cdots + \alpha_mv_m\]is a convex combination if all coefficients are nonnegative and sum to $1$.
Convex Combination of Two Points
For two vectors $u$ and $v$, every vector of the form:
\[\alpha u + (1-\alpha)v\]where:
\[0 \le \alpha \le 1\]lies on the line segment between $u$ and $v$.
Example:
\[u = (0,0), \qquad v = (4,2)\]For $\alpha = \frac{1}{2}$:
\[\frac{1}{2}(0,0) + \frac{1}{2}(4,2) = (2,1)\]This is the midpoint of the segment.
Why Convex Combinations Matter
Feasible regions in linear programming are convex.
This means:
If $x$ and $y$ are feasible, then every convex combination:
\[\alpha x + (1-\alpha)y\]with:
\[0 \le \alpha \le 1\]is also feasible.
This is why linear programming has such clean geometry.
Sum and Average as Special Linear Combinations
Given vectors:
\[v_1,\ldots,v_m\]their sum is:
\[v_1 + v_2 + \cdots + v_m\]This is a linear combination where every coefficient is $1$.
Their average is:
\[\frac{1}{m}v_1 + \frac{1}{m}v_2 + \cdots + \frac{1}{m}v_m\]This is also a convex combination.
In Simplex
In standard form:
\[Ax=b,\qquad x\ge 0\]the equation:
\[Ax=b\]means that $b$ must be represented as a nonnegative linear combination of columns of $A$:
\[x_1A_1 + x_2A_2 + \cdots + x_nA_n = b\]A basic solution chooses a small set of columns and tries to represent $b$ using only those columns.
Checklist
You understand linear combinations if you can:
- identify the vectors
- identify the coefficients
- compute the resulting vector
- explain span
- rewrite $Ax=b$ as a linear combination of columns
- explain why convex combinations lie between points
- connect linear combinations to feasible solutions in LP
See Also
- Vectors
- Matrices
- Linear Systems
- Rank and Linear Independence
- Bases and Invertible Matrices
- Polyhedra
Exam checkpoint
Use this topic only as much as needed to support LP algebra: matrices, rank, bases, linear systems, half-spaces, and hyperplanes. Connect every computation back to $Ax=b$, basis matrices, and feasible regions.