Home > matgraph > @graph > sl2graph.m

sl2graph

PURPOSE ^

sl2graph(g,p) -- create an SL(2,p) graph

SYNOPSIS ^

function sl2graph(g,p)

DESCRIPTION ^

 sl2graph(g,p) -- create an SL(2,p) graph
 g is the graph to be created
 p is a prime
 the vertices of g correspond to 2-by-2 matrices with determinant equal to
 1 and entries modulo p
 Two vertices are adjacent if one can be obtained from the other by
 multiplication by either [1 1; 0 1] or [1 0; 1 1].
 In other words, g is a Cayley graph based on the group SL(2,p) with the
 two matrices as generators.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function sl2graph(g,p)
0002 % sl2graph(g,p) -- create an SL(2,p) graph
0003 % g is the graph to be created
0004 % p is a prime
0005 % the vertices of g correspond to 2-by-2 matrices with determinant equal to
0006 % 1 and entries modulo p
0007 % Two vertices are adjacent if one can be obtained from the other by
0008 % multiplication by either [1 1; 0 1] or [1 0; 1 1].
0009 % In other words, g is a Cayley graph based on the group SL(2,p) with the
0010 % two matrices as generators.
0011 
0012 % Make sure p is prime
0013 
0014 if ((p<1) || (length(factor(p)) > 1))
0015     error('p must be prime')
0016 end
0017 
0018 % Generate a table of all matrices [ a b ; c d ] in SL2(p). There are p^3
0019 % of them that we store row-wise as [ a b c d ].
0020 
0021 n = p^3-p;
0022 vtable = zeros(n,4);
0023 idx = 1;
0024 
0025 % first the rows with a = 0
0026 for c=1:p-1
0027     b = p-modinverse(c,p);
0028     for d=0:p-1
0029         row = [ 0, b, c, d ];
0030         vtable(idx,:) = row;
0031         idx = idx+1;
0032     end
0033 end
0034 
0035 % now the rows with a not equal to 0
0036 for a=1:p-1
0037     for b=0:p-1
0038         for c=0:p-1
0039             aa = modinverse(a,p);
0040             d = aa*(b*c+1);
0041             d = mod(d,p);
0042             row = [ a, b, c, d ];
0043             vtable(idx,:) = row;
0044             idx = idx+1;
0045         end
0046     end
0047 end
0048 
0049 
0050 % DEBUG determinant check
0051 for idx=1:size(vtable,1)
0052     row = vtable(idx,:);
0053     A = reshape(row,2,2);
0054     d = det(A);
0055     if (mod(d,p) ~= 1)
0056         disp([row,d])
0057     end
0058 end
0059 
0060 vtable = sortrows(vtable);
0061 
0062 edgelist = [];
0063 resize(g,0);
0064 if (n>1000)
0065     sparse(g);
0066 end
0067 resize(g,n);
0068 
0069 for v=1:n
0070     label(g,v,int2str(reshape(vtable(v,:),2,2)));
0071 end
0072 
0073 % Caley graph generators
0074 
0075 S = [ 1 1 ; 0 1 ];
0076 T = S';
0077 
0078 
0079 for i = 1:n
0080     A = reshape(vtable(i,:),2,2);
0081     B = A*S;
0082     B = mod(B,p);
0083     j = findrow(B(:)',vtable);
0084     edgelist = [edgelist; [i,j]];
0085     
0086     B = A*T;
0087     B = mod(B,p);
0088     j = findrow(B(:)',vtable);
0089     edgelist = [edgelist; [i,j]];
0090 end
0091 
0092 add(g,edgelist);
0093 
0094 
0095 
0096 
0097 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0098 
0099 function b = modinverse(a,p)
0100 % computer inv(a) modulo p
0101 [d,x,y] = gcd(a,p);
0102 b = mod(x,p);
0103 
0104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0105 
0106 function idx = findrow(row, A)
0107 % find a row in a row sorted matrix, assume row is correct length
0108 % return 0 if not found
0109 
0110 n = size(A,1);
0111 idx = 0;
0112 if n==0
0113     return
0114 end
0115 
0116 
0117 mid = ceil(n/2);
0118 midrow = A(mid,:);
0119 if all(row == midrow)
0120     idx = mid;
0121     return
0122 end
0123 
0124 m = length(row); % presumably 4
0125 for j=1:m
0126     if row(j) < midrow(j)
0127         idx = findrow(row,A(1:mid-1,:));
0128         return
0129     end
0130     if row(j) > midrow(j)
0131         idx = findrow(row,A(mid+1:end,:));
0132         if (idx>0)
0133             idx = idx+mid;
0134         end
0135         return
0136     end
0137 end
0138 
0139 
0140 
0141 
0142 
0143

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003