Lecture 26: Fourier analysis on finite groups

IIT Kanpur July 201
20 followers
Sep 6, 2024
[Music]
welcome uh today we will discuss some
different topic than what we have done
uh till last lecture so we have
discussed the four year series of 2 p
period perodic function or in more
General periodic
function uh
so we will start doing some finite for
year analysis so to do uh a for year
analysis uh what we need is a group
structure as we have uh seen there uh in
the0 pi 0 to 2 pi interval so we have uh
done the sum modu 2 pi and that itself
was providing us a group structure and
uh so for the finite group first let us
look at uh okay this is for
year
analysis on finite sets
okay so first let us look at uh
let 1 Omega Omega squ up to Omega n
where N is a natural integer
be all
the
N roots of unity
this is n minus1 because I'm starting
from Nal to 0 that means what if I look
at the solution that is all
these are
solutions of the equation
z the^ n is equal to
1 obviously
if any number is a solution of this
equation then this is going to
lie on the unit circle centered at
origon so depending on N so these are
placed
here here
like this so they are placed on the unit
circle of
radius uh one centered at zero and uh
one so this namely we can write this
Omega uh to
be e to the
power 2 pi r
I by
n so then all these roots are zero if I
take the power is 2 < I by n then this
is e^ 4 < I by n and this goes up to e^
2 pi i n
-1 by n now if I take uh any
Zed and Z Prime this belongs to this
set
then if you say that Zed into Z Prime
this is equal to e^ 2 pi i k by n into E
power 2 pi i k Prime by n where K and K
Prime there can be any number between 0
to
nus1 now this itself is e the power 2 pi
i k + K Prime by
n now
if k + K Prime is more than n then it is
going to repeat because e to the^ 2 pi I
integer time integer is equal to
1 i n is equal to 1 for n varies over
Z so therefore this is again going to
after it cross n again it is going to
fall back here so that's why this J and
J Prime let me denote this set as PN
then J into Z Prime this belongs to PN
so which means this is the operation in
which we are looking for PN to be a
group so there so now in order to be a
group we need to have one identity and
the closure is satisfied we can satisfy
the associativity law exactly like this
and then
uh the function uh the number one If I
multiply it with any complex number so
that is going to give me that so that is
the identity and what about the inverse
now if J belongs to
PN
then Z is equal to e^ 2 pi i k by n for
some K lying between 0 to n minus of 1
now you consider Zed inverse to be I
denoted this e to the power 2 pi I nus
of K by
n so this is
again uh this is n root of unity
with uh so now as you can see this will
imply that z z Prime is nothing but one
so this is a group under
multiplication PN is a group
under
multiplication on the other hand there
is another group this reminds us that if
I look at ZN which consist of 0 1 2 up
to n
-1 now I Define
Define the
Operation uh
if uh for let us
say X and Y belongs to ZN you define
X this Y which is equal to x + y more n
what do I mean by that it's exactly like
uh so if I take uh three uh and I
suppose for
example if I take Zed 8 then you have
got 0 1 2 up to 7 so now what is my 6 +
7 6 + 7 is 13 so this is equal to module
8 is equal to 5 so as uh you can uh
always see that uh this Z8 under this
operation of
addition
z uh suppose uh uh I take uh let's
say uh two now what will be the inverse
of this two inverse of this two is if I
add six then I am going to get that this
is 8 and modu 8 is 0er and 0 is the
adita identity and hence j8 is a group
in general one can show that
ZN is a an aan group
group under this
operation okay so it's a there one can
see that there is uh a similarity
between this uh group of n root of unity
but there the operation is
multiplication and here ZN there the
multiplication
is some modul 8 and uh the two group we
can say that they are the same group
provided there is an
isomorphism between them now if we
Define the map from ZN
to to
PN so n going
to uh e to the power
2 pi i n by
n then easily one can check that this is
an nonto
isomorphism uh N1 + N2 if we take let us
say
N1 + N2 this will go to e ^ 2 pi
I uh N1 + N2 this is going to be suppose
uh this is the sum module of
this N2
byn so now we have an aelan group now we
can talk
of the function from
Jen to
C any let
F be a
function then we
Define for year
coefficient of f
as F of K
this is equal 1 / n summation / n is = 0
to N - 1 F of n e to the power - 2 pi i
k into n / by
n so we are
trying this is what is the for exactly
the same way what we have defined for
the 2 pi periodic function and uh here
it's enough for us to say that K belongs
to 0 to n
-1 now if I take any K Beyond nus of one
greater or equal to n then this is going
to be
suppose K is equal to n + K is greater
than or equal to
n
then K is equal to some
PN plus certain L and this L is going to
lie between 1
to
nus1 now e to the
power 2 pi i k n by n this is equal to
e^ 2 pi i k is PN
n
plus
Ln / n this is equal to e^ 2 pi I PN
into E power 2 pi I
Ln by n so this is equal to E power 2 pi
I because this is an integer so e to
the^ 2 pi I PN this is going going to be
equal to 1 so this is l n by n so it is
enough for us to restrict ourself from K
= 0 to nus1 although for any integer
even if we Define we can Define the for
transform which is denoted here as
capital F on Jed but this is going to
get repeated after the first n minus of
one integers
it be equal to some of them so let us
uh
compute
example
let F of N is a constant function
one
then
F K this is equal to 1 by n summation
Over N = 0 to N - of
1 E the power - 2i
I because FN is 1 k n by
n so now if K is equal to
Zer then what we are going to get we are
going to get that this F of0 all this
things are going to be equal to one and
if we add them then there will be n of
them and 1 by n is going to give me
one and if K is not equal to
zero then this
FK this is going to be 1 by n summation
/ n = 0 to nus of 1 e^ - 2 pi i k a n by
n now as you can see that e^ 2 pi i n by
n these are all for all n0 to n minus of
one they are the nth Capital nth root of
unity so what we know
that 1 +
Omega + Omega s up to Omega n minus of 1
this is equal to Z
because you just multiply it by Omega
then you can see that uh what you are
going to get
okay so so far so good
uh therefore this is going to be equal
to zero so essentially what we get is
that F K is equal to 1 if K is equal to
0 0
otherwise this we can denote that is f k
this is equal to Delta 0 of K where
Delta 0 here I am defining the function
which is takes the value 1 at k equal to
0 and Zer
otherwise okay so now let's compute uh
another example
um now let's do it uh I can I can leave
this as an
exercise uh you can compute let's take F
of n this is equal to
1 if n equal to 0 is equal to 0
otherwise that is in our just newly
introduced notation F of Nal to Delta 0
of n then you can compute
FK FK it's simple because uh if you take
uh 1 by n sum of this only one term get
survives and that is what you are going
to get it as 1 by
n okay so then let's do a little
non-trivial example so
let
F from Z Z
4 to
C uh be
defined by F of n is equal to n +
1 so this is a nicely defined function
what are the elements of Z 4 so Z4 we
have 0 1 2 and 3
so let's compute
uh uh so therefore
FK by definition is 1x 4 summation / n
from 0 to 3 F of n e to the power - 2 pi
i k n by n this is by
definition so there for I will let me
first calculate 4 F of 0 this is going
to
be F of when n equal to 0 f of 0 is
going to take the value one so the first
one is 1 and N equal to 0 this will go
away now the second one is f of 1 is 2
and then e to the power - 2 piun this is
uh again this is going to be zero so
therefore this is just one and + 3 K is
= 0 means this is 1 +
4 F of 3 is 4 therefore this is equal to
10 now I take four of f of
1 now this is equal to again F of 0 is =
1 and N = 0 means this is 1 into 1 plus
F of 1 is 2 N = 1 and K = 1 is - 2 < I
by 4
+ n = 2 then F of n is 3 into e the^ - 2
< I 3x 4 + 4 into E power - 2 pi
I
uh this is 2 this is 3 by
4 so now a simple compation this is 1 E
the
power 2 * e^ - I Pi by 2 in e^ - I Pi by
2 is uh equal to minus I so 2 into minus
of I + 3 into e^ - pi I which is equal
to -1 so this is minus of
3 + 4 into e^ - 3 < by 2 sin 3i by 2 is
going to take the negative value so this
is minus so this is going to be m
plus
uh e ^ 3 < by 2 that is going to be
minus of one so this is
I because cos is zero
so yeah this is I so what I get is - 2 +
2 I similarly if you take
f 2 you can you can compute it so this
is uh going to be 1 + 2 into uh minus of
I because e the power - < by uh 2 which
is going to be uh
I so this is 2 N = 1 n = 1 and K = 2 so
this is e the^ - 1 2 to 4 I
Pi I
pi and plus uh 3 into e^ - 2 < i k is 2
N is 2 / 4 and + 4 into E power - 2 < I
2 into 3 /
4 so so that is easy to compute
similarly you can compute four of f of 3
so all these things one can
compute four of f of3 if you compute
then this is going to be get
minus minus of 2
I okay and uh this would be a real
number which maybe 2
okay so now another important example
what we are going to compute is uh F of
Z is equal to F is a function from uh
JN where if I take my Z to be 01 2 2 N
minus of 1 and I Define this to be z
the^ n therefore uh
if J is equal E power 2 pi i k by
n in the PN I am defining it is uh K by
n for some k then for this particular K
because I am taking here the J I am
identifying with
PN
so if so if for this k then I can take
that F of K this is equal to 1 by n
summation n = 0 to n -1 e^ 2 pi i k by n
into e the power - 2 pi I
z the^ n means this to the power n 2 pi
i k n by n this is equal
to 1 by n and then this is n uh this is
going to be equal to
1 if J is not of the form e^ 2 pi i k by
n then what we can Define is that then
this F of K this is equal to summation 1
/ n n = 0 to n minus of 1 and z e to the
power so what I am here it is sorry uh
it is f of n isal to z the^ n
so
this is equal to 1 by n and then this is
uh this is a geometric progression so
what I will get is that this is equal to
uh Z the power n e to the power - 2 pi i
k by n to the power N - 1 ided by
z e power 2 pi i k by n
-1 and this is never equal to uh this is
minus this cannot be equal to 1 that's
what we have taken so this is
essentially is equal to 1 by n j ^ n- of
1 ided by Z into E power 2 pi
i k by n -1 denominator is never
zero so we have calculated some of the
forar coefficient and we have defined
the for year coefficient uh for finite
uh for this particular finite aan group
in the next lecture we will see that
what are the basic properties this for
year coefficient is going to obey uh
Visa is what we have learned in the four
year series uh for 2p periodic function
thank you
[Music]
[Music]
[Music]
