View source for User:Tholden/11-1100/Homework Part 1

This page showcases my work done in implementing the Non-Commutative Gaussian Elimination algorithm with direct application to solving a permutation puzzle. I would like it to be known that I had originally chosen the Megaminx puzzle and am still in the process of solving it. The algorithm is currently running on a Sun x4600 computational server using Matlab 2010b including eight Opteron 8212 processors with 32 GB of memory. However, the algorithm is not conducive to parallelization and so has yet to converge. As a test-case, I have solved the <math> 2 \times 2 \times 2 </math> Rubik's cube, which I will also present here. In the event that the algorithm has not converged, I will submit the <math> 2 \times 2 \times 2 </math> Rubik's cube for marking.

==Theoretical Review of the Algorithm==

The purpose of Non-Commutative Gaussian Elimination (NCGE) is to find the elements and order of a subgroup generated by a finite set of generators. The algorithm proceeds as follows:

Let <math>G = \langle g_1,\ldots, g_\alpha \rangle</math>. Define the pivot of <math>\sigma \in S_n</math> to be the minimal <math>k \in \mathbb N</math> such that <math>\sigma(k) \neq k</math>. We prepare a table which is mostly empty

[[Image:NCGETable1.jpg|thumb|right|alt=The table initialization for Non-Commutative Gaussian Elimination.|A mostly empty table for Gaussian Elimination]]

Feed <math>g_1, \ldots, g_n</math> in order. To feed a non-identity <math>\sigma</math>, find its pivotal position <math>i</math> and let <math>j = \sigma(i)</math>. 
#If box <math>(i,j)</math> is empty, put <math>\sigma</math> in this box.
#If box <math>(i,j)</math> is not-empty, feed <math>\sigma' = \sigma_{i,j}^{-1} \sigma</math> into the table.

After this procedure is completed, for each occupied box <math>(i,j)</math> and <math>(k,\ell)</math> feed the product <math>\sigma_{i,j}\sigma_{k,\ell}</math> into the table. Repeat this until the table stops changing.

==Matlab Implementation ==

Individual and additional files can be downloaded from [[User:Tholden/11-1100/File Repository|this page]]. However, for completeness the primary algorithm has been included below. Its documentation is fairly comprehensive, and so all explanation of the code will be deferred to the code itself.

   function [table, tabLogic] = NonComGaussElim(myperms, table, tabLogic)
   %
   % NONCOMGAUSSELIM: A function used for computing the non-commutive gaussian
   % elimination algorithm on a finitely generated subset of the symmetric
   % group.
   %
   % [table,tabLogic] = NonComGaussElim(myperms,table,tabLogic)
   %
   %  INPUT:  myperms - [cell] A cell whose entries consist of the generators
   %                    of the group. The format of these entries should be
   %                    given via the "image" notation. Namely, if sigma is
   %                    a generator in Sn, then express sigma as
   %                    [sigma(1), sigma(2), ..., sigma(n)]
   %            table - [3d array, non-user input] The result of the
   %                    calculations. Necessary for recursion and needn't be
   %                    supplied by the end-user.
   %         tabLogic - [2d array, non-user input] The logical array
   %                    consisting of the non-identity indices for which
   %                    elements have been inserted into the table. Need not
   %                    be supplied by the end-user.
   % OUTPUT:    table - [3d array] The final result of the calculations.
   %                    table(i,j,:) consists of the permutation element
   %                    corresponding to pivot i with image j. 
   %         tabLogic - [2d array] The logical array
   %                    consisting of the non-identity indices for which
   %                    elements have been inserted into the table.
   %
   % Example: Consider the symmetric group S4 and the generators
   %          g1 = [2 3 1 4] and g2 = [2 1 4 3]. The code is executed as
   %          >>myperms = {[2 3 1 4], [2 1 4 3]};
   %          >>[table, tabLogical] = NonComGaussElim(myperms);
   
   % Version : 1.2
   % Author  : Tyler Holden
   % Date    : September 29, 2011
   
   %    To Do: 
   % 1) Add step to pre-process the input permutations. In particular, if
   %    the identity element is given as one of the generators, this algorithm
   %    will terminate prematurely. This is because the recursive halting
   %    criterion is the identity permutation
   % 2) Optimize for parallel computing. There are not many places wherein
   %    such improvements could be made, since the algorithm is recursive and
   %    heavily dependent on neighbouring iterations. However, some
   %    improvements may be made to computing products and inverses of
   %    elements.
   
   try
       
       % Return condition for recursion.
       if isempty(myperms)
           return
       end %End if
   
       sizeGrp = length(cell2mat(myperms(1)));
   
       % Since the user is not expected to input the table, the following
       % condition checks that we are at the top level of the recursion and
       % creates the table as necessary.
       if nargin < 2
           table = zeros(sizeGrp,sizeGrp,sizeGrp);
           tabLogic = zeros(sizeGrp);
           %     for i=1:sizeGrp
           %         table(i,i,:) = 1:sizeGrp;
           %     end %End for(i)
       end %End if
   
       % Here we pull out the first generator and calculate its pivot point.
       curGen = cell2mat(myperms(1));
       [piv,img] = findPivot(curGen);
   
       % If curGen is the identity, piv will be empty. In this case, we simply
       % return to the call function. This is used in sublevels of the recursion.
       % However, this will result in improper calculations if the identity is
       % included in the original set of permutations. In a future version of this
       % code, one could "pre-process" the input permutations to remove the
       % identity elements. This would remove the erroneous calculations and the
       % recursion check would stay consistent.
       if isempty(piv)
           return;
       end %End if
   
       % Pull the permutation from the table. Afterwards, check if it is empty. If
       % so, input curGen into the table. Otherwise, pre-multiply and apply
       % recursively to the singleton permutation.
       sigij(1:sizeGrp) = table(piv,img,1:sizeGrp);
   
       if isempty(find(sigij))
           table(piv,img,:) = curGen;
           tabLogic(piv,img) = 1;
           % Only when something new has been added to the table do we do the
           % multiplication step. Note that it is important to do multiplication
           % on both sides, otherwise this will not work.
           for it1=sizeGrp:-1:1;
               for it2=sizeGrp:-1:it1
                   if tabLogic(it1,it2)
                       sigij(1:sizeGrp) = table(it1,it2,1:sizeGrp);
                       %First multiplication.
                       newPerm = permMult(sigij, curGen);
                       [table,tabLogic] = NonComGaussElim({newPerm}, table, tabLogic);
                       %Second multiplication.
                        newPerm = permMult(curGen, sigij);
                        [table,tabLogic] = NonComGaussElim({newPerm}, table, tabLogic);
                    end %End if
                end %End for(it2)
            end %End for (it1)
        else
            newPerm = permMult(permInv(sigij),curGen);
            [table, tabLogic] = NonComGaussElim({newPerm}, table, tabLogic);
        end %end if 
 
     %Once the generator and its multiples have been added, we remove it from
     %the list of permutations and apply the algorithm recursively.
     [table, tabLogic] = NonComGaussElim(myperms(2:end), table, tabLogic);
   catch ME
       disp('Error');
   end 
   
   %-------------------------------Subroutines-------------------------------%
 
   function [pivot, image] = findPivot(permut)
   %
   % Calculates the pivot of the permutation. If the permutation is identity,
   % pivot and image return empty.
   pivot = find(permut ~= 1:length(permut),1);
   image = permut(pivot);
   
   function prod = permMult(perm1, perm2)
   %
   % Multiplies two permutations. This is simply the composition of the
   % permtuations acting on the set {1,...,n}. That is, if sigma and tau are
   % permutations, then sigma*tau acting on the set {1,...,n} is given in
   % "image notation" as
   % sigma*tau = [sigma(tau(1)), sigma(tau(2)), ... , sigma(tau(n)) ]
   prod = perm1(perm2);
   
   function inverse = permInv(perm)
   %
   % Calculates the inverse element. If sigma is the permutation to be
   % inverted, it is written as [sigma(1), sigma(2), ... , sigma(n)]. The
   % inverse of this function is just done by placing j in the sigma(j)
   % position. 
   inverse(perm) = 1:length(perm);



== 2x2x2 Rubik's cube==

[[Image:2x2x2CubeSmall.jpg|thumb|right|alt=A picture of the 2x2x2 Rubik's cube.|The 2x2x2 Rubik's cube.]]

The <math> 2 \times 2 \times 2 </math> Rubik's cube is a simplified version of the classical Rubik's cube. Indeed, while this simplified Rubik's cube still has six faces, each face only has four stickers. This greatly simplifies the process of analyzing the subgroup generated by this problem. We note that there are a total of <math> 24 </math> stickers on this cube, so that the generators a subgroup of <math> S_{24} </math> which has order <math> 24! </math>.

To determine our sticker numbering, we have rendered a [http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/RotatingCube.gif three-dimensional image of the cube], the source code for which can be found on my [[User:Tholden/11-1100/File Repository|file repository]].

Using the numbering scheme given in the rendered image of the cube, our generators can be given in cycle notation as
* <math> g_1 = (1\ 3\ 4\ 2) (22\ 6\ 9\ 17) (21\ 5\ 10\ 18) </math>
* <math> g_2 = (5\ 6\ 8\ 7) (21\ 14\ 11\ 1) (23\ 13\ 9\ 2) </math>
* <math> g_3 = (9\ 11\ 12\ 10) (3\ 5\ 13\ 19) ( 1\ 7\ 15\ 17) </math>
* <math> g_4 = (13\ 15\ 16\ 14) (24\ 8\ 11\ 19) (23\ 7\ 12\ 20) </math>
* <math> g_5 = (17\ 18\ 20\ 19) (22\ 16\ 12\ 3)(24\ 15\ 10\ 4) </math>
* <math> g_6 = (21\ 23\ 24\ 22)(14\ 20\ 4\ 6)(16\ 18\ 2\ 8) </math>

Using the supplied files, the code can be executed as follows:

 >> SimpleCube2
 >> tic; [table,tabLogic] = NonComGaussElim(myPerms); toc
 Elapsed time is 4.016460 seconds.
 >> prod(sum(tabLogic')+1)
 ans =
    88179840

However, we note that unlike the classical Rubik's cube, there are no center pieces whose position fixes an orientation of our configuration. Consequently, there are 24 additional symmetries. We conclude the actual size of the <math> 2\times 2 \times 2 </math> Rubik's cube group is <math> 3674160 = \frac{88179840}{24} </math>

==Megaminx==

[[Image:Megaminx.jpg|thumb|right|alt=The Megaminx permutation puzzle in a solved state. |The Megaminx Permutation Puzzle.]]

The Megaminx is an advanced but conceptually related cousin of the Rubik's cube. However, the polyhedron on which this puzzle is situated is not a cube, but is instead a dodecahedron. Consequently, this puzzle has twelve (12) faces and each face has a star configuration. The star configuration imparts eleven (11) stickers per face, meaning that this puzzle forms a subgroup of <math> S_{132} </math> which has order <math> 132! </math>. 

The sticker numbering for the Dodecahedron has been done by rendering a [http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/MegaminxNumbering.gif three-dimensional image of the dodecahedron.] With this numbering convention, the generators of the Megaminx group are given by

*<math> g_1 =(1\ 5\ 11\ 9\ 2)(4\ 8\ 10\ 6\ 3)(20\ 64\ 53\ 42\ 31)(21\ 65\ 54\ 43\ 32)(22\ 66\ 55\ 44\ 35)</math>
*<math> g_2 =(12\ 16\ 22\ 20\ 13)(15\ 19\ 21\ 17\ 14)(\ 1\ 33\ 86\ 68\ 57)(3\ 30\ 87\ 72\ 61)(2\ 27\ 88\ 75\ 64)</math>
*<math> g_3 =(23\ 27\ 33\ 31\ 24)(26\ 30\ 32\ 28\ 25)(2\ 44\ 97\ 79\ 13)(6\ 41\ 98\ 83\ 17)(9\ 38\ 99\ 86\ 20)</math>
*<math> g_4 =(34\ 38\ 44\ 42\ 35)(37\ 41\ 43\ 39\ 36)(9\ 55\ 108\ 90\ 24 )(10\ 52\ 109\ 94\ 28)(11\ 49\ 110\ 97\ 31)</math>
*<math> g_5 =(45\ 49\ 55\ 53\ 46)(48\ 52\ 54\ 50\ 47)(5\ 60\ 121\ 108\ 42)(8\ 63\ 120\ 105\ 39)(11\ 66\ 119\ 101\ 35)</math>
*<math> g_6 =(56\ 60\ 66\ 64\ 57)(59\ 63\ 65\ 61\ 58)(1\ 16\ 77\ 119\ 53)(4\ 19\ 76\ 116\ 50)(5\ 22\ 75\ 112\ 46)</math>
*<math> g_7 =(67\ 71\ 77\ 75\ 68)(70\ 74\ 76\ 72\ 69)(12\ 82\ 130\ 112\ 57)(15\ 85\ 127\ 113\ 58)(16\ 88\ 123\ 111\ 56)</math>
*<math> g_8 =(78\ 82\ 88\ 86\ 79)(81\ 85\ 87\ 83\ 80)(13\ 23\ 93\ 123\ 68)(14\ 26\ 96\ 124\ 69)(12\ 27\ 99\ 122\ 67)</math>
*<math> g_9 =(89\ 93\ 99\ 97\ 90)(92\ 96\ 98\ 94\ 91)(24\ 34\ 104\ 122\ 79)(25\ 37\ 107\ 125\ 80)(23\ 38\ 110\ 126\ 78)</math>
*<math> g_{10} =(100\ 104\ 110\ 108\ 101)(103\ 107\ 109\ 105\ 102)(35\ 45\ 115\ 126\ 90)(36\ 48\ 118\ 129\ 91)(34\ 49\ 121\ 132\ 89)</math>
*<math> g_{11} =(111\ 115\ 121\ 119\ 112)(114\ 118\ 120\ 116\ 113)(46\ 56\ 71\ 132\ 101)(47\ 59\ 74\ 131\ 102)(45\ 60\ 77\ 130\ 100)</math>
*<math> g_{12} =(122\ 126\ 132\ 130\ 123)(125\ 129\ 131\ 127\ 124)(67\ 78\ 89\ 100\ 111)(70\ 81\ 92\ 103\ 114)(71\ 82\ 93\ 104\ 115)</math>

As of writing this article, the algorithm has yet to converge. However, there are partial results that we can state. In particular, on four generators, the size of the group is the order of <math> 1.9 \times 10^{57} </math>. This was done using the code
 >>Dodecahedron2
 >>subPerms = myPerms(1:4);
 >> tic; [table,tabLogic] = NonComGaussElim(subPerms); toc
 Elapsed time is 1153.4619 seconds