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 2 - Linear Transformations and Matrices

Opening Remarks

Rotations in 2D

  • αRθ(x)=Rθ(αx)\alpha R_{\theta}(x) = R_{\theta}(\alpha x),
  • Rθ(x+y)=Rθ(x)+Rθ(x)R_{\theta}(x+y) = R_{\theta}(x) + R_{\theta}(x)

Linear Transformations

  • A linear transformation is a vector function that has the following two properties:
    • Transforming a scaled vector is the same as scaling the transformed vector: $$L(\alpha x) = \alpha L(x)$$
    • Transforming the sum of two vectors is the same as summing the two transformed vectors: $$L(x + y) = L(x) + L(y)$$
  • Lemma: L:RnRmL: \mathbb{R}^n \to \mathbb{R}^m is a linear transformation if and only if(iff) for all u,vRnu,v \in \mathbb{R}^n and α,βRn\alpha, \beta \in \mathbb{R}^n $$L(\alpha u + \beta v) = \alpha L(u) + \beta L(v)$$
  • Lemma: Let v0,v1,,vk1Rnv_0, v_1, \ldots, v_{k-1} \in \mathbb{R}^n and let L:RnRmL: \mathbb{R}^n \to \mathbb{R}^m be a linear transformation. Then
    • L(v0+v1++vk1)=L(v0)+L(v1)++L(vk1)L(v_0 + v_1 + \ldots + v_{k-1}) = L(v_0) + L(v_1) + \ldots + L(v_{k-1})

Mathematical Induction

  • What is the Principle of Mathematical Induction(week induction)(数学归纳法)?
    • if one can show that:
      • (Base case) a property holds for k=kbk = k_b; and
      • (Inductive step) if it holds for k=Kk = K, where KkbK \ge k_b , then it is also holds for k=K+1k = K +1,
    • then one can conclude that the property holds for all integers kkbk \ge k_b . Often kb=0k_b = 0 or kb=1k_b = 1.
  • Example: To proof: i=0n1i=n(n1)/2\displaystyle\sum_{i=0}^{n-1}{i} = n(n-1)/2
    • Base case: n=1n = 1. For this case, we must show that i=0i1i=1(11)/2\displaystyle\sum_{i=0}^{i-1}{i} = 1(1-1)/2
      • i=0i1i=0=1(11)/2\displaystyle\sum_{i=0}^{i-1}{i} = 0 = 1(1-1)/2
      • So this proves the base case.
    • Inductive step: Inductive Hypothesis (IH): Assume that the result is true for n=kn = k where k1k \ge 1: i=0k1i=k(k1)/2\displaystyle\sum_{i=0}^{k-1}{i} = k(k-1)/2
      • We need to show that the result is then also true for n=k+1n=k+1: i=0(k+1)1i=(k+1)((k+1)1)/2\displaystyle\sum_{i=0}^{(k+1)-1}{i} = (k+1)((k+1)-1)/2
      • Assume that k1k \ge 1, Then
        • i=0(k+1)1i=i=0k1i+k=k(k1)/2+k=k(k+1)/2=(k+1)((k+1)1)/2\begin{aligned}\sum_{i=0}^{(k+1)-1}{i} &= \sum_{i=0}^{k-1}{i} + k \\ &= k(k-1)/2 + k = k(k+1)/2 \\ &= (k+1)((k+1)-1)/2 \end{aligned}

      • This proves the inductive step.

Representing Linear Transformations as Matrices

  • The Big Idea. The linear transformation L is completely described by the vectors
    • a0,a1,...,an1a_0 ,a_1 ,...,a_{n-1}, where aj=L(ej)a_j = L(e_j)
  • because for any vector x, L(x)=j=0n1xjajL(x) = \sum^{n-1}_{j=0} x_j a_j.


  • Let L:RnRmL: \mathbb{R}^n \to \mathbb{R}^m be defined by L(x)=AxL(x) = Ax where ARm×nA \in \mathbb{R}^{m \times n}. Then L is a linear transformation.
  • Alternatively, A vector function f:RnRmf: \mathbb{R}^n \to \mathbb{R}^m is a linear transformation if and only if it can be represented by an m×nm \times n matrix, which is a very special two dimensional array of numbers (elements).
  • The set of all real valued m×nm \times n matrices is denoted by Rm×n\mathbb{R}^{m \times n}

How to check if a vector function is a linear transformation

  • Check if f(0)=0f(0)=0. If it isn’t, it is not a linear transformation.
  • If f(0)=0f(0)=0 then either:
    • Prove it is or isn’t a linear transformation from the definition:
      • Find an example where f(αx)αf(x)f(\alpha x) \ne \alpha f(x) or f(x+y)f(x)+f(y)f(x + y) \ne f(x) + f(y). In this case the function is not a linear transformation; or
      • prove that f(αx)=αf(x)f(\alpha x) = \alpha f(x) or f(x+y)=f(x)+f(y)f(x + y) = f(x) + f(y) for all α,x,y\alpha, x, y.
      • or
    • Compute the possible matrix A that represents it and see if f(x)=Axf(x)=Ax. If it is equal, it is a linear transformation. If it is not, it is not a linear transformation.

Rotations and Reflections, Revisited

Some Summations will be Used in Future Weeks

  • i=0n1i=n(n1)/2n2/2\sum _{i=0}^{n-1} i = n ( n-1 ) / 2 \approx n^2 / 2
  • i=1ni=n(n+1)/2n2/2\sum _{i=1}^{n} i = n ( n+1 ) / 2 \approx n^2 / 2
  • i=0n1i2=(n1)n(2n1)/613n3\sum _{i=0}^{n-1} i^2 = (n-1) n ( 2n-1 ) / 6 \approx \frac{1}{3} n^3


  • arithmetic [ə’riθmətik, ,æriθ’metik] n. 算术,算法