[GAP Forum] functions work wih conjugacy class

[Alireza Abdollahi]

Dear Azhvan

The generating set must be symmetrized.  
Also, remeber that root function in GAP (as other computational package) cannot compute all the roots and present them as an output, so sometimes (or often!) you see an output which  seemingly incomplete (i.e., it does not contain all the eigenvalues). 
Anyway, the functions below can be considered as starting point to obtain and adhoc one for yourself.

It may be possible to find eigenvalues corresponding to an irreducible character (you need change the followings for it), I think it is not possible to find in this way all the eigenvalues.
In fact, this is my feeling (not a mathematical thing) that it is better to calculate eigenvalues of a Cayley graph by constructing its adjacency matrix and then finding its spectrum. It is very easy, e.g., in GAP by using Soicher's GRAPE package to have the adjacency matrix. While using the approach of ``irreducible character'' (I think)it is often used in theoretical proofs for some computations and apart of its nice form suggesting that it is useful for compute for the ``whole of spectrum'', it is NOT. Of course, it is ideal to compute a part of spectrum.

All the Best
Alireza


Alireza Abdollahi
Department of Mathematics
University of Isfahan 
Isfahan 81746-73441,Iran
a.abdollahi at math.ui.ac.ir
abdollahi at member.ams.org
http://sci.ui.ac.ir/~a.abdollahi 




________________________________
From: azhvan sanna <azhvan at hotmail.com>
To: alireza_abdollahi at yahoo.com
Sent: Tuesday, July 21, 2009 12:11:06 AM
Subject: RE: [GAP Forum] functions work wih conjugacy class

Dear Alireza,

Do you mean I need to use symmetric Cayley set ( so when I list the elements of S, I use both x and x^-1, x inverse,) or no If I just enter a set of generators it will be enough and it counts already all the inverse too. because I checked for some small groups it gives me some strange result.  Do you think this can be used for those big sporadic groups?
thanks so much

Azhvan


> Date: Mon, 20 Jul 2009 14:05:12 -0700
> From: alireza_abdollahi at yahoo.com
> Subject: Re: [GAP Forum] functions work wih conjugacy class
> To: azhvan at hotmail.com
> 
> Dear Azhvan,
> Here is the text file of  a program for finding  the spectrum of  a cayley graph.
> 
> The function name EigenCayley 
> 
> it has two parameters the first one is the group and the second one is the (symmetric) generating set.
> 
> for example
> gap> S5:=SymmetricGroup(5);;
> gap>S:=[(1,2),(1,3),(1,4),(1,5)];;
> gap>EigenCayley(S5,S);
> [[-4,1],[-3,12],[-2,28],[-1,4],[0,30],[1,4],[2,28],[3,12],[4,1]]
> 
> The first argument of each list in the above list is an eigen value of the graph and the second is its multiplicity.
> 
> You need to change it for your problem. Note that if the spectrum contains a root which cannot be found by GAP (see the correspoding function).
> 
> In the meanwhile it should be quoted that some parts of this code can be find it the GAP forum and I do not remember the author (maybe Alex Hulpke) and the code (maybe "classfinder")!!
> (Appologies for this!)
> 
> All the Best
> Alireza
> 
> 
> Alireza Abdollahi
> Department of Mathematics
> University of Isfahan, 
> Isfahan 81746-73441,Iran
> abdollahi at member.ams.org
> URL: http://sci.ui.ac.ir/~a.abdollahi 
> 
> 
> 
> -----Inline Attachment Follows-----
> 
> setproduct:=function(S,n)
> local T,m;
> T:=S; m:=1;
> if n=1 then T:=S; fi;
> while  n>m do
> T:=List(Cartesian(T,S),i->i[1]*i[2]);
> m:=m+1;
> od;
> return T;
> end; 
> 
> classfinder:=function(G,g)
> local c;
> c:=ConjugacyClasses(G);
> return First([1..Length(c)],i->g in c[i]);
> end;
> 
> sumeigen:=function(G,S,t)
> local l,irr;
> irr:=Irr(G);
> l:=List(setproduct(S,t),i->classfinder(G,i));
> return List(irr,X->[Sum(l,i->X[i]), "deg=", X[1]]);
> end;
> 
> sumeigenn:=function(G,S,i)
> local l,X;
> X:=Irr(G)[i];
> l:=List(S,i->classfinder(G,i));
> return Sum(l,i->X[i]);
> end;
> 
> sumeigennn:=function(G,S,i)
> local d,X,l;
> X:=Irr(G)[i];
> d:=X[1];
> l:= List([1..d],j->sumeigenn(G,setproduct(S,j),i));
> return l;
> end;
> 
> 
> newtonformulae:=function(L)
> local n,a,A,B,i;
> n:=Size(L); a:=-L[1]; A:=[a];
> for i in [2..n] do
> a:=-(1/i)*(Sum(List([1..i-1],j->L[j]*A[i-j]))+L[i]);
> Add(A,a);
> od;
> return A;
> end; 
> 
> root:=function(L)
> local n,x,f;
> x:=Indeterminate(Rationals,"x");
> n:=Size(L);
> f:=Sum(List([1..n],j->L[j]*x^(n-j)))+x^n;
> return RootsOfUPol(f);
> end;
> 
> eigenX:=function(G,S,i)
> local d,X,l;
> X:=Irr(G)[i];
> d:=X[1];
> l:=root(newtonformulae(sumeigennn(G,S,i)));
> return [l, d];
> end;
> 
> eigenCayley:=function(G,S)
> return List([1..Size(ConjugacyClasses(G))],i->eigenX(G,S,i));
> end;
> 
> listexpand:=function(L)
> local a,i,j;
> a:=[];
> for i in [1..Size(L[1])] do
> for j in [1..L[2]] do
> Add(a,L[1][i]);
> od;
> od;
> return a;
> end;
> 
> 
> EigenCayley:=function(G,S)
> local e1,E1,a,B,i;
> E1:=[];
> e1:=eigenCayley(G,S);
> a:=List(e1,i->listexpand(i));
> for i in [1..Size(a)] do
> Append(E1,a[i]);
> od;
> B:=Set(E1);
> return List(B,i-> [i, Size( Filtered(E1,j->j=i))] );
> end;
> 
> 
> 
> 
> 
> 
>  Alireza Abdollahi
> Department of Mathematics
> University of Isfahan 
> Isfahan 81746-73441,Iran
> a.abdollahi at math.ui.ac.ir
> abdollahi at member.ams.org
> http://sci.ui.ac.ir/~a.abdollahi 
> 
> 
> 
> ----- Original Message ----
> From: azhvan sanna <azhvan at hotmail.com>
> To: GAP Forum <forum at gap-system.org>
> Sent: Monday, July 20, 2009 7:32:35 PM
> Subject: [GAP Forum] functions work wih conjugacy class
> 
> 
> Dear GAP Forum,
> This was my unsolved question: 
> I want to calculate all eigenvalues of cubic cayley graphs associate
> with sporadic simple group. So if G denote one of 26 sporadic simple
> group, and X a set of generators with 3 elements, one "a" of order 2,
> and the other "b" and "b^-1" of order greater than 2. then Cay(G,X) is
> a cubic Cayley graph. and by a well-know formula for computing
> eigenvalues of cayley graphs, we have: for each
> 
> "Xi" in Irr(G)
> of degree n, we have n eigenvalues L_1, L_2,...,L_n each of them has
> multiplicity n ( so in total this character "Xi" of
> 
> degree n gives us "n^2" eigenvalues of our graph). and we can compute them by Newton-Waring identities and following fact that 
> 
> for t from 1 to n we have (L_1)^t + (L_2)^t + ... +(L_n)^t =  Sum {Xi (x_1.x_2....x_t)} where sum is over the value of "Xi" on 
> 
> the all product of t elemnts from our generator set X.
> 
> Using
> this I will find a polynomial of degree n and roots give me the
> eigenvalues, instead of determaining the characterestic polynomial of a
> matrix of order |G| which for sporadic simple group this number is huge
> and also finding their roots!
> 
> As you see, I need to calculate
> this for every character in Irr(G), and evalute them in all t-product
> of  elements of generator set.
> 
> I know this will involve lots of calculation as  mentioned it to me by Thomas Breuer. Because of the special case  here, I am just having a generator set of 3 elements, I would like to know is it any function to calculate for generator "a" and "b"  and conjugacy class "C" the number "n_{t,C}(a,b)" which calculates the number of t-products( products of length t of a,a^-1, b, b^-1) of a and b which belongs to the Conjugacy class "C" for t runs from 1 to max{ deg(Xi) | "Xi" runs over Irr(G)}?
> Because after this point most of calculations above are pretty simple.
> 
> Azhvan
> 
> 
> 
> _________________________________________________________________
> More storage. Better anti-spam and antivirus protection. Hotmail makes it simple.
> http://go.microsoft.com/?linkid=9671357_______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
> 
> 
> 
> 

________________________________
Stay in the loop and chat with friends, right from your inbox! Learn how!