Vectors primer
Vectors Primer
A vector is an ordered finite list of numbers.
Usually we write an $n$-vector as:
\[x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\]or compactly as:
\[x = (x_1, x_2, \ldots, x_n)\]The numbers $x_1, x_2, \ldots, x_n$ are called the entries, components, or coordinates of the vector.
The number of entries is the dimension or length of the vector.
Vector Space
A vector space is a set of objects called vectors where two operations are defined:
- vector addition
- scalar multiplication
For vectors $u, v$ and scalar $\alpha$:
\[u + v\]is another vector, and
\[\alpha v\]is another vector.
The main example in operational research is:
\[\mathbb{R}^n\]the set of all real $n$-vectors.
Vector Addition
If:
\[x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}, \qquad y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}\]then:
\[x + y = \begin{bmatrix} x_1 + y_1 \\ x_2 + y_2 \\ \vdots \\ x_n + y_n \end{bmatrix}\]You add vectors component by component.
Scalar Multiplication
If $\alpha \in \mathbb{R}$ and:
\[x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\]then:
\[\alpha x = \begin{bmatrix} \alpha x_1 \\ \alpha x_2 \\ \vdots \\ \alpha x_n \end{bmatrix}\]You multiply every component by the scalar.
Zero Vector
The zero vector is:
\[0 = (0,0,\ldots,0)\]It satisfies:
\[x + 0 = x\]In operational research, the zero vector often represents choosing nothing, producing nothing, or assigning zero quantity to every decision variable.
Unit Vectors
The standard unit vectors are:
\[e_1 = (1,0,\ldots,0)\] \[e_2 = (0,1,\ldots,0)\]and so on, up to:
\[e_n = (0,0,\ldots,1)\]Each unit vector has one component equal to $1$ and all other components equal to $0$.
For example, in $\mathbb{R}^3$:
\[e_1 = (1,0,0), \qquad e_2 = (0,1,0), \qquad e_3 = (0,0,1)\]Canonical Basis
Every vector in $\mathbb{R}^n$ can be written using unit vectors.
If:
\[x = (x_1,x_2,\ldots,x_n)\]then:
\[x = x_1 e_1 + x_2 e_2 + \cdots + x_n e_n\]The set:
\[\{e_1,e_2,\ldots,e_n\}\]is called the canonical basis or standard basis of $\mathbb{R}^n$.
Vectors as Quantities
In operational research, vectors usually represent quantities.
Example:
\[x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}\]could mean:
- $x_1$ = number of units of product A
- $x_2$ = number of units of product B
- $x_3$ = number of units of product C
A production decision is therefore a vector.
Vectors as Decision Variables
In linear programming, the decision variables are grouped into a vector:
\[x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\]Instead of writing:
\[x_1, x_2, \ldots, x_n\]one by one, we write simply:
\[x\]This makes large problems readable.
Nonnegative Vectors
A vector is nonnegative if every component is nonnegative:
\[x \ge 0\]means:
\[x_1 \ge 0, \quad x_2 \ge 0, \quad \ldots, \quad x_n \ge 0\]In OR this is common because many variables represent physical quantities:
- production amounts
- investment amounts
- transported units
- hours of machine use
- hectares of land
These cannot usually be negative.
Linear Combination
A linear combination of vectors is an expression of the form:
\[\alpha_1 v_1 + \alpha_2 v_2 + \cdots + \alpha_m v_m\]where:
- $v_1,\ldots,v_m$ are vectors
- $\alpha_1,\ldots,\alpha_m$ are scalars
Example:
\[2(1,0) + 1(1,2) - 1(0,2)\]gives:
\[(2,0) + (1,2) - (0,2) = (3,0)\]So $(3,0)$ is a linear combination of $(1,0)$, $(1,2)$, and $(0,2)$.
Convex Combination
A convex combination is a special linear combination:
\[\alpha_1 v_1 + \alpha_2 v_2 + \cdots + \alpha_m v_m\]where:
\[\alpha_i \ge 0\]and:
\[\alpha_1 + \alpha_2 + \cdots + \alpha_m = 1\]For two points $u$ and $v$, every convex combination:
\[\alpha u + (1-\alpha)v, \qquad 0 \le \alpha \le 1\]lies on the line segment between $u$ and $v$.
This matters because feasible regions in linear programming are convex.
Inner Product
The inner product, or dot product, of two vectors is:
\[x^T y = x_1y_1 + x_2y_2 + \cdots + x_ny_n\]The result is a scalar, not a vector.
Example:
\[x = (2,3,4), \qquad y = (5,1,2)\]Then:
\[x^T y = 2 \cdot 5 + 3 \cdot 1 + 4 \cdot 2 = 10 + 3 + 8 = 21\]Objective Function as Inner Product
In linear programming, the objective function is often:
\[c^T x\]where:
\[c = (c_1,c_2,\ldots,c_n)\]is the cost or profit vector.
Then:
\[c^T x = c_1x_1 + c_2x_2 + \cdots + c_nx_n\]Example:
If:
\[c = (5, 12)\]and:
\[x = (6,3)\]then:
\[c^T x = 5 \cdot 6 + 12 \cdot 3 = 66\]So the objective value is $66$.
Price-Quantity Interpretation
If:
\[p = \text{price vector}\]and:
\[q = \text{quantity vector}\]then:
\[p^T q\]is the total cost.
Example:
\[p = (4, 7, 2), \qquad q = (10, 3, 5)\]Then:
\[p^T q = 4 \cdot 10 + 7 \cdot 3 + 2 \cdot 5 = 71\]Linear Dependence
Vectors $v_1,\ldots,v_m$ are linearly dependent if there are scalars, not all zero, such that:
\[\alpha_1v_1 + \alpha_2v_2 + \cdots + \alpha_m v_m = 0\]This means at least one vector can be built from the others.
Linear Independence
Vectors $v_1,\ldots,v_m$ are linearly independent if:
\[\alpha_1v_1 + \alpha_2v_2 + \cdots + \alpha_m v_m = 0\]only when:
\[\alpha_1 = \alpha_2 = \cdots = \alpha_m = 0\]This means none of the vectors is redundant.
Why Independence Matters in OR
In simplex and standard-form linear programming, we select columns of the constraint matrix $A$ to form a basis matrix $B$.
For $B$ to be a valid basis matrix, its columns must be linearly independent.
If the selected columns are dependent, they do not define a valid basic solution.
Quick Example
Consider:
\[v_1 = (1,0), \qquad v_2 = (0,1)\]They are linearly independent because:
\[\alpha_1(1,0) + \alpha_2(0,1) = (0,0)\]implies:
\[\alpha_1 = 0, \qquad \alpha_2 = 0\]Now consider:
\[v_1 = (1,0), \qquad v_2 = (2,0)\]They are linearly dependent because:
\[v_2 = 2v_1\]Sparse Vectors
A sparse vector is a vector with many zero entries.
Example:
\[x = (0,0,5,0,0,2,0)\]Only two entries are nonzero.
The number of nonzero entries is often written as:
\[nnz(x)\]Sparse vectors are important in computational OR because large optimization problems often contain many zeros.
Checklist
You understand vectors if you can:
- identify the dimension of a vector
- add two vectors
- multiply a vector by a scalar
- compute an inner product
- interpret $c^Tx$ as an objective value
- explain what $x \ge 0$ means
- recognize linear combinations
- recognize linear independence
- understand why vectors represent decisions in OR
See Also
- Matrices
- Linear Combinations
- Rank and Linear Independence
- Bases and Invertible Matrices
- Linear Programming
- Standard Form
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.