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.

Answer

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

W=1N[ω1,1ω2,1ω3,1ωN,1ω1,2ω2,2ω3,2ωN,2ωj,kω1,NωN,N]

where,

ωj,k=exp(2πi(j1)(k1)N).

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:


\boldsymbol{x}=
\begin{bmatrix}
x_{1} & x_{2} & \cdots & x_{j} & \cdots & x_{N}
\end{bmatrix}
^{\text{T}}

so that:


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

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:


\begin{aligned}
||(\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}) \\=&
\|\boldsymbol{x}\|_{2}^2
\end{aligned}


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


\mathsf{M}=
\begin{bmatrix}
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}
\end{bmatrix}

where k=m-n and:


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

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:


\begin{aligned}
\lambda_{j}=m_{0}+
\sum_{k=1}^{N-1}m_{-k}\omega_{j,k}
\end{aligned}

In this case, these eigenvalues are follows:


\begin{aligned}
\lambda_{j}=
\cfrac{N-1}{2}+
\sum_{k=1}^{N-1}\cfrac{\omega_{j,k+1}}{1-\omega_{1,k}}
\end{aligned}

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

Leave a Comment