Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been playing with Fourier transform a little and discovered the identity quoted in the title. More precisely, writing the matrix for the Fourier transform in ${\mathbb Z} / N {\mathbb Z}$ as

$$A = {1 \over \sqrt{N}} \pmatrix{ \zeta^0& \zeta^0 & \cdots & \zeta^0 \cr \zeta^0& \zeta^1 & \cdots & \zeta^{N-1} \cr \vdots & \vdots &\ddots &\vdots \cr \zeta^0& \zeta^{N-1} & \cdots & \zeta^1 \cr }$$

(with $\zeta \equiv \exp({2 \pi i \over N})$) one easily obtains the quoted identity by using the famous determinant of Vandermonde matrix and the fact that the transform is unitary.

Now, I'd be interested whether the identity can be proven directly, and ideally given a nice combinatorial interpretation. I suppose this should be possible because of lot of structure in the problem but I wasn't able to come up with anything yet.

share|improve this question
    
I have a partial answer, but it's missing two steps, one of which I can't remember and one of which I don't know. It involves relating the discriminant of t^n + pt + q to the generating function satisfying y = x + y^n, which describes a certain family of trees. Not sure if it works. –  Qiaochu Yuan Jan 19 '11 at 16:37
    
@Qiaochu: thank you, this is the closest to an answer yet. I am not sure I follow though; could you be a little bit more explicit about that connection (even if it doesn't work or is just sketchy). It would be nice if you posted a CW answer so that we could see what it leads to. –  Marek Jan 19 '11 at 18:29
add comment

3 Answers 3

up vote 3 down vote accepted

It can be derived directly by considering the n-roots of one $z_k = exp(\frac{i 2\pi k}{N})$

$F(z) = z^N-1 = (z-z_0) ... (z-z_{N-1})$

First, this readily implies (by setting $z=0$) that

$ \prod z_i = (-1)^{N+1}$

Second, by deriving $F(z)$ and evaluating at, say, $z=z_0$ we get

$ N z_0^{N-1} = (z_0 - z_1) (z_0 - z_2) ... (z_0 - z_{N-1}) $

Rearranging, writing the same equation for all $z_i$, multiplying all them, and using the previous equation, we get at your result.

$ N^N (\prod z_i)^{N-1} = \prod_{i \ne j} (z_i - z_j) $

$ N^N (-1)^{N+1} = \prod_{i \ne j} (z_i - z_j) $

$N^{N/2} = | \prod_{i<j} (z_i - z_j)|$

No combinatorial interpretation, though.

share|improve this answer
    
Thanks. There are a few little mistakes as far as I can see though. On the third line there should be no $-$ on the LHS and likewise the first $z_0$ on the RHS. There is also a typo of writing $z_0 - z_1$ twice. Because of these small typos, signs are also wrong on the latter lines. If you fix the issues I'd be happy to up-vote :) –  Marek Jan 19 '11 at 15:39
    
i had fixed the sign before reading your comment - fixed the other –  leonbloy Jan 19 '11 at 15:43
    
thanks again. And sorry if I sounded too critical; I appreciate your answer but I didn't want to up-vote until I was sure I understood it properly. –  Marek Jan 19 '11 at 15:55
    
apologies not necessary, you didn't sound critical. thanks for the corrections –  leonbloy Jan 19 '11 at 16:04
add comment

This is not an answer. I worked out some of the details relevant to my comment above here and here. A rough summary is as follows:

  • The discriminant of $t^n + pt + q$ turns out to equal $(-1)^{ {n \choose 2} } ((1 - n)^{n-1} p^n + n^n q^{n-1} )$. This is a generalization of the fact you want to prove ($p = 0, q = -1$).
  • There is a unique power series $t$ in the variable $q$ which satisfies $t = q + t^n$ ($p = -1$) and $t(0) = 0$. It turns out to be precisely $t = \sum \frac{1}{(n-1)k + 1} {nk \choose k} q^{(n-1)k + 1}$ for combinatorial reasons; $t$ counts what I call "$n$-ary trees" in the blog post above (but you should read the definition carefully).
  • Therefore $\frac{dt}{dq} = \sum {nk \choose k} q^{(n-1)k}$. It turns out that the relation $t = q + t^n$ implies a corresponding algebraic relation for $\frac{dt}{dq}$, and the leading term of this algebraic relation is, up to sign, the discriminant of $t^n - t + q$.

Unfortunately I do not know a conceptual reason why the third bullet point is true. You can see it directly in the case $n = 2$, where the discriminant of $t^2 - t + q$ is $1 - 4q$ and

$$\frac{dt}{dq} = \sum {2k \choose k} q^k = \frac{1}{\sqrt{1 - 4q}}.$$

Here $t$ is the generating function for the Catalan numbers. You can also work out what happens when $n = 3$ by the cubic formula, but after that things become troublesome.

share|improve this answer
    
Here is an idea: when the discriminant vanishes, the power series for dt/dq ought to have a pole. This is because t is a parameterized root of the equation t = q + t^n, and when the discriminant vanishes some of the roots are merging, which should cause branch points. Unfortunately, I still don't know how to give a combinatorial proof of the relation that dt/dq satisfies. –  Qiaochu Yuan Jan 19 '11 at 19:05
    
Nice, thank you very much! I'll try to play with these ideas a little and see whether I'll think of something. –  Marek Jan 20 '11 at 8:16
add comment

If you look at Combinatorial Proof of Vandermonde's determinant perhaps you can extract the desired combinatorial proof.

share|improve this answer
    
Thank you Slowsolver, I'll take a look. –  Marek Jan 19 '11 at 13:21
    
After a quick peek, I don't think this helps. The proof in the article assumes that $zeta^i$ ($x_i$ in their setting) are integers which is a completely different problem from my case of $N$th roots of unity. –  Marek Jan 19 '11 at 13:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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