13.21. EXERCISES 385

Here is one way to approach this problem. Note z =Ux where U =

1√n



e−i 2πn 0·0 e−i 2π

n 1·0 e−i 2πn 2·0 · · · e−i 2π

n (n−1)·0

e−i 2πn 0·1 e−i 2π

n 1·1 e−i 2πn 2·1 · · · e−i 2π

n (n−1)·1

e−i 2πn 0·2 e−i 2π

n 1·2 e−i 2πn 2·2 · · · e−i 2π

n (n−1)·2

......

......

e−i 2πn 0·(n−1) e−i 2π

n 1·(n−1) e−i 2πn 2·(n−1) · · · e−i 2π

n (n−1)·(n−1)

Now argue U is unitary and use this to establish the result. To show this verifyeach row has length 1 and the inner product of two different rows gives 0. NowUk j = e−i 2π

n jk and so (U∗)k j = ei 2πn jk.

16. Let f be a periodic function having period 2π . The Fourier series of f is an expres-sion of the form

∞

∑k=−∞

ckeikx ≡ limn→∞

n

∑k=−n

ckeikx

and the idea is to find ck such that the above sequence converges in some way to f .If

f (x) =∞

∑k=−∞

ckeikx

and you formally multiply both sides by e−imx and then integrate from 0 to 2π, in-terchanging the integral with the sum without any concern for whether this makessense, show it is reasonable from this to expect

cm =1

2π

∫ 2π

0f (x)e−imxdx.

Now suppose you only know f (x) at equally spaced points 2π j/n for j = 0,1, · · · ,n.Consider the Riemann sum for this integral obtained from using the left endpoint ofthe subintervals determined from the partition

{ 2π

n j}n

j=0. How does this comparewith the discrete Fourier transform? What happens as n→ ∞ to this approximation?

17. Suppose A is a real 3× 3 orthogonal matrix (Recall this means AAT = AT A = I. )having determinant 1. Show it must have an eigenvalue equal to 1. Note this showsthere exists a vector x ̸= 0 such that Ax= x. Hint: Show first or recall that anyorthogonal matrix must preserve lengths. That is, |Ax|= |x| .

18. Let A be a complex m×n matrix. Using the description of the Moore Penrose inversein terms of the singular value decomposition, show that

limδ→0+

(A∗A+δ I)−1 A∗ = A+

where the convergence happens in the Frobenius norm. Also verify, using the singu-lar value decomposition, that the inverse exists in the above formula. Observe thatthis shows that the Moore Penrose inverse is unique.

19. Show that A+ = (A∗A)+ A∗. Hint: You might use the description of A+ in terms ofthe singular value decomposition.