Transcript bezout identities with inequality constraints

MA5242 Wavelets
Lecture 1 Numbers and Vector Spaces
Wayne M. Lawton
Department of Mathematics
National University of Singapore
2 Science Drive 2
Singapore 117543
Email [email protected]
Tel (65) 6874-2749
Z
Q
R
Numbers
integers, is a ring
rationals, Z p integers modulo a prime, are fields
reals, is a complete field under the topology
induced by the absolute value
| x | x , x  R
2
C
complex numbers, is a complete field under the
topology induced by the absolute value
| x  iy |  x  y , x, y  R
2
2
that is algebraically closed (every polynomial
with coefficients in C has a root in C )
Polar Representation of Complex Numbers
Z – integer, R-real, Q-rational, C-complex
Polar Representation of the Field
i
C
x  iy  re , r  x  y
2
i
e  cos   i sin 
Euler’s Formula
y
2
r

x
Cartesian Geometry
Problem Set 1
1. State the definition of group, ring, field.
2. Give addition & multiplication tables for
Z2 , Z3 , Z4
Determine which are fields?
3. What is a Cauchy Sequence? Why is Q not
complete and why is R complete.
4. Show that R is not algebraically closed.
5. Derive the following:
| uw |  | u | | w |, u, w  C
| u  w |  | u |  | w |, u, w  C
Vector Spaces over a Field
Definition: V is a vector space over a field F if
V is an abelian (commutative) group under addition
a  F , a : V  V 
a ( x  y)  a ( x)  a ( y), x, y V ,
and, for every
this means that
 a is a homomorphism of V into V,
a, b  F , u  V
a  b  a b  a b   ab 1u  u
this means that a   a is a ring homomorphism
Convention: au   a u, a  C , u V
and, for every
d
Examples of Vector Spaces
a positive integer, F a field 
  v1 

  

  v2 

d
F  v 
: v j  F , j  1,..., d 







 vd  with operations 


d
(u  v) j  u j  v j , u, v  F
(au ) j  au j , a  F
is a vector space over the field F
Examples of Vector Spaces
Example 1. The set of functions f : R  R below
f : a,   R  f ( x)  a sin(x   ), x  R
f  exits
Example 3. The subset of Ex. 2 with continuous f 
Example 2. The set of f : R  R such that
Example 4. The subset of Ex. 3 with
f ( x)   f ( x),
xR
Example 5. The set of continuous f : RR that satisfy
f ( x  2 )  f ( x),
xR
Bases
Assume that S is a subset of a vector space V over F
Definition: The linear span of S is the set of all linear
combinations, with coefficients in F, of elements in S
S 

n
c
x
:
x

S
,
c

F
j
j
j
j
j 1
Definition: S is linearly independent if
T  S    T
 S

  S  T 
Definition: S is a basis for V if S is linearly
independent and <S> = V
Problem Set 2
1. Show that the columns of the d x d identity
matrix over F is a basis (the standard basis) of
F
d
2. Show examples 1-5 are vector spaces over R
3. Which examples are subsets of other examples
4. Determine a basis for example 1
5. Prove that any two basis for V either are both
infinite or contain the same (finite) number of
elements. This number is called the dimension of V
Linear Transformations
Definition: If V and W and vector spaces over F
a function L : V W is a linear transformation if
L( x  y )  Lx  Ly, x, y  V
L(ax)  aLx, a  F , x V
Definition: for positive integers m and n define
  m  n matrices over F 
n
m
mn
For every A  F
define LA : F  F
n
by LAu  Au, u  F (matrix-vector product)
F
mn
Problem Set 3
1. Assume that V is a vector space over F and
BV   u1 ,, un

is a basis for V. Then use B to construct a linear
n
transformation from V to F that is 1-to-1
2. If V and W are finite dimensional vector spaces
over a field F with bases
BV   u1 ,, un
 BW   w1 ,, wm 
and L : V  W is a linear transformation, use the
construction in the exercise above and the definitions
in the preceding page to construct an m x n matrix
over F that represents L
Discrete Fourier Transform Matrices
Definition: for positive integers d define  d
1
d
1
1
1
1 
2


2
4
1 






1  d 1  2 d  2
where
 e
2 i / d


1 
d 1 
 

2d 2

 


 

 
Translation and Convolution
Definitions: If X is a set and F is a field, F(X) denotes
the vector space of F-valued functions on X under
pointwise operations. If X is a group and we define
translations  g : F ( X )  F ( X ), g  X
( g f )( x)  f ( g x), f  F ( X ), x  X
1
If X is a finite group we define convolution on F(X)
 f  h ( x)  gX
1
f ( g )h( gx),
f , h  F ( X ), x  X
Remark: in abelian groups we usually write gx as g+x
1
and g as -g
Problem Set 4
d
F (Z d ) is isomorphic to F and
translation by 1 Z d is represented by the matrix
0 0 0  1  2. Show that the
columns
of
the
matrix
1
0
0

0


are eigenvectors

d
C  0 1 0  0 
of multiplication by C
     
2
3. Compute  d
0 0  1 0

T

4. Show that    I where  d   d
d
d
d
5. Derive a relation between convolution and 
d
1. Show that
Problem Set 5
1. Show that the subset Pn of C (R ) defined by
polynomials of degree  n is a vector space over C.
2. Compute the dimension of Pn by showing that its
subset of functions defined by monomials is a basis.
3. Compute the matrix representation for the linear
d
transformation D : Pn  Pn where D  dx
4. Compute the matrix representation for translations
 r : Pn  Pn , ( r f )( x)  f ( x  r )
5. Compute the matrix representation for convolution
by an integrable function f that has compact support.
Hint: the matrix entries depend on the moments of f .