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$,

F = dftmtx(N);
U = F/sqrt(N);

$S$ above looks like the following: enter image description here

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).

  • $\begingroup$ Your $S$ matrix is wrong. S(1,1)=1, not zero. $\endgroup$ – Matt L. Sep 11 '14 at 18:29
  • $\begingroup$ @MattL. Turns out using real(S==1) to observe matrix elements is not such a good idea. Apologies. $\endgroup$ – 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


the following time-inverted (and periodically continued) vector


Here's an 'odd power' example:

x=[1 2 3 4 5 6 7 8]';
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
| improve this answer | |
  • $\begingroup$ Please see clarification above. The time inversion seems to be the case for even powers, but not odd powers. $\endgroup$ – curryage Sep 11 '14 at 18:20
  • $\begingroup$ @curryage: I added an example to my answer. Time inversion seems to be the case also for odd powers. $\endgroup$ – Matt L. Sep 11 '14 at 18:23
  • $\begingroup$ The formula involves ctranspose (complex conjugate transpose), not the usual matrix transpose. $\endgroup$ – curryage Sep 11 '14 at 18:24
  • $\begingroup$ @curryage ctranspose and ' do the same: mathworks.nl/help/matlab/ref/ctranspose.html $\endgroup$ – Matt L. Sep 11 '14 at 18:26

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.