Show norm preserving property and determine Eigenvalues

Can someone of you give me a solution for this?

Let NN.
a) We define the map F:(CN,||||2)(CN,||||2) by (F(x))k:=1NNj=1xje2πi(j1)(k1)Nk{1,...,N}
Show that F is norm-preserving, i.e. ||(F(x))k||2=||x||2k{1,...,N}
b) For n,m{1,2,...,N} we define the entries of MCN×N by Mnm:={N+12,n=m1e2πimnN1,nm
Show that 1,2,3,...,N are the Eigenvalues of M.


a), Like Omnomnomnom’s opinion, the DFT matrix shows a good guidance. Here, DFT matrix W is defined as below:




This matrix is an orthogonal matrix, and has a property that the calculation WTW shows just an identity matrix. Therefore the mapping can be described by DFT matrix and the following vector:

x_{1} & x_{2} & \cdots & x_{j} & \cdots & x_{N}

so that:

(\mathfrak F(\boldsymbol{x})) =&
(\mathfrak F(x))_{1} &
(\mathfrak F(x))_{2} & \cdots &
(\mathfrak F(x))_{k} & \cdots &
(\mathfrak F(x))_{N}
^{\text{T}}\\[5pt]=& \

This matrix multiplication denotes the Discrete Fourier Transform(DFT) of the signal \boldsymbol{x}. Owing to the above description, the norm-preserving ||(\mathfrak F(x))_k||_2 can be proved as follows:

||(\mathfrak F(x))_k||_2^2 =& \sum_{k=1}^{N} (\mathfrak F(x))_{k}^2 \\=&
(\mathfrak F(\boldsymbol{x}))^{\text{T}}(\mathfrak F(\boldsymbol{x})) \\=&
(\mathsf{W}\boldsymbol{x})^{\text{T}}(\mathsf{W}\boldsymbol{x}) \\=&

b), At first, the matrix \mathsf{M} can be expressed as below:

m_{0} & m_{-1} & m_{-2} & \cdots & m_{1-N} \\
m_{1} & m_{0} & m_{-1} & \cdots & m_{2-N} \\
m_{2} & m_{1} & m_{0} & \cdots & m_{3-N} \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
\vdots & \ddots & m_{k} & \ddots & \vdots \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
m_{N-1} & \cdots & \cdots & \cdots & m_{0}

where k=m-n and:

\cfrac{N-1}{2} & (k=0)\\
\cfrac{1}{\exp\biggl(2\pi i\cfrac{k}{N}\biggr)-1} & (\text{otherwise})

Of course, it is also established as m_{N-k}=m_{-k}. Then, we must be noticed that the matrix of arrangement has a particular pattern. These matrices are called circulant matrix. In generally, circulant matrix has a very interesting and beautiful property that eigenvalues \lambda_{j} can be determined uniquely like follows:


In this case, these eigenvalues are follows:


Source : Link , Question Author : lasik43 , Answer Author : Hayabusananji

Leave a Comment