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.

How to prove that convolution is associative, that is $(x*y)*z = x*(y*z)$, for $x,y,z \in l^2(Z_N)$. Either directly from the definition of convolution( Definition of convolution: For $z,w \in l^2(Z_N)$, the convolution $z*w \in l^2(Z_N)$ is the vector with components $z*w(m) = \sum_{n=0}^{N-1} z(m-n)w(n)$ ) or using following lemma:Suppose $z,w \in l^2(Z_N)$. Then for each m, $(z*w)\hat{}(m) = \hat{z(m)}\hat{w(m)}$( where ^ is discrete fourier transform $\sum_{n=0}^{N-1} z(n)e^{-2 \pi i m n/N}$) and also Fourier inversion formula: $z(n) = 1/N \sum_{m=0}^{N-1} \hat{z(m)} e^{2 \pi i m n/N}$, for $n=0,1,\dots, N-1$. In my solution I have used lemma above and Fourier inversion formula as following: \begin{align*} (x*y)*z(n) &= \frac{1}{N} \sum_{m=0}^{N-1} ((x*y)*z)\widehat{(m)}e^{2 \pi i m n/N}\\ &= \frac{1}{N} \sum_{m=0}^{N-1} (x*y)\widehat{(m)}*\widehat{z(m)}e^{2 \pi i m n/N}\\ &= \frac{1}{N} \sum_{m=0}^{N-1} \widehat{x(m)}\widehat{y(m)}\widehat{z(m)}e^{2 \pi i m n/N} \\ &= \frac{1}{N} \sum_{m=0}^{N-1} \widehat{x(m)}(y*z)\widehat{(m)}e^{2 \pi i m n/N}\\ &= \frac{1}{N} \sum_{m=0}^{N-1} (x*(y*z))\widehat{(m)}e^{2 \pi i m n/N}\\ &= x*(y*z). \end{align*}

share|improve this question
1  
tagged it as hw. (in case it was not obvious) –  user17762 Nov 22 '10 at 11:46

2 Answers 2

up vote 6 down vote accepted

This (very standard) computation is done in more generality on Proposition 46, p. 41 of

http://math.uga.edu/~pete/integral.pdf

The OP is asking for the special case in which the algebra $R$ is $\mathbb{C}$ and the semigroup $M$ is the (group) $(\mathbb{Z}/N\mathbb{Z},+)$.

Of course use of the language of algebras and semigroups is overkill for this particular special case. But if you look at the three lines of computation in the middle of the page, you see that the point is just to expand each of $(x*y)*z$ and $x*(y*z)$ into a triple sum and then notice that these two triple sums are identical.

In other words, just do it: it sounds harder than it actually is.

share|improve this answer
    
Right. In particular you don't need to know anything about the Fourier transform to do this computation. Morally it follows from the special case of functions with finite support. –  Qiaochu Yuan Nov 22 '10 at 15:57
    
@Qiaochu: unless I am misinterpreting the notation, we are talking about the discrete Fourier transform on a finite abelian group, so all functions have finite support. (But I agree that the proofs in other cases, like the Fourier transform on $\mathbb{R}^n$, are quite similar.) –  Pete L. Clark Nov 22 '10 at 16:19
    
ah, right. I thought the question was about l^2(Z). –  Qiaochu Yuan Nov 22 '10 at 18:54

HINT $\ $ Put $\rm\ \hat f = \sum_{i=0}^{N-1} \:f(i)\: X^i\ $ and note $\rm\ \hat f \:(\hat g\: \hat h) \equiv (\hat f\: \hat g)\:\hat h\ \ (mod\:\ X^N - 1)\ $

share|improve this answer

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.