Vectors: Notation, Addition, Scalar Multiplication, and Inner Product

Vectors: Notation and Examples

1. VectorsOutline Notation Examples Addition and scalar multiplication Inner product Complexity Introduction to Applied Linear Algebra Boyd & Vandenberghe

Defining Vectors

1.1Vectors a vector is an ordered list of numbers written as 6 6 6 6 2 -1.1 0.0 3.6 -7.2 3 7 7 7 or . . * . , . -7.2 3.6 + / / / - / or (-1.1,0,3.6,-7.2)

• numbers in the list are the elements (entries, coefficients, components)
• number of elements is the size (dimension, length) of the vector
• vector above has dimension 4; its third entry is 3.6 vector of size n is called an n-vector numbers are called scalars Introduction to Applied Linear Algebra Boyd & Vandenberghe

Vector Symbols and Indexing

1.2

• we'll use symbols to denote vectors, e.g., a, X, p, B, Faut
• other conventions: g, a
• ith element of n-vector a is denoted ai if a is vector above, a3 = 3.6
• in aj, i is the index
• for an n-vector, indexes run from i = 1 to i = n warning: sometimes di refers to the ith vector in a list of vectors
• two vectors a and b of the same size are equal if di = bi for all i
• we overload = and write this as a = b Introduction to Applied Linear Algebra Boyd & Vandenberghe

Block Vectors

1.3Block vectors suppose b, c, and d are vectors with sizes m, n, p the stacked vector or concatenation (of b, c, and d) is a = 6 6 6 4 b d 3 7 7 7 7 5 7

• also called a block vector, with (block) entries b, c, d a has size m + n + p a = (b1,b2, ... ,bm,C1,c2, ... ,Cn,d1,d2, ... ,dp) Introduction to Applied Linear Algebra Boyd & Vandenberghe

Special Vectors: Zero, Ones, and Unit

1.4Zero, ones, and unit vectors n-vector with all entries 0 is denoted On or just 0 n-vector with all entries 1 is denoted 1n or just 1 a unit vector has one entry 1 and all others 0 denoted ej where i is entry that is 1

• unit vectors of length 3: 2 3 2 6 6 e1 = 6 6 6 4 6 6 0 1 0 | 5 7 7 £ , e2 = 6 6 4 6 01 0 7 7 7 5 7 1 , e3 = 6 6 6 6 6 4 0 1 0 3 7 7 7 7 7 5 Introduction to Applied Linear Algebra Boyd & Vandenberghe

Vector Sparsity

1.5Sparsity a vector is sparse if many of its entries are 0 can be stored and manipulated efficiently on a computer nnz(x) is number of entries that are nonzero examples: zero vectors, unit vectors Introduction to Applied Linear Algebra Boyd & Vandenberghe

Vector Applications and Examples

1.6Outline Notation Examples Addition and scalar multiplication Inner product Complexity Introduction to Applied Linear Algebra Boyd & Vandenberghe

2-D and 3-D Location or Displacement

1.7Location or displacement in 2-D or 3-D 2-vector (x1, x2) can represent a location or a displacement in 2-D x X2 x X2 ×1 x1 Introduction to Applied Linear Algebra Boyd & Vandenberghe

Diverse Vector Examples

1.8More examples

• color: (R, G, B)
• quantities of n different commodities (or resources), e.g., bill of materials
• portfolio: entries give shares (or $ value or fraction) held in each of n assets, with negative meaning short positions
• cash flow: xi is payment in period i to us
• audio: xi is the acoustic pressure at sample time i (sample times are spaced 1/44100 seconds apart)
• features: xi is the value of ith feature or attribute of an entity
• customer purchase: xi is the total $ purchase of product i by a customer over some period
• word count: xi is the number of times word i appears in a document Introduction to Applied Linear Algebra Boyd & Vandenberghe

Word Count Vectors

1.9Word count vectors a short document: Word count vectors are used in computer based document analysis. Each entry of the word count vector is the number of times the associated dictionary word appears in the document.

• a small dictionary (left) and word count vector (right) word number the document 2 7 7 7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 6 6 4 5 3 in horse 1 0 4 2 3 2 dictionaries used in practice are much larger Introduction to Applied Linear Algebra Boyd & Vandenberghe

Vector Addition and Scalar Multiplication

1.10Outline Notation Examples Addition and scalar multiplication Inner product Complexity Introduction to Applied Linear Algebra Boyd & Vandenberghe

Vector Addition

1.11Vector addition n-vectors a and b can be added, with sum denoted a + b

• to get sum, add corresponding entries: 0 7 + 2 3 7 6 6 4 2 0 3 5 7 7 7 7 = 6 6 6 2 6 4 6 9 3 3 7 7 7 7 5 7 subtraction is similar Introduction to Applied Linear Algebra Boyd & Vandenberghe

Properties of Vector Addition

1.12 2 6 6 6 6 3 7 5 7 1 1Properties of vector addition

• commutative: a + b = b + a
• associative: (a + b) + c = a + (b+c) (so we can write both as a + b + c)
• a + 0 = 0 + a =a
• a-a= 0 these are easy and boring to verify Introduction to Applied Linear Algebra Boyd & Vandenberghe

Adding Displacements

1.13Adding displacements if 3-vectors a and b are displacements, a + b is the sum displacement b a + b a Introduction to Applied Linear Algebra Boyd & Vandenberghe

Displacement Between Points

1.14Displacement from one point to another displacement from point q to point p is p - q q p-q p Introduction to Applied Linear Algebra Boyd & Vandenberghe

Scalar-Vector Multiplication

1.15Scalar-vector multiplication scalar ß and n-vector a can be multiplied Ba = (Bal, ... , Ban) also denoted aß example: (-2) 6 6 4 9 7 7 7 = 6 5 7 2 -2 3 7 6 6 6 4 -18 6 6 5 -12 7 7 7 7 Introduction to Applied Linear Algebra Boyd & Vandenberghe

Properties of Scalar-Vector Multiplication

1.16 6 6 6 2 1 3 7Properties of scalar-vector multiplication

• associative: (By)a = B(ya)
• left distributive: (B + y)a = Ba + ya
• right distributive: B(a + b) = Ba + ßb these equations look innocent, but be sure you understand them perfectly Introduction to Applied Linear Algebra Boyd & Vandenberghe

Linear Combinations

1.17Linear combinations

• for vectors a1, . . . , am and scalars B1, . . . , Bm, Bia1 + ... + Bmam is a linear combination of the vectors B1, ... , Bm are the coefficients a very important concept a simple identity: for any n-vector b, b = b1e1 + ... + bnen Introduction to Applied Linear Algebra Boyd & Vandenberghe

Linear Combination Example

1.18Example two vectors a1 and a2, and linear combination b = 0.75a1 + 1.5a2 b a2 1.5a2 a1 0.75a1 Introduction to Applied Linear Algebra Boyd & Vandenberghe

Replicating Cash Flow

1.19Replicating a cash flow C1 = (1,-1.1,0) is a $1 loan from period 1 to 2 with 10% interest C2 = (0,1,-1.1) is a $1 loan from period 2 to 3 with 10% interest

• linear combination d= c1 + 1.1c2 = (1,0,-1.21) is a two period loan with 10% compounded interest rate we have replicated a two period loan from two one period loans Introduction to Applied Linear Algebra Boyd & Vandenberghe

Inner Product

1.20Outline Notation Examples Addition and scalar multiplication Inner product Complexity Introduction to Applied Linear Algebra Boyd & Vandenberghe

Inner Product Definition

1.21Inner product inner product (or dot product) of n-vectors a and b is aT b = a1b1 + d2b2 + . . . + anbn other notation used: (a, b), (a|b), (a,b), a · b example: 6 7 6 7 7 4 2 6 6 6 -1 2 3 5 7 7 T 6 6 6 6 4 6 1 -3 0 3 7 7 7 7 5 7 =(-1)(1)+(2)(0)+(2)(-3) =- 7 Introduction to Applied Linear Algebra Boyd & Vandenberghe

Properties of Inner Product

1.22Properties of inner product

• a™b = bTa
• (ya)Tb = y(aTb) (a + b)Tc = aTc + bTc can combine these to get, for example, (a + b)™ (c + d) = aTc+aTd+bTc+bTd Introduction to Applied Linear Algebra Boyd & Vandenberghe

General Inner Product Examples

1.23General examples

• eȚa = ai (picks out ith entry)
• 1Ta = a1 + ... + an (sum of entries)
• aTa = a2 + . . . + a (sum of squares of entries) Introduction to Applied Linear Algebra Boyd & Vandenberghe

Practical Inner Product Examples

1.24Examples

• w is weight vector, f is feature vector; wTf is score
• p is vector of prices, q is vector of quantities; p q is total cost
• c is cash flow, d is discount vector (with interest rate r): d=(1,1/(1 +r), ... , 1/(1 +r)"-1) dT c is net present value (NPV) of cash flow
• s gives portfolio holdings (in shares), p gives asset prices; pTs is total portfolio value Introduction to Applied Linear Algebra Boyd & Vandenberghe

Complexity of Vector Operations

1.25Outline Notation Examples Addition and scalar multiplication Inner product Complexity Introduction to Applied Linear Algebra Boyd & Vandenberghe

Flop Counts

1.26Flop counts computers store (real) numbers in floating-point format basic arithmetic operations (addition, multiplication, ... ) are called floating point operations or flops complexity of an algorithm or operation: total number of flops needed, as function of the input dimension(s)

• this can be very grossly approximated crude approximation of time to execute: (flops needed)/(computer speed) current computers are around 1Gflop/sec (109 flops/sec)
• but this can vary by factor of 100 Introduction to Applied Linear Algebra Boyd & Vandenberghe

Complexity of Vector Addition and Inner Product

1.27Complexity of vector addition, inner product x + y needs n additions, so: n flops

• xTy needs n multiplications, n - 1 additions so: 2n - 1 flops
• we simplify this to 2n (or even n) flops for xTy and much less when x or y is sparse Introduction to Applied Linear Algebra Boyd & Vandenberghe

1.28