Page 382 - Matrix Analysis & Applied Linear Algebra

378 Chapter 5 Norms, Inner Products, and Orthogonality

5.8.8. Awaveform given by a finite sum

x(τ)= (α k cos 2πf k τ + β k sin 2πf k τ)
k
in which the f k ’s are integers and max{f k }≤ 3is sampled at eight
equally spaced points between τ =0 and τ =1. Let
   
x(0/8) 0
 x(1/8)   −5i 
   
 x(2/8)   1 − 3i 
  1  4 
 x(3/8)   
x =   , and suppose that y = F 8 x =   .
 x(4/8)  4  0 
   4 
 x(5/8)   
x(6/8) 1+3i
   
x(7/8) 5i
What is the equation of the waveform?
n
5.8.9. Prove that a b = b a for all a, b ∈C —i.e., convolution is a
commutative operation.
n−1 k th
5.8.10. For p(x)= α k x and the n roots of unity ξ k , let
k=0
T 2 n−1 T
a =( α 0 α 1 α 2 ··· α n−1 ) and p =( p(1) p(ξ) p(ξ ) ··· p(ξ )) .
Explain why F n a = p and a = F −1 p. This says that the discrete
n
Fourier transform allows us to go from the representation of a polynomial
p in terms of its coefficients α k to the representation of p in terms of its
k
values p(ξ ), and the inverse transform takes us in the other direction.
n−1 k n−1 k
5.8.11. Fortwo polynomials p(x)= α k x and q(x)= β k x , let
k=0 k=0
p(1) q(1)
   
p(ξ) q(ξ)
   
p =  .  and q =  .  ,
 .   . 
. .
p(ξ 2n−1 ) q(ξ 2n−1 )
2 2n−1 th
where 1,ξ,ξ ,. .., ξ are now the 2n roots of unity. Explain
why the coefficients in the product
2
p(x)q(x)= γ 0 + γ 1 x + γ 2 x + ··· + γ 2n−2 x 2n−2
must be given by
   
γ 0 p(1)q(1)
 γ 1   p(ξ)q(ξ) 
  = F −1  2 2  .
 γ 2  2n  p(ξ )q(ξ ) 
. .
. .
. .
This says that the product p(x)q(x)is completely determined by the
values of p(x) and q(x)at the 2n th roots of unity.