I am studying a paper which describes split-radix algorithms by making matrix factorizations, so that e.g. DCT 8x8 can be computed via 4 DCT4x4.
I must apologize, but the question is related to an article, which is located here: http://duepublico.uni-duisburg-essen.de/servlets/DerivateServlet/Derivate-5235/mathe4.pdf
On the page5 there is a Lemma 2.2 which, basically, says that DCTnxn can be computed via sevelar DCTmxm where m = n/2 for even n (see equation 2.4). They use Pn matrix here, which transforms vector column {x0, x1, x2, ....., xn-1} into { x0, x2, x4, x6,.., xn-2, x1, x3, ...,xn-1 }. For such transform it is easy to imagine how Pn looks.
But later they give a proof, and the first equation in a proof uses Pn. But I cannot understand how should this Pn matrix look, so that it will have such effect on another matrix CnII (last equation at page 5).
Here I copied those matrices, in case link will not work.
Its effect is as follows (splitting odd end even): Suppose we have DCT-II described by:
$ C_n^{II} = \frac{1}{\sqrt{2}} \sum{(e_n(j)cos(\frac{(2j+1)(2k+1)\pi}{2n}))} $ , $ j,k \in {0...n-1}$
$ e_n(0) = e_n(n) := \sqrt{2}/2, e_n(j):= 1 $ for $ j \in \{1,..,n-1\} $
then
$ P_nC_n^{II} = \frac{1}{\sqrt{n_1}} \begin{pmatrix} (e_n(2j)cos(\frac{2j(2k+1)\pi}{2n})) & (e_n(2j)cos(\frac{2j(n+2k+1)\pi}{2n})) \\ (e_n(2j+1)cos(\frac{(2j+1)(2k+1)\pi}{2n})) & (e_n(2j+1)cos(\frac{(2j+1)(n + 2k+1)\pi}{2n})) \end{pmatrix} $
Right-hand side is a block matrix (4 matrices) $ j,k \in {0..n_1-1} $ where $ n_1 =n / 2 $
or put more simply (have I understood it right?): \begin{pmatrix} a00 & a01 & a02 & a03 \\ a10 & a11 & a12 & a13 \\ a20 & a21 & a22 & a23 \\ a30 & a31 & a32 & a33 \end{pmatrix} =>
\begin{pmatrix} a00 & a02 & a01 & a03 \\ a20 & a22 & a21 & a23 \\ a10 & a12 & a11 & a13 \\ a30 & a32 & a31 & a33 \end{pmatrix}
I would appreciate any help or insight about how this $P_n$ matrix would look. Simple example for 4x4 case would be excellent !
Thanks in advance.