1
$\begingroup$

I was reading a paper about DFT, at the end he got the relations $Y=\frac{1}{\sqrt N}W_n \cdot y$ and $y=\frac{1}{\sqrt N}W_n \cdot Y$, where $y$ is a vector and $Y$ is the coordinates of that vector in the basis. $W_n$ stands for the transformation matrix. Later, the author shows how to reduce the following into smaller matrices but I don't really understand what is he doing nor how is he doing it.

\begin{align*} W_4 \begin{bmatrix} y_0\\y_1\\y_2\\y_3 \end{bmatrix} &= \begin{bmatrix} \begin{bmatrix} 1&1\\1&\omega^2 \end{bmatrix} \begin{bmatrix} y_0\\y_2 \end{bmatrix} +\begin{bmatrix} 1&1\\\omega&\omega^3 \end{bmatrix} \begin{bmatrix} y_1\\y_3 \end{bmatrix} \\ \begin{bmatrix} 1&\omega^4\\1&\omega^6 \end{bmatrix} \begin{bmatrix} y_0\\y_2 \end{bmatrix} +\begin{bmatrix} \omega^2&\omega^6\\\omega^3&\omega^9 \end{bmatrix} \begin{bmatrix} y_1\\y_3 \end{bmatrix} \end{bmatrix} \\ &= \begin{bmatrix} \begin{bmatrix} 1&1\\1&\omega^2 \end{bmatrix} \begin{bmatrix} y_0\\y_2 \end{bmatrix} +\begin{bmatrix} 1\\&\omega \end{bmatrix} \begin{bmatrix} 1&1\\1&\omega^2 \end{bmatrix} \begin{bmatrix} y_1\\y_3 \end{bmatrix} \\ \begin{bmatrix} 1&1\\1&\omega^2 \end{bmatrix} \begin{bmatrix} y_0\\y_2 \end{bmatrix} -\begin{bmatrix} 1\\&\omega \end{bmatrix} \begin{bmatrix} 1&1\\1&\omega^2 \end{bmatrix} \begin{bmatrix} y_1\\y_3 \end{bmatrix} \end{bmatrix} \end{align*}

$\endgroup$
1
$\begingroup$

In the first step, the author is just exploiting some associativity of the matrix-vector product. For instance, the first two rows of $W_4y$ are: \begin{align*} \begin{bmatrix} 1&1&1&1\\ 1&\omega&\omega^2&\omega^3 \end{bmatrix} \begin{bmatrix} y_0\\y_1\\y_2\\y_3 \end{bmatrix} &= \begin{bmatrix} y_0+y_1+y_2+y_3\\ y_0+\omega y_1+\omega^2y_2+\omega^3y_3 \end{bmatrix} \\ &= \begin{bmatrix} (y_0+y_2)+(y_1+y_3)\\ (y_0+\omega^2y_2)+(\omega y_1+\omega^3y_3) \end{bmatrix} \\ &= \begin{bmatrix} y_0+y_2\\ y_0+\omega^2y_2 \end{bmatrix} + \begin{bmatrix} y_1+y_3\\ \omega y_1+\omega^3y_3 \end{bmatrix} \\ &= \begin{bmatrix} 1&1\\1&\omega^2 \end{bmatrix} \begin{bmatrix} y_0\\y_2 \end{bmatrix} +\begin{bmatrix} 1&1\\\omega&\omega^3 \end{bmatrix} \begin{bmatrix} y_1\\y_3 \end{bmatrix}. \end{align*}

$\endgroup$
  • $\begingroup$ Oh ok, now i get it thanks. i will continue by myself from here $\endgroup$ – Alejandro Duque Dec 25 '18 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.