Shawn Zhong

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Home / 2017 / October / 27

Math 375 – 10/26

  • Oct 27, 2017
  • Shawn
  • Math 375
  • No comments yet
Solving Linear Equations • Trying to solve the equation ○ Ax=y ○ where x∈V is sought, y∈W is given ○ V,W vector spaces ○ T:V→W linear transformation • Example 1 ○ {█(a_11 x_1+a_12 x_2+…+a_1n x_n=y_1@⋮@a_m1 x_1+a_m2 x_2+…+a_mn x_n=y_m )┤ ○ Let § x=(█(x_1@⋮@x_n ))∈Rn § y=(█(y_1@⋮@y_n ))∈Rn § A: Rn→Rn § A(█(x_1@⋮@x_n ))=(█(a_11 x_1+…+a_1n x_n@⋮@a_m1 x_1+…+a_mn x_n )) § A(█(x_1@⋮@x_n ))=(■8(a_11&⋯&a_1n@⋮&⋱&⋮@a_m1&⋯&a_mn ))(█(x_1@⋮@x_n )) § A with respect to standard bases of Rn, Rm ○ Then the linear equations could be represented as § Ax=y • Theorem 1 ○ Statement § If A:V→W is linear § and if u,v∈V are solutions to Ax=y § (i.e. if Au=y, and Av=y) § Then u−v∈N(A) ○ Proof § A(u−v)=Au−Av=y−y=0 ○ Text version § If 〖Ax〗_p=y then for all x∈V with Ax=y § There is an x_ℎ∈N(A) with x=x_p+x_ℎ • Theorem 2 ○ Statement § If u is a solution to Ax=y § and if w∈N(A) § then u+w is also a solution of Ax=y ○ Proof § A(u+w)=Au+Aw=y+0=y ○ Text version § For all x_p with 〖Ax〗_p=y and for all x_ℎ∈N(A) § A(x_p+x_h)=y • General solution ○ Homogeneous equation Ax=0 ○ Inhomogeneous equation § Ax=y, where y≠0 ○ The general solution to Ax=y is of the form § x_gen=x_p+x_ℎ, where § x_p is a particular solution § x_h is the general solution to the homogeneous equation ○ Set of all solutions § {x∈V│Ax=y}={x_p+x_h■8(Ax_p=y@x_hN(A) )} ○ Proof § We are given one solution x_p of Ax=y § If x_ℎ∈N(A) § then by definition 〖Ax〗_ℎ=0 § and hence A(x_p+x_h)=y § ⇒x_p+x_ℎ∈{x∈V│Ax=y} § Conversely if Ax=y then § A(x−x_p )=Ax−Ax_p=y−y=0 § So x_ℎ≝x−x_p∈N(A) • Example 2 ○ Solve the linear equation{█(x_1+2x_2−x_3=7@2x_1−x_2+x_3=4)┤ ○ Setup § V=R3⇒x=(█(x_1@x_2@x_3 )) § W=R2⇒y=(█(7@4)) § A: R3→R2 is matrix multiplication with [■8(1&2&−1@2&−1&1)] ○ Range(A) § ={Ax│x∈R3 } § ={all possible y∈R2 for which Ax=y has a solution} ○ By Rank–nullity theorem § dim⁡〖N(A)+dim⁡〖Range(A)〗=dim⁡〖R3 〗=3〗 dim⁡〖Range(A)〗 dim⁡N(A) 0 3 1 2 2 1 ○ Solving the equation by Gaussian Elimination § [■8(1&2&−1@2&−1&1) │ ■8(7@4)]→[■8(1&0&1/5@0&1&−3/5) │ ■8(3@2)] § {█(x_1+1/5 x_3=3@x_2−3/5 x_3=2)┤ § Let x_3=5c § Then{█(x_2=2+3/5 x_3=2+3c@x_2=3−1/5 x_3=3−c)┤ § Therefore the general solution is § x=[█(3−c@2+3c@5c)]=⏟([█(3@2@0)] )┬(x_p )+c⏟([█(−1@3@5)] )┬(x_h) • Example 3 ○ Given § V=W={functions y:[a,b]→R § A:V→W where Af=f^′+xf ○ Question § Solve dy/dx+xy=x ○ The general solution is in form of § x+x_p+x_ℎ ○ It
Read More >>

Math 375 – 10/19

  • Oct 27, 2017
  • Shawn
  • Math 375
  • No comments yet
Matrix Representation of Linear Transformations • Given ○ Linear Transformation T:V→W ○ Basis for V: {e_1,…,e_n } ○ Basis for W:{f_1,…,f_m } • Let x∈V, y=T(x) then ○ {█(x=x_1 e_1+x_2 e_2+…+x_n e_n@y=y_1 f_1+y_2 f_2+…+y_m f_m )┤ • T(e_k )∈W⇒T(e_k ) is a linear combination of {f_1,…,f_m } i.e. ○ T(e_k )=∑_(i=1)^m▒〖T_ik f_i 〗=T_1k f_1+T_2k f_2+…+T_mk f_m • Suppose we know T_ik (i∈{1,…m},k∈{1,…,n}), then ○ T(x)=T(x_1 e_1+…+x_n e_n ) ○ =x_1 (T_11 f_1+…+T_m1 f_m )+…+x_n (T_1n f_1+…+T_mn f_m ) ○ =(T_11 x_1+…+T_1n x_n ) f_1+…+(T_m1 x_1+…+T_mn x_n ) f_m ○ =y_1 f_1+…+y_m f_m ○ where y_i=T_i1 x_1+…+T_1n x_n ○ Note: T(e_k )=T_1k f_1+T_2k f_2+…+T_mk f_m • The matrix of the linear transformation T:V→W is ○ Mat(T,{e},{f})=[■8(T_11&⋯&T_1n@⋮&⋱&⋮@T_m1&⋯&T_mn )] ○ with respect to the basis {e_1,…,e_n } and {f_1,…,f_m } of V and W • Example ○ V=W=R2 ○ e,f: standard basis for V and W ○ T: rotation by 90° ○ Te_1=0⋅f_1+1⋅f_2 ○ Te_2=(−1)⋅f_1+0⋅f_2 ○ mat(T)=[Te_1,Te_2 ]=[■8(0&−1@1&0)] Matrix Multiplication • Motivation ○ Consider the composition of linear transformations T and S ○ U→┴T V→┴S W ○ basis for U: {e_1,…,e_k } ○ basis for V: {f_1,…,e_l } ○ basis for W: {g_1,…,e_m } ○ mat(ST)=mat(S)⋅mat(T) • Definition ○ A_(m×n) B_(n×q)=[■8(a_11&⋯&a_1n@⋮&⋱&⋮@a_m1&⋯&a_mn )][■8(b_11&⋯&b_1q@⋮&⋱&⋮@b_n1&⋯&b_nq )] ○ =[■8(a_11 b_11+…+a_1n b_n1&⋯&a_11 b_1q+…+a_1n b_nq@⋮&⋱&⋮@a_m1 b_11+…+a_mn b_n1&⋯&a_m1 b_1q+…+a_mn b_nq )]_(m×q) • Example ○ T: rotation by 90° ○ mat(T)=[■8(0&−1@1&0)] ○ {█(T^2 e_1=−f_1=(−1)⋅f_1+0⋅f_2@T^2 e_2=−f_2=0⋅f_1+(−1)⋅f_2 )┤⇒mat(T^2 )=[■8(−1&0@0&−1)] ○ (mat(T))^2=[■8(0&−1@1&0)][■8(0&−1@1&0)]=[■8(−1&0@0&−1)] ○ Therefore mat(T^2 )=(mat(T))^2 VEIR: " either Wilkin Their in E € is + Ten
Read More >>

Math 375 – 10/18

  • Oct 27, 2017
  • Shawn
  • Math 375
  • No comments yet
Theorem • V,W: vector spaces • x_1,…,x_n: basis for V • For any w_1,…,w_n∈W • There is a unique linear map T:V→W • s.t. {█(T(x_1 )=w_1@⋮@T(x_n )=w_n )┤ • v∈W⇒∃c_1,…,c_n∈R • s.t. v=c_1 x_1+…+c_n x_n • T(v)=c_1 w_1+…+c_n w_n • Linear map can be determined only by operations on basis Question 1 • Requirement ○ T: R2→R3 ○ dim⁡(range(T))=1 • Example ○ T(x,y)=(x,0,0) ○ T(x,y)=(0,y,y) ○ T(x,y)=(0,x+3y,−2x−6y) Question 2 • Requirement ○ T: R2→R2 ○ S: R2→R2 ○ ST=−TS • Example ○ T(x,y)=(−y,x) ○ S(x,y)=(−x,y) Question 3 • Requirement ○ T: R3→R3 ○ T^2≠0 ○ T^3≠0 • Example ○ T(x,y,z)=(0,x,y) Question 4 • Requirement ○ T: R2→R2 ○ T maps the unit square to the parallgram below ○ T(0,0)=(0,0) ○ T(1,0)=(2,0) ○ T(0,1)=(1,1) ○ T(1,1)=(3,0) • Example ○ T(x,y)=(2x+y,y) ○ T(x,y)=(2y+x,x) Question 5 • Requirement ○ T: R3→R3 ○ T(x,0,0)=(2x,0,0) ○ T^3 (0,a,b)=(0,a,b) • Example ○ T(x,y,z)=(2x,y,z) Question 6 • Requirement ○ T: R2→R2 ○ T(1,0)=(1,0) ○ {(x,y),T(x,y)} is independent whenever y≠0 • Example ○ T(x,y)=(x+y,y) Question 7 • Requirement ○ T: R2→R3 ○ T is injective ○ dim⁡(range(T))=1 • Example ○ Impossible " t • --- .... ice (1.1) T (1.1) (3.1) I _ _ _ _ _ " - _ ~) > > (2.0)
Read More >>

Math 375 – 10/17

  • Oct 27, 2017
  • Shawn
  • Math 375
  • No comments yet
Examples of Linear Transformations • Example 1 ○ V={all polynomials} ○ Consider D:V→V defined by § Given f∈V § Df=g if g(x)=f′(x) § e.g. D(1+x−3x^2 )=1−6x ○ Null Space § Null(D)={f∈V│Df=0} § ={f∈V│f^′ (x)=0} § ={f∈V│f is constant function} § ={f(x)=c│c∈R} § dim⁡Null(D)=1 § Basis for Null(D)={1} • Example 2 ○ V={all polynomials} ○ K:V→V ○ Kf=g⟺g(x)=∫_0^x▒f(s)ds ○ e.g. K(x^2+3)=∫_0^x▒f(s^2+3)ds=[s^2/3+3s]_0^x=1/3 x^3+3x Addition and Scalar Multiplication of Linear Transformations • Addition ○ V,W: vector spaces ○ T,S: V→W: linear transformations ○ T+S is the map V→W with (T+S)(x)=Tx+Sx • Example ○ V=W=R2 ○ T= rotation by 45° counter-clockwise ○ S= reflection in the y-axis ○ T+S=? • Theroem ○ Statement § If T,S:V→W is linear, so are (T+S) ○ Proof: closed under addition § (T+S)(x+y) § =T(x+y)+S(x+y) § =Tx+Ty+Sx+Sy § =(Tx+Sx)+(Ty+Sy) § =(T+S)(x)+(T+S)(y) ○ Proof: closed under scalar multiplication § (T+S)(cx) § =T(cx)+S(cx) § =c⋅T(x)+c⋅S(x) § =c[T(x)+S(x)] § =c(T+S)(x) • Scalar Multiplication ○ V,W: vector spaces ○ T,S: V→W: linear transformations ○ cT:V→W (c∈R is defined by ○ (cT)(x)=c(Tx), ∀x∈V • Theorem ○ Let V,W be two vector spaces ○ L(V,W)={all linear transformation from V to W} ○ Then L(V,W) is a vector space ○ e.g. T,S∈L(V,W)⇒c_1 T+c_2 S∈L(V,W), ∀c_1,c_2∈R Multiplication/Composition of Linear Transformations • Definition ○ U,V,W: vector spaces ○ T:U→V, S:V→W ○ Then ST:V→W is given by (ST)(x)=S(Tx) • Theorem ○ If S,T_1,T_2 is linear, then S(T_1+T_2 )=ST_1+ST_2 • Example ○ Given § V={all polynomials} § D,K:V→V § Df=f^′, (Kf)(x)=∫_0^x▒f(s)ds ○ DKf=? § Let g=Kf=∫_0^x▒f(s)ds § D(g(x))=d/dx g(x)=d/dx ∫_0^x▒f(s)ds=f(x) § Therefore DKf=f ○ KDf=? § KDf=∫_0^x▒(Df)(s)ds=∫_0^x▒〖f^′ (s)ds〗=f(x)−f(0) § Therefore KDf≠f Injective and Inverse • Injective ○ T is injective if and only if N(T)={0} ○ If T:V→W is injective then ○ Tx=y has exactly one solution for every y∈Range(T) ○ (Range(T)={Tx│x∈V}, "exactly one" because T is injective) • Inverse ○ T^(−1):Range(T)→V is given by ○ T^(−1) (y)=x, if y=Tx • Example ○ Given § V=R2, W=R2 § T:V→W § Tx=(x,x) ○ Whether T is inversable? § Tx=0⇒x=0⇒N(T)={0} § Range(T)={(x,x)│x∈R={(x,y)∈R2│x=y} § T^(−1):Range(T)→R § T^(−1) (x,x)=x • Theorem ○ Statement § T^(−1):Range(T)→V is linear § ⟺{█(T^(−1) (u+v)=T^(−1) (u)+T^(−1) (v)@T^(−1) (c⋅u)=c⋅T^(−1) (u)@∀u,v∈Range(T), c∈R┤ ○ Proof § If u∈Range(T) then there is an x∈V with u=Tx § By definition of T^(−1), x=T^(−1) (u) § Similarly, there is y∈V with v=Ty, and y=T^(−1) (u) § T(x+y)=Tx+Ty=u+v § ⇒u+v∈Range(T) § ⇒x+y=T^(−1) (u+v) • Theorem ○ Statement § Suppose V is a finite-dimensional linear space § T:V→V is injective, then § Range(T)=V ○ Proof § Rank–Nullity Theorem says that § dim⁡Null(T)+rank(T)=dim⁡V § T is injective ⇒Null(T)={0}⇒dim⁡Null(T)=0 § Therefore dim⁡Range(T)=dim⁡V § Also, Range(T) is a sunspace of V § ⇒Range(T)=V • Theorem ○ Suppose V is a finite-dimensional linear space ○ T:V→V is injective, then ○ Tx=y has a unique solution for every y∈V • Example ○ Given § V={all polynomials} § D,K:V→V § Df=f^′, (Kf)(x)=∫_0^x▒f(s)ds ○ Is K injective? § We have proven DKf=f § Suppose Kf=0, then D(Kf)=0 § But f=DKf, so f=0 § ⇒K is injective ○ Is K surjective? § Suppose K is surjective then § Given g∈V, we can solve Kf=g with f∈W § i.e. given g∈V, there is one f with § ∫_0^x▒f(s)ds=1, ∀x∈R § At x=0, we have § ∫_0^0▒f(s)ds=1 § Which makes a contradiction, therefore K is not surjective
Read More >>

Math 375 – Midterm 1 Practice

  • Oct 27, 2017
  • Shawn
  • Math 375
  • No comments yet
Read More >>

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 – Discrete Math
    • Math 375 – Linear Algebra
    • Math 431 – Intro to Probability
    • Math 514 – Numerical Analysis
    • Math 521 – Analysis I
    • Math 541 – Abstract Algebra
    • Math 632 – Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 – Intro to Computer Engr.
    • CS/ECE 352 – Digital System Fund.
    • Learn Haskell
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E&M
    • AP Physics C: Mechanics
    • CLEP Psychology
  • 2048 Game
  • HiMCM 2016
  • 登峰杯 MCM

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E&M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (2)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP