Page 384 - Matrix Analysis & Applied Linear Algebra

380 Chapter 5 Norms, Inner Products, and Orthogonality

5.8.13. Fora nonsingular circulant C n×n , explain how to use the FFT algo-
rithm to efficiently perform the following operations.
(a) Solve a system Cx = b.
(b) Compute C −1 .
(c) Multiply two circulants C 1 C 2 .

5.8.14. For the vectors
   
α 0 β 0
. .
   
α 0 β 0  . .   . . 
   
   
ˆ
 α 1   β 1 
 α n−1 
a=  .  , b=  .  , ˆ a= , and b= ,
 β n−1 
 .   .  0
. .    0 
 .   . 
α n−1 β n−1  . .   . . 
0 0
2n×1 2n×1
let C be the 2n × 2n circulant matrix (see Exercise 5.8.12) whose first
column is ˆ a.
(a) Show that the convolution operation can be described as a
matrix–vector product by demonstrating that
ˆ
a b = Cb.
(b) Use this relationship to give an alternate proof of the convolu-
tion theorem. Hint: Use the diagonalization result of Exercise
5.8.12 together with the result of Exercise 5.8.10.

5.8.15. The Kronecker product of two matrices A m×n and B p×q is defined
to be the mp × nq matrix

 
a 11 B a 12 B ··· a 1n B
 a 21 B a 22 B ··· a 2n B 
A ⊗ B =  . . . .  .
. . . .
 . . . . 
a m1 B a m2 B ··· a mn B
This is also known as the tensor product or the direct product. Al-
though there is an extensive list of properties that the tensor product
satisfies, this exercise requires only the following two elementary facts
(which you need not prove unless you feel up to it). The complete list of
properties is given in Exercise 7.8.11 (p. 597) along with remarks about
Kronecker, and another application appears in Exercise 7.6.10 (p. 573).
A ⊗ (B ⊗ C)=(A ⊗ B) ⊗ C.
(A⊗B)(C⊗D)= AC⊗BD (if AC and BD exist).