# Determining effect of powers of DFT matrix conjugate on input without multiplying

Suppose I have a DFT matrix $F$ of dimensions $N \times N$ where $N$ is a power of $2$. I convert it into a unitary matrix $\displaystyle U = \frac{F}{\sqrt{N}}$ and compute $S = U^* U^*$.

$S$ seems to have a pattern. $S$ has at most one $1$ per row. Applying $S$ on my $N$-sample signal $x$ essentially provides me either a permutation of $x$(if $N$ is an even power of $2$) or a subset of $x$(if $N$ is odd power of $2$). By subset, the length of $x$ remains the same, but some of the elements get truncated to $0$

Translated to MATLAB code for $N=8$,

N=8;
F = dftmtx(N);
U = F/sqrt(N);
S=ctranspose(U)*ctranspose(U);


$S$ above looks like the following:

My problem is the following: Given $N$, can I determine how to pick elements of $x$ without having to resort to multiplying by $S$ ? (For the curious, let's say the matrix multiplication is expensive for my situation).

• Your $S$ matrix is wrong. S(1,1)=1, not zero. – Matt L. Sep 11 '14 at 18:29
• @MattL. Turns out using real(S==1) to observe matrix elements is not such a good idea. Apologies. – curryage Sep 11 '14 at 23:57

In both cases (odd and even powers of 2) you should get as a result simply a time inversion of your original signal. Because of the implicit periodicity you get from the original vector

$$[x_1,x_2,x_3,\ldots,x_N]$$

the following time-inverted (and periodically continued) vector

$$[x_1,x_N,x_{N-1},\ldots,x_2]$$

Here's an 'odd power' example:

N=8;F=dftmtx(N);U=F/sqrt(N);
x=[1 2 3 4 5 6 7 8]';
y=U'*U'*x;
y =

1.00000 - 0.00000i
8.00000 + 0.00000i
7.00000 + 0.00000i
6.00000 - 0.00000i
5.00000 + 0.00000i
4.00000 + 0.00000i
3.00000 + 0.00000i
2.00000 - 0.00000i

• Please see clarification above. The time inversion seems to be the case for even powers, but not odd powers. – curryage Sep 11 '14 at 18:20
• @curryage: I added an example to my answer. Time inversion seems to be the case also for odd powers. – Matt L. Sep 11 '14 at 18:23
• The formula involves ctranspose (complex conjugate transpose), not the usual matrix transpose. – curryage Sep 11 '14 at 18:24
• @curryage ctranspose and ' do the same: mathworks.nl/help/matlab/ref/ctranspose.html – Matt L. Sep 11 '14 at 18:26