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.abdoll...@math.ui.ac.ir abdoll...@member.ams.org http://sci.ui.ac.ir/~a.abdollahi ________________________________ From: azhvan sanna <azh...@hotmail.com> To: alireza_abdoll...@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_abdoll...@yahoo.com > Subject: Re: [GAP Forum] functions work wih conjugacy class > To: azh...@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 > abdoll...@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.abdoll...@math.ui.ac.ir > abdoll...@member.ams.org > http://sci.ui.ac.ir/~a.abdollahi > > > > ----- Original Message ---- > From: azhvan sanna <azh...@hotmail.com> > To: GAP Forum <fo...@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@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! _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
