Introduction to Probability

Multivariable Calculus

Algorithms: Part II

Algorithms: Part I

Introduction to Software Design and Architecture

Calculus Two: Sequences and Series

LAFF Linear Algebra

Stanford Machine Learning

Calculus One

Computational Thinking

Effective Thinking Through Mathematics

CS50 Introduction to Computer Science


Week 1 - Vectors in Linear Algebra

What is Vector?


  • A two-dimensional vector:
  • Vector in higher dimensions:
    • x=(x0x1xn1)x = \begin{pmatrix} x_0 \\ x_1 \\ \vdots \\ x_{n-1} \end{pmatrix}
      • It is an ordered array.
      • The entries in the array are called components.
      • We start indexing the components at zero.
      • The component indexed with i is denoted by xix_i.
      • Each number is a real number: xiRx_i \in \mathbb{R}.
      • xRnx \in \mathbb{R}^n
      • A vector has a direction and a length.
        • Draw an arrow from the origin to the point(x0,x1,,xn1)(x_0,x_1,\ldots,x_{n-1}).
        • The length is x02+x12++xn12\sqrt{x_0^2+x_1^2+\ldots+x_{n-1}^2}.
        • A vector does not have a location.
  • Summary
    • A vector has a direction and a length.
    • We will write it as a column of values which we call a (column) vector.

Unit Basis Vectors (Standard Basis Vectors)

  • An important set of vectors is the set of unit basis vectors given by
    • Where the “1” appears as the component indexed by j. Thus, we get the set {e0,e1,,en1}Rn\{e_0,e_1,\ldots,e_{n-1}\} \subset \mathbb{R}^n given by
  • Different with unit vector, which is any vector of length one (unit length). For example, the vector (2222)\begin{pmatrix}\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2}\end{pmatrix} has length one.

Simple Vector Operations

Equality (=), Assignment (:=), and Copy

  • Two vectors x,yRnx,y \in \mathbb{R}^n are equal if all their components are element-wise equal: $$x=y\ \text{if and only if}\ x_i = \psi_i, \text{for all}\ 0 \le i < n$$
  • operation y := x:

Vector Addition(ADD), Scaling(SCAL), Subtraction

  • Addition and Subtraction
  • Scaling

Advanced Vector Operations

Scaled Vector Addition (AXPY)

  • axpy: αx+y\alpha x + y
  • The AXPY operation requires 3n + 1 memops(memory operations) and 2n flops(floating point operations). The reason is that α\alpha is only brought in from memory once and kept in a register for reuse.
    • 3n+1: x, ax, y, a
    • 2n: ax, ax+y

Dot or Inner Product (DOT)

Vector Length(NORM2)

  • Let xRnx \in \mathbb{R}^n. Then the (Euclidean) length of a vector x (the two-norm) is given by
    • x2=x02+x12++xn12=i=0n1xi2\lVert x \rVert _2 = \sqrt{x_0^2+x_1^2+\ldots+x_{n-1}^2} = \sqrt{\sum_{i=0}^{n-1}{}x_i^2}

    • Here x2\lVert x \rVert _2 notation stands for “the two norm of x”, which is another way of saying “the length of x”.

Cauchy-Schwarz inequality

  • Let x,yRnx, y \in R^n, then xyxy|x y| \le \lVert x \rVert \lVert y \rVert
  • And xy=xy|x y| = \lVert x \rVert \lVert y \rVert, iff x=cy,cRx = cy, c \in \mathbb{R}.
  • Proof:
    • Let’s Define P(t)=tyx2P(t) = \lVert t y - x \rVert ^2
    • P(t)=(tyx)(tyx)0P(t) = (t y - x) \cdot (t y - x) \ge 0
    • P(t)=(yy)t22(xy)t+xx0P(t) = (y \cdot y)t^2 - 2 ( x \cdot y) t + x \cdot x \ge 0
    • Set a=yy,b=2(xy),c=xxa = y \cdot y, b = 2( x \cdot y ) , c = x \cdot x
    • P(t)=at2bt+c0P(t) = a t^2 - b t + c \ge 0
    • Set t=b2at = \frac{b}{2a}
    • P(t)=ab2a2bb2a+c0P(t) = a \frac{b}{2a}^2 - b \frac{b}{2a} + c \ge 0 => 4acb24ac \ge b^2
    • 4y2x2(2(xy)24 \lVert y \rVert ^2 \lVert x \rVert ^2 \ge (2 ( x \cdot y)^2 => yxxy\lVert y \rVert \lVert x \rVert \ge | x \cdot y |

Vector Functions

  • Sample:

Vector Functions that Map a Vector to a Vector

  • f:RnRmf: \mathbb{R}^n \to \mathbb{R}^m
  • Sample:


The Greek Alphabet

  • Lowercase Greek letters (α, β, etc.) are used for scalars.
  • Lowercase (Roman) letters (a, b, etc) are used for vectors.
  • Uppercase (Roman) letters (A, B, etc) are used for matrices.
  • The Alphabet

Other Norms

  • A norm is a function, in our case of a vector in Rn\mathbb{R}^n, that maps every vector to a nonnegative real number. The simplest example is the absolute value of a real number: Given αR\alpha \in \mathbb{R}, the absolute value of α, often written as |α|, equals the magnitude of α:
    • α={αif α0,αotherwise.\lvert \alpha \rvert = \left\{ \begin{array}{rl} \alpha & \text{if } \alpha \ge 0,\\ -\alpha & \text{otherwise}. \end{array} \right.

  • Similarly, one can find functions, called norms, that measure the magnitude of vectors. One example is the (Euclidean) length of a vector, which we call the 2-norm: for xRnx \in \mathbb{R}^n,
    • x2=i=0n1xi2\lVert x \rVert _2 = \sqrt{\sum_{i=0}^{n-1}x_i^2}

  • Other norms:
    • 1-norm (also called taxi-cab norm):
      • x1=i=0n1xi\lVert x \rVert _1 = \sqrt{\sum_{i=0}^{n-1}|x_i|}

    • For 1p1 \le p \le \infty, the p-norm:
      • xp=i=0n1xipp\lVert x \rVert _p = \sqrt[p]{\sum_{i=0}^{n-1}|x_i|^p}

Summary of the Properties for Vector Operations

Vector Addition

  • Is commutative. That is, for all vectors x,yRn,x+y=y+x.x,y\in \mathbb R^n, x+y=y+x..
  • Is associative. That is, for all vectors x,y,zRn,(x+y)+z=x+(y+z)x,y,z\in \mathbb R^n, (x+y)+z=x+(y+z).
  • Has the zero vector as an identity. For all vectors xRn,x+0=0+x=xx \in \mathbb R^n, x+\mathbf 0=\mathbf0+x=x where 0 is the vector of size n with 0 for each component.
  • Has an inverse, −x. That is x+(x)=0x+(-x)=\mathbf 0.

The dot product of vectors

  • Is commutative. That is, for all vectors x,yRn,xTy=yTxx,y\in R^n,x^Ty = y^Tx.
  • Distributes over vector addition. That is, for all vectors x,y,zRn,xT(y+z)=xTy+xTzx,y,z\in R^n,x^T(y+z)=x^Ty+x^Tz. Also, (x+y)Tz=xTz+yTz(x+y)^Tz=x^Tz+y^Tz.

Other Properties

  • For x,yRn,(x+y)T(x+y)=xTx+2xTy+yTyx,y \in R^n, (x+y)^T(x+y)=x^Tx+2x^Ty+y^Ty.
  • For x,yRn,xTy=0x,y \in R^n, x^Ty=0 if and only if x and y are orthogonal.
  • Let x,yRnx,y \in R^n be nonzero vectors and let the angle between them equal θ. Then cos(θ)=xTyx2y2\cos(\theta) = \frac{x^Ty}{||x||_2||y||_2}.
  • For xRn,xTei=eiTx=χix \in R^n, x^Te_i=e_i^Tx=\chi_i where χi\chi_i equals the ith component of x.