Drorbn - User contributions [en]

11-1100/Homework Assignment 5

2011-12-02T22:41:46Z

Tholden: /* Solve the following questions */ Spelling Mistake

{{11-1100/Navigation}}
===The Final Exam===
The Final Exam will take place on Friday December 9, 10-1 at Bahen 6183. You may expect very approximately one third of the exam to be about class-proven theorems, one third to be repeats of HW problems and/or exam problems from this year or last, and one third to be fresh exercises. You will have to solve about 5 out of about 6 problems. It is likely that the overall shape of the exam will be similar to last year's final exam, which can be found at [[10-1100/Final Exam]].

When I was a student, before exams I usually made sure that I '''absolutely''' understand all class material and I worried less about the exercises, on the assumption that class was about the most important knowledge and that if I really understood all that was done in class, the exercises would follow relatively easily. That was my strategy; it worked well for me, but what works for you is not for me to tell.

===Last Week's Schedule===
<center>

'''Warning.''' This schedule is subject to changes. Recheck this web site the day before any activity.


{|border=1 cellspacing=0
|-
|Tuesday December 6
|10-12
|Last Class
|-
|Wednesday December 7
|12-2
|{{Dror}}'s office hours, Bahen 6178.
|-
|
|2PM
|HW5 "early bird" due date. If you submit HW5 by this time, it will be marked by noon of the following day.
|-
|Thursday December 8
|10:30-12:30
|{{Dror}}'s office hours, Bahen 6178.
|-
|
|Noon
|HW5 is due in {{Dror}}'s office, to be graded after the final. Also, at this time "early bird" marked HW5 can be collected at {{Dror}}'s office.
|-
|
|3-5
|Stephen Morgan's office hours, at Huron 1028.
|-
|Friday December 9
|10-1
|The Final Exam.
|}
</center>

===Solve the following questions===

'''Problem 1.''' Let <math>M</math> be a module over a PID <math>R</math>. Assume that <math>M</math> is isomorphic to <math>R^k\oplus R/\langle a_1\rangle\oplus R/\langle a_2\rangle\oplus\cdots\oplus R/\langle a_l\rangle</math>, with <math>a_i</math> non-zero non-units and with <math>a_1\mid a_2\mid\cdots\mid a_l</math>. Assume also that <math>M</math> is isomorphic to <math>R^m\oplus R/\langle b_1\rangle\oplus R/\langle b_2\rangle\oplus\cdots\oplus R/\langle b_n\rangle</math>, with <math>b_i</math> non-zero non-units and with <math>b_1\mid b_2\mid\cdots\mid b_l</math>. Prove that <math>k=m</math>, that <math>l=n</math>, and that <math>a_i\sim b_i</math> for each <math>i</math>.

'''Problem 2.''' Let <math>q</math> and <math>p</math> be primes in a PID <math>R</math> such that <math>p\not\sim q</math>, let <math>\hat{p}</math> denote the operation of "multiplication by <math>p</math>", acting on any <math>R</math>-module <math>M</math>, and let <math>s</math> and <math>t</math> be positive integers.
# For each of the <math>R</math>-modules <math>R</math>, <math>R/\langle q^t\rangle</math>, and <math>R/\langle p^t\rangle</math>, determine <math>\ker\hat{p}^s</math> and <math>(R/\langle p\rangle)\otimes\ker\hat{p}^s</math>.
# Explain why this approach for proving the uniqueness in the structure theorem for finitely generated modules fails.

'''Problem 3.''' (comprehensive exam, 2009) Find the tensor product of the <math>{\mathbb C}[t]</math> modules <math>{\mathbb C}[t,t^{-1}]</math> ("Laurent polynomials in <math>t</math>") and <math>{\mathbb C}</math> (here <math>t</math> acts on <math>{\mathbb C}</math> as <math>0</math>).

'''Problem 4.''' (from Selick) Show that if <math>R</math> is a PID and <math>S</math> is a multiplicative subset of <math>R</math> then <math>S^{-1}R</math> is also a PID.

'''Definition.''' The "rank" of a module <math>M</math> over a (commutative) domain <math>R</math> is the maximal number of <math>R</math>-linearly-independent elements of <math>M</math>. (Linear dependence and independence is defined as in vector spaces).

'''Definition.''' An element <math>m</math> of a module <math>M</math> over a commutative domain <math>R</math> is called a "torsion element" if there is a non-zero <math>r\in R</math> such that <math>rm=0</math>. Let <math>\mbox{Tor }M</math> denote the set of all torsion elements of <math>M</math>. (Check that <math>\mbox{Tor }M</math> is always a submodule of <math>M</math>, but don't bother writing this up). A module <math>M</math> is called a "torsion module" if <math>M=\mbox{Tor }M</math>.

'''Problem 5.''' (Dummit and Foote, page 468) Let <math>M</math> be a module over a commutative domain <math>R</math>.
# Suppose that <math>M</math> has rank <math>n</math> and that <math>x_1,\ldots x_n</math> is a maximal set of linearly independent elements of <math>M</math>. Show that <math>\langle x_1,\ldots x_n\rangle</math> is isomorphic to <math>R^n</math> and that <math>M/\langle x_1,\ldots x_n\rangle</math> is a torsion module.
# Conversely show that if <math>M</math> contains a submodule <math>N</math> which is isomorphic to <math>R^n</math> for some <math>n</math>, and so that <math>M/N</math> is torsion, then the rank of <math>M</math> is <math>n</math>.

'''Problem 6.''' (see also Dummit and Foote, page 469) Show that the ideal <math>\langle 2,x\rangle</math> in <math>R={\mathbb Z}[x]</math>, regarded as a module over <math>R</math>, is finitely generated but cannot be written in the form <math>R^k\oplus\bigoplus R/\langle p_i^{s_i}\rangle</math>.

11-1100/Navigation

2011-11-29T16:19:40Z

Tholden:

<noinclude>Back to [[11-1100]]. </noinclude>
{| border="1px" cellpadding="1" cellspacing="0" width="100%" style="font-size: small; align: left"
|- align=left
!#
!Week of...
!Notes and Links
|- align=left
|align=center|1
|Sep 12
|[[11-1100/About This Class|About This Class]], [[11-1100/Classnotes for Tuesday September 13|Tuesday]] - Non Commutative Gaussian Elimination, [[11-1100/Classnotes for Thursday September 15|Thursday]] - NCGE completed, the category of groups, images and kernels.
|- align=left
|align=center|2
|Sep 19
|I'll be in {{Home link|Talks/Strasbourg-1109/|Strasbourg}}, class was be taught by [http://www.math.toronto.edu/selick/ Paul Selick]. See my {{Home link|classes/1112/1100-AlgebraI/The_Selick_Week.html|summary}}.
|- align=left
|align=center|3
|Sep 26
|[[11-1100/Class Photo|Class Photo]], [[11-1100/Homework Assignment 1| HW1]], [[11-1100/Homework Assignment 1 Submissions| HW1 Submissions]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 1| HW 1 Solutions]]
|- align=left
|align=center|4
|Oct 3
|[[11-1100/The Simplicity of the Alternating Groups| The Simplicity of the Alternating Groups]]
|- align=left
|align=center|5
|Oct 10
|[[11-1100/Homework Assignment 2|HW2]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 2| HW 2 Solutions]]
|- align=left
|align=center|6
|Oct 18
|[[11-1100/Groups of Order 60 and 84|Groups of Order 60 and 84]]
|- align=left
|align=center|7
|Oct 24
|Extra office hours: Monday 10:30-12:30 (Dror), 5PM-7PM @ Huron 1028 (Stephen). [[11-1100/Term Test|Term Test]] on Tuesday. [[11-1100/Summary for the midterm| Summary for the midterm exam]]. [[11-1100/Term Test Solutions|Term Test - Sample Solutions ]]
|- align=left
|align=center|8
|Oct 31
|[[11-1100/Homework Assignment 3|HW3]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 3| HW 3 Solutions]]
|- align=left
|align=center|9
|Nov 7
|Monday-Tuesday is November Break, {{Pensieve Link|Classes/11-1100/1t2c4w.pdf|One Theorem, Two Corollaries, Four Weeks}}
|- align=left
|align=center|10
|Nov 14
|[[11-1100/Homework Assignment 4|HW4]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 4| HW 4 Solutions]]
|- align=left
|align=center|11
|Nov 21
|
|- align=left
|align=center|12
|Nov 28
|[[11-1100/Homework Assignment 5|HW5 and last week's schedule]]
|- align=left
|align=center|13
|Dec 5
|UofT Fall Semester ends Wednesday; our [[10-1100/Final Exam|Final Exam]] will be on Friday
|- align=left
|colspan=3 align=center|[[11-1100/Register of Good Deeds|Register of Good Deeds]]
|- align=left
|colspan=3 align=center|[[Image:11-1100-ClassPhoto.jpg|310px]] [[11-1100/Class Photo|Add your name / see who's in!]]
|- align=left
|colspan=3 align=center|[[Image:10-1100-Splash.png|310px]] See {{Home Link|classes/1112/1100-AlgebraI/NCGE.html|Non Commutative Gaussian Elimination}}
|}

11-1100/Homework Solutions

2011-11-29T16:07:28Z

Tholden:

{{11-1100/Navigation}}

==Sample solutions to Homework Assignment 1==

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Smith || Jerrod || [[User:Smith36j|Smith36j]] || [[Media:Smith-HW1Soln.pdf | Solutions]]
|-
| Holden || Tyler || [[User:Tholden|tholden]] || [[Media:HoldenAlgHW1.pdf | Solutions]]
|-
| Mracek || James || [[User:jmracek|jmracek]] || [[Media:jmracekHW1.pdf | Solutions]]
|-
|}

==Sample solutions to Homework Assignment 2==

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Holden || Tyler || [[User:tholden|tholden]] || [[Media:HoldenHW2.pdf|Solutions]]
|-
| Mracek || James || [[User:jmracek|jmracek]] || [[Media:jmracekHW2.pdf | Solutions]]
|-
| Smith || Jerrod || [[User:Smith36j|Smith36j]] || [[Media:JMS_MAT1100_HW2.pdf | Solutions]]
|-
| Grigorios || Fournodavlos || [[User:Gregdavlos|Gregdavlos]] || [[Media:GD_MAT1100_HW2.pdf | Solutions]]
|}

==Sample solutions to Homework Assignment 3==

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Holden || Tyler || [[User:tholden|tholden]] || [[Media:HoldenHW3.pdf|Solutions]]
|-
| Thibault || Louis-Philippe || [[User:Lp.thibault|Lp.thibault]] || [[Media:11-1100HW3.pdf|Solutions]]
|-
| Smith|| Jerrod || [[User:Smith36j|Smith36j]] ||[[Media:11-1100_JMS_HW3.pdf |Solutions]]
|}

==Sample solutions to Homework Assignment 4==

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Holden || Tyler || [[User:tholden|tholden]] || [[Media:HoldenHW4.pdf|Solutions]]
|}

User:Tholden

2011-11-29T15:25:24Z

Tholden: /* Assignments */

Hello and welcome to my user page.

I will be using this page to publish my course notes, as well as a hyperlink to pages made before going live.

==Course Notes ==

[http://individual.utoronto.ca/tholden/CourseNotes/Algebra.pdf Tyler's Course Notes]

==Assignments==

[[Media:HoldenAlgHW1.pdf|First Homework Assignment]]

[[Media:HoldenHW2.pdf|Second Homework Assignment]]

[[Media:HoldenHW4.pdf|Fourth Homework Assignment]]

==User Sub-Pages ==

[[User:Tholden/11-1100 Simplicity of the Alternating Group ]]

[[User:Tholden/Simplicity Redirect]]

[[User:Tholden/11-1100/Homework Part 1]]

[[User:Tholden/11-1100/File Repository]]

==Source Code ==

[[User:Tholden/11-1100/HW2 SourceCode|HW2 Source Code]]

==Messages ==

Please leave messages for me here.

File:HoldenHW4.pdf

2011-11-29T15:24:31Z

Tholden:

11-1100/Homework Solutions

2011-11-15T15:20:11Z

Tholden: Fix formatting

11-1100/Navigation

2011-11-15T15:19:15Z

Tholden:

<noinclude>Back to [[11-1100]]. </noinclude>
{| border="1px" cellpadding="1" cellspacing="0" width="100%" style="font-size: small; align: left"
|- align=left
!#
!Week of...
!Notes and Links
|- align=left
|align=center|1
|Sep 12
|[[11-1100/About This Class|About This Class]], [[11-1100/Classnotes for Tuesday September 13|Tuesday]] - Non Commutative Gaussian Elimination, [[11-1100/Classnotes for Thursday September 15|Thursday]] - NCGE completed, the category of groups, images and kernels.
|- align=left
|align=center|2
|Sep 19
|I'll be in {{Home link|Talks/Strasbourg-1109/|Strasbourg}}, class was be taught by [http://www.math.toronto.edu/selick/ Paul Selick]. See my {{Home link|classes/1112/1100-AlgebraI/The_Selick_Week.html|summary}}.
|- align=left
|align=center|3
|Sep 26
|[[11-1100/Class Photo|Class Photo]], [[11-1100/Homework Assignment 1| HW1]], [[11-1100/Homework Assignment 1 Submissions| HW1 Submissions]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 1| HW 1 Solutions]]
|- align=left
|align=center|4
|Oct 3
|[[11-1100/The Simplicity of the Alternating Groups| The Simplicity of the Alternating Groups]]
|- align=left
|align=center|5
|Oct 10
|[[11-1100/Homework Assignment 2|HW2]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 2| HW 2 Solutions]]
|- align=left
|align=center|6
|Oct 18
|[[11-1100/Groups of Order 60 and 84|Groups of Order 60 and 84]]
|- align=left
|align=center|7
|Oct 24
|Extra office hours: Monday 10:30-12:30 (Dror), 5PM-7PM @ Huron 1028 (Stephen). [[11-1100/Term Test|Term Test]] on Tuesday. [[11-1100/Summary for the midterm| Summary for the midterm exam]]. [[11-1100/Term Test Solutions|Term Test - Sample Solutions ]]
|- align=left
|align=center|8
|Oct 31
|[[11-1100/Homework Assignment 3|HW3]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 3| HW 3 Solutions]]
|- align=left
|align=center|9
|Nov 7
|Monday-Tuesday is November Break, {{Pensieve Link|Classes/11-1100/1t2c4w.pdf|One Theorem, Two Corollaries, Four Weeks}}
|- align=left
|align=center|10
|Nov 14
|[[11-1100/Homework Assignment 4|HW4]]
|- align=left
|align=center|11
|Nov 21
|
|- align=left
|align=center|12
|Nov 28
|[[11-1100/Homework Assignment 5|HW5]]
|- align=left
|align=center|13
|Dec 5
|UofT Fall Semester ends Wednesday; our [[10-1100/Final Exam|Final Exam]] will be on Friday
|- align=left
|colspan=3 align=center|[[11-1100/Register of Good Deeds|Register of Good Deeds]]
|- align=left
|colspan=3 align=center|[[Image:11-1100-ClassPhoto.jpg|310px]] [[11-1100/Class Photo|Add your name / see who's in!]]
|- align=left
|colspan=3 align=center|[[Image:10-1100-Splash.png|310px]] See {{Home Link|classes/1112/1100-AlgebraI/NCGE.html|Non Commutative Gaussian Elimination}}
|}

11-1100/Homework Solutions

2011-11-15T15:15:53Z

Tholden:

File:HoldenHW3.pdf

2011-11-15T15:15:35Z

Tholden:

11-1100/Notes

2011-11-06T03:07:50Z

Tholden:

{{11-1100/Navigation}}

==Notes from Lectures==

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Da Silva || Sergio || [[User:Sdasilva|Sdasilva]] || [[Media:October27.pdf | October 27]]
|-
| Holden || Tyler || [[User:tholden|tholden]] || [http://individual.utoronto.ca/tholden/CourseNotes/Algebra.pdf Course Notes]
|-
|}

User:Tholden/11-1100/HW2 SourceCode

2011-10-20T15:27:04Z

Tholden:

The following is a collection of Matlab m-files used for computing quantities of the symmetric group. I apologize as these are not properly commented at this time, though this will hopefully change in the near future. However, all code that is not commented is small and easily parsed.

==Generalized Least Common Multiple==

Matlab has a built in least common multiple command; however, it can only take two inputs at a time. Consequently the following is a recursive algorithm for calculating the least common multiple of a several integers

function mylcm = genLCM(array)

if length(array)<2
mylcm = array;
return;
elseif length(array)==2
mylcm = lcm(array(1),array(2));
return;
else
mylcm = lcm(array(1),genLCM(array(2:end)));
return;
end

==Computing the Orders of Elements in the Symmetric Group==

function orders = compSymOrders(grpSize)

myParts = partitions(grpSize);
orders = zeros(size(myParts,1),1);

for itrow = 1:size(myParts,1)
cycle=[];
for itcol = 1:size(myParts,2)
cycle = [cycle itcol*ones(1,myParts(itrow,itcol))];
end
orders(itrow) = genLCM(cycle);
end

==Smallest Subgroup with Element of Given Order==

function grpSize = smallestSymGrp(order)

answerFound=false;
grpSize = 2;
while ~answerFound && grpSize < 100
orders = compSymOrders(grpSize);
if ~isempty(find(orders==order, 1))
return;
else
grpSize = grpSize + 1;
end
end %end while

==Partitions of an Integer==

The following is a canned algorithm, available from the [http://www.mathworks.com/matlabcentral/fileexchange/12009 Mathworks website], and is not my own work:

function plist = partitions(total_sum,candidate_set,max_count,fixed_count)
% extracts the list of all partitions of a number as integer sums of a list of candidates
% usage: plist = partitions(total_sum,candidate_set)
% usage: plist = partitions(total_sum,candidate_set,max_count,fixed_count)
%
% PARTITIONS solves the money changing problem. E.g.,
% how can you make change for one dollar given coins
% of a given set of denominations. A good reference on
% the general problem is found here:
%
% http://en.wikipedia.org/wiki/Integer_partition
%
% PARTITIONS uses a recursive strategy to enumerate all
% possible partitions of the total_sum. This may be
% highly intensive for large sums or large sets of
% candidates.
%
% arguments: (input)
% total_sum - scalar positive integer (to be partitioned)
%
% BEWARE! a large total_sum can easily cause
% stack problems. For example, the number of
% partitions of 40 is 37338, a set that took 24
% seconds to completely enumerate on my cpu.
%
% candidate_set - (OPTIONAL) vector of (distinct) candidate
% positive integers for the partitions.
%
% Efficiency considerations force me to require
% that the candidates be sorted in non-decreasing
% order. An error is produced otherwise.
%
% DEFAULT: candidate_set = 1:total_sum
%
% BEWARE! large candidate sets can easily cause
% stack problems
%
% max_count - (OPTIONAL) the maximum quantity of any
% candidate in the final sum.
%
% max_count must be either a vector of the
% same length as candidate_set, or a scalar
% that applies to all elements in that set.
%
% DEFAULT = floor(total_sum./candidate_set)
%
% fixed_count - (OPTIONAL) Allows you to specify a fixed
% number of terms in the partitioned sum.
%
% fixed_count must be a positive integer if
% supplied.
%
% DEFAULT = []
%
% arguments: (output)
% plist - array of partitions of total_sum. This is a list
% of the quantity of each element such that
% plist*candidate_set(:) yields total_sum
%
%
% example: Write 9 as an integer combination of the set [1 2 4 7]
%
% partitions(9,[1 2 4 7])
%
% ans =
% 9 0 0 0
% 7 1 0 0
% 5 2 0 0
% 3 3 0 0
% 1 4 0 0
% 5 0 1 0
% 3 1 1 0
% 1 2 1 0
% 1 0 2 0
% 2 0 0 1
% 0 1 0 1
%
% Thus, we can write 9 = 9*1
% or 9 = 1*1 + 4*2
% or 9 = 1*2 + 1*7
% or any of 8 distinct other ways.
%
% There are 11 such ways to write 9 in terms of these
% candidates.
%
%
% example: Change a 1 dollar bill (100 cents) as an integer
% combination of the set [1 5 10 25 50], using no more than
% 4 of any one coin denomination. Note that no pennies will
% be allowed by the maximum constraint.
%
% partitions(100,[1 5 10 25 50],4)
%
% ans =
% 0 4 3 2 0
% 0 2 4 2 0
% 0 3 1 3 0
% 0 1 2 3 0
% 0 0 0 4 0
% 0 4 3 0 1
% 0 2 4 0 1
% 0 3 1 1 1
% 0 1 2 1 1
% 0 0 0 2 1
% 0 0 0 0 2
%
% example: Write 13 as an integer combination of the set [2 4 6 8 10 12]
% (Note that no such combination exists.)
%
% partitions(13,[2 4 6 8 10 12])
%
% ans =
% Empty matrix: 0-by-6
%
%
% example: find all possible ways to write 100 as a sum of EXACTLY 4
% squares of the integers 1:9.
%
% partitions(100,(1:9).^2,[],4)
% ans =
% 0 0 0 0 4 0 0 0 0
% 1 0 0 0 2 0 1 0 0
% 2 0 0 0 0 0 2 0 0
% 0 1 0 2 0 0 0 1 0
% 1 0 2 0 0 0 0 0 1
%
%
% Author: John D'Errico
% e-mail: woodchips@rochester.rr.com
% Release: 2
% Release date: 7/15/08

% default for candidate_set
if (nargin<2) || isempty(candidate_set)
candidate_set = 1:total_sum;
end

% how many candidates are there
n = length(candidate_set);

% error checks
if any(candidate_set<=0)
error('All members of candidate_set must be > 0')
end
% candidates must be sorted in increasng order
if any(diff(candidate_set)<0)
error('Efficiency requires that candidate_set be sorted')
end

% check for a max_count. do we supply a default?
if (nargin<3) || isempty(max_count)
% how high do we need look?
max_count = floor(total_sum./candidate_set);
elseif length(max_count)==1
% if a scalar was provided, then turn it into a vector
max_count = repmat(max_count,1,n);
end

% check for a fixed_count
if (nargin<4) || isempty(fixed_count)
fixed_count = [];
elseif (fixed_count<0) || (fixed_count~=round(fixed_count))
error('fixed_count must be a positive integer if supplied')
end

% check for degenerate cases
if isempty(fixed_count)
if total_sum == 0
plist = zeros(1,n);
return
elseif (n == 0)
plist = [];
return
elseif (n == 1)
% only one element in the set. can we form
% total_sum from it as an integer multiple?
p = total_sum/candidate_set;
if (p==fix(p)) && (p<=max_count)
plist = p;
else
plist = [];
end
return
end
else
% there was a fixed_count supplied
if (total_sum == 0) && (fixed_count == 0)
plist = zeros(1,n);
return
elseif (n == 0) || (fixed_count <= 0)
plist = [];
return
elseif (n==1)
% there must be a non-zero fixed_count, since
% we did not trip the last test. since there
% is only one candidate in the set, will it work?
if (fixed_count*candidate_set) == total_sum
plist = fixed_count;
else
plist = [];
end
return
end
end

% finally, we can do some work. start with the
% largest element and work backwards
m = max_count(end);
% do we need to back off on m?
c = candidate_set(end);
m = min([m,floor(total_sum/c),fixed_count]);

plist = zeros(0,n);
for i = 0:m
temp = partitions(total_sum - i*c, ...
candidate_set(1:(end-1)), ...
max_count(1:(end-1)),fixed_count-i);
plist = [plist;[temp,repmat(i,size(temp,1),1)]]; %#ok
end

User:Tholden/11-1100/HW2 SourceCode

2011-10-20T15:25:43Z

Tholden:

The following is a collection of Matlab m-files used for computing quantities of the symmetric group. I apologize as these are not properly commented at this time, though this will hopefully change in the near future. However, all code that is not commented is small and easily parsed.

==Partitions of an Integer==

The following is a canned algorithm, available from the [http://www.mathworks.com/matlabcentral/fileexchange/12009 Mathworks website], and is not my own work:

==Generalized Least Common Multiple==

Matlab has a built in least common multiple command; however, it can only take two inputs at a time. Consequently the following is a recursive algorithm for calculating the least common multiple of a several integers

function mylcm = genLCM(array)

if length(array)<2
mylcm = array;
return;
elseif length(array)==2
mylcm = lcm(array(1),array(2));
return;
else
mylcm = lcm(array(1),genLCM(array(2:end)));
return;
end

==Computing the Orders of Elements in the Symmetric Group==

function orders = compSymOrders(grpSize)

myParts = partitions(grpSize);
orders = zeros(size(myParts,1),1);

for itrow = 1:size(myParts,1)
cycle=[];
for itcol = 1:size(myParts,2)
cycle = [cycle itcol*ones(1,myParts(itrow,itcol))];
end
orders(itrow) = genLCM(cycle);
end

==Smallest Subgroup with Element of Given Order==

function grpSize = smallestSymGrp(order)

answerFound=false;
grpSize = 2;
while ~answerFound && grpSize < 100
orders = compSymOrders(grpSize);
if ~isempty(find(orders==order, 1))
return;
else
grpSize = grpSize + 1;
end
end %end while

function plist = partitions(total_sum,candidate_set,max_count,fixed_count)
% extracts the list of all partitions of a number as integer sums of a list of candidates
% usage: plist = partitions(total_sum,candidate_set)
% usage: plist = partitions(total_sum,candidate_set,max_count,fixed_count)
%
% PARTITIONS solves the money changing problem. E.g.,
% how can you make change for one dollar given coins
% of a given set of denominations. A good reference on
% the general problem is found here:
%
% http://en.wikipedia.org/wiki/Integer_partition
%
% PARTITIONS uses a recursive strategy to enumerate all
% possible partitions of the total_sum. This may be
% highly intensive for large sums or large sets of
% candidates.
%
% arguments: (input)
% total_sum - scalar positive integer (to be partitioned)
%
% BEWARE! a large total_sum can easily cause
% stack problems. For example, the number of
% partitions of 40 is 37338, a set that took 24
% seconds to completely enumerate on my cpu.
%
% candidate_set - (OPTIONAL) vector of (distinct) candidate
% positive integers for the partitions.
%
% Efficiency considerations force me to require
% that the candidates be sorted in non-decreasing
% order. An error is produced otherwise.
%
% DEFAULT: candidate_set = 1:total_sum
%
% BEWARE! large candidate sets can easily cause
% stack problems
%
% max_count - (OPTIONAL) the maximum quantity of any
% candidate in the final sum.
%
% max_count must be either a vector of the
% same length as candidate_set, or a scalar
% that applies to all elements in that set.
%
% DEFAULT = floor(total_sum./candidate_set)
%
% fixed_count - (OPTIONAL) Allows you to specify a fixed
% number of terms in the partitioned sum.
%
% fixed_count must be a positive integer if
% supplied.
%
% DEFAULT = []
%
% arguments: (output)
% plist - array of partitions of total_sum. This is a list
% of the quantity of each element such that
% plist*candidate_set(:) yields total_sum
%
%
% example: Write 9 as an integer combination of the set [1 2 4 7]
%
% partitions(9,[1 2 4 7])
%
% ans =
% 9 0 0 0
% 7 1 0 0
% 5 2 0 0
% 3 3 0 0
% 1 4 0 0
% 5 0 1 0
% 3 1 1 0
% 1 2 1 0
% 1 0 2 0
% 2 0 0 1
% 0 1 0 1
%
% Thus, we can write 9 = 9*1
% or 9 = 1*1 + 4*2
% or 9 = 1*2 + 1*7
% or any of 8 distinct other ways.
%
% There are 11 such ways to write 9 in terms of these
% candidates.
%
%
% example: Change a 1 dollar bill (100 cents) as an integer
% combination of the set [1 5 10 25 50], using no more than
% 4 of any one coin denomination. Note that no pennies will
% be allowed by the maximum constraint.
%
% partitions(100,[1 5 10 25 50],4)
%
% ans =
% 0 4 3 2 0
% 0 2 4 2 0
% 0 3 1 3 0
% 0 1 2 3 0
% 0 0 0 4 0
% 0 4 3 0 1
% 0 2 4 0 1
% 0 3 1 1 1
% 0 1 2 1 1
% 0 0 0 2 1
% 0 0 0 0 2
%
% example: Write 13 as an integer combination of the set [2 4 6 8 10 12]
% (Note that no such combination exists.)
%
% partitions(13,[2 4 6 8 10 12])
%
% ans =
% Empty matrix: 0-by-6
%
%
% example: find all possible ways to write 100 as a sum of EXACTLY 4
% squares of the integers 1:9.
%
% partitions(100,(1:9).^2,[],4)
% ans =
% 0 0 0 0 4 0 0 0 0
% 1 0 0 0 2 0 1 0 0
% 2 0 0 0 0 0 2 0 0
% 0 1 0 2 0 0 0 1 0
% 1 0 2 0 0 0 0 0 1
%
%
% Author: John D'Errico
% e-mail: woodchips@rochester.rr.com
% Release: 2
% Release date: 7/15/08

% default for candidate_set
if (nargin<2) || isempty(candidate_set)
candidate_set = 1:total_sum;
end

% how many candidates are there
n = length(candidate_set);

% error checks
if any(candidate_set<=0)
error('All members of candidate_set must be > 0')
end
% candidates must be sorted in increasng order
if any(diff(candidate_set)<0)
error('Efficiency requires that candidate_set be sorted')
end

% check for a max_count. do we supply a default?
if (nargin<3) || isempty(max_count)
% how high do we need look?
max_count = floor(total_sum./candidate_set);
elseif length(max_count)==1
% if a scalar was provided, then turn it into a vector
max_count = repmat(max_count,1,n);
end

% check for a fixed_count
if (nargin<4) || isempty(fixed_count)
fixed_count = [];
elseif (fixed_count<0) || (fixed_count~=round(fixed_count))
error('fixed_count must be a positive integer if supplied')
end

% check for degenerate cases
if isempty(fixed_count)
if total_sum == 0
plist = zeros(1,n);
return
elseif (n == 0)
plist = [];
return
elseif (n == 1)
% only one element in the set. can we form
% total_sum from it as an integer multiple?
p = total_sum/candidate_set;
if (p==fix(p)) && (p<=max_count)
plist = p;
else
plist = [];
end
return
end
else
% there was a fixed_count supplied
if (total_sum == 0) && (fixed_count == 0)
plist = zeros(1,n);
return
elseif (n == 0) || (fixed_count <= 0)
plist = [];
return
elseif (n==1)
% there must be a non-zero fixed_count, since
% we did not trip the last test. since there
% is only one candidate in the set, will it work?
if (fixed_count*candidate_set) == total_sum
plist = fixed_count;
else
plist = [];
end
return
end
end

% finally, we can do some work. start with the
% largest element and work backwards
m = max_count(end);
% do we need to back off on m?
c = candidate_set(end);
m = min([m,floor(total_sum/c),fixed_count]);

plist = zeros(0,n);
for i = 0:m
temp = partitions(total_sum - i*c, ...
candidate_set(1:(end-1)), ...
max_count(1:(end-1)),fixed_count-i);
plist = [plist;[temp,repmat(i,size(temp,1),1)]]; %#ok
end

User:Tholden

2011-10-20T14:58:58Z

Tholden:

Hello and welcome to my user page.

I will be using this page to publish my course notes, as well as a hyperlink to pages made before going live.

==Course Notes ==

[http://individual.utoronto.ca/tholden/CourseNotes/Algebra.pdf Tyler's Course Notes]

==Assignments==

[[Media:HoldenAlgHW1.pdf|First Homework Assignment]]

[[Media:HoldenHW2.pdf|Second Homework Assignment]]

==User Sub-Pages ==

[[User:Tholden/11-1100 Simplicity of the Alternating Group ]]

[[User:Tholden/Simplicity Redirect]]

[[User:Tholden/11-1100/Homework Part 1]]

[[User:Tholden/11-1100/File Repository]]

==Source Code ==

[[User:Tholden/11-1100/HW2 SourceCode|HW2 Source Code]]

==Messages ==

Please leave messages for me here.

11-1100/Navigation

2011-10-20T14:36:50Z

Tholden:

<noinclude>Back to [[11-1100]]. </noinclude>
{| border="1px" cellpadding="1" cellspacing="0" width="100%" style="font-size: small; align: left"
|- align=left
!#
!Week of...
!Notes and Links
|- align=left
|align=center|1
|Sep 12
|[[11-1100/About This Class|About This Class]], [[11-1100/Classnotes for Tuesday September 13|Tuesday]] - Non Commutative Gaussian Elimination, [[11-1100/Classnotes for Thursday September 15|Thursday]] - NCGE completed, the category of groups, images and kernels.
|- align=left
|align=center|2
|Sep 19
|I'll be in {{Home link|Talks/Strasbourg-1109/|Strasbourg}}, class was be taught by [http://www.math.toronto.edu/selick/ Paul Selick]. See my {{Home link|classes/1112/1100-AlgebraI/The_Selick_Week.html|summary}}.
|- align=left
|align=center|3
|Sep 26
|[[11-1100/Class Photo|Class Photo]], [[11-1100/Homework Assignment 1| HW1]], [[11-1100/Homework Assignment 1 Submissions| HW1 Submissions]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 1| HW 1 Solutions]]
|- align=left
|align=center|4
|Oct 3
|[[11-1100/The Simplicity of the Alternating Groups| The Simplicity of the Alternating Groups]]
|- align=left
|align=center|5
|Oct 10
|[[11-1100/Homework Assignment 2|HW2]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 2| HW 2 Solutions]]
|- align=left
|align=center|6
|Oct 18
|
|- align=left
|align=center|7
|Oct 24
|Extra office hours: Monday 10:30-12:30 (Dror), 5PM-7PM @ Huron 1028 (Stephen). [[11-1100/Term Test|Term Test]] on Tuesday
|- align=left
|align=center|8
|Oct 31
|[[11-1100/Homework Assignment 3|HW3]]
|- align=left
|align=center|9
|Nov 7
|Monday-Tuesday is November Break
|- align=left
|align=center|10
|Nov 14
|[[11-1100/Homework Assignment 4|HW4]]
|- align=left
|align=center|11
|Nov 21
|
|- align=left
|align=center|12
|Nov 28
|[[11-1100/Homework Assignment 5|HW5]]
|- align=left
|align=center|13
|Dec 5
|UofT Fall Semester ends Wednesday; our [[10-1100/Final Exam|Final Exam]] will be on Friday
|- align=left
|colspan=3 align=center|[[11-1100/Register of Good Deeds|Register of Good Deeds]]
|- align=left
|colspan=3 align=center|[[Image:11-1100-ClassPhoto.jpg|310px]] [[11-1100/Class Photo|Add your name / see who's in!]]
|- align=left
|colspan=3 align=center|[[Image:10-1100-Splash.png|310px]] See {{Home Link|classes/1112/1100-AlgebraI/NCGE.html|Non Commutative Gaussian Elimination}}
|}

11-1100/Homework Solutions

2011-10-20T14:31:15Z

Tholden:

User:Tholden

2011-10-20T14:26:49Z

Tholden:

Hello and welcome to my user page.

I will be using this page to publish my course notes, as well as a hyperlink to pages made before going live.

==Course Notes ==

[http://individual.utoronto.ca/tholden/CourseNotes/Algebra.pdf Tyler's Course Notes]

==Assignments==

[[Media:HoldenAlgHW1.pdf|First Homework Assignment]]

[[Media:HoldenHW2.pdf|Second Homework Assignment]]

==User Sub-Pages ==

[[User:Tholden/11-1100 Simplicity of the Alternating Group ]]

[[User:Tholden/Simplicity Redirect]]

[[User:Tholden/11-1100/Homework Part 1]]

[[User:Tholden/11-1100/File Repository]]

==Messages ==

Please leave messages for me here.

File:HoldenHW2.pdf

2011-10-20T14:25:23Z

Tholden:

11-1100/Navigation

2011-10-13T15:56:04Z

Tholden: Added anchor to sample solution subpage

<noinclude>Back to [[11-1100]]. </noinclude>
{| border="1px" cellpadding="1" cellspacing="0" width="100%" style="font-size: small; align: left"
|- align=left
!#
!Week of...
!Notes and Links
|- align=left
|align=center|1
|Sep 12
|[[11-1100/About This Class|About This Class]], [[11-1100/Classnotes for Tuesday September 13|Tuesday]] - Non Commutative Gaussian Elimination, [[11-1100/Classnotes for Thursday September 15|Thursday]] - NCGE completed, the category of groups, images and kernels.
|- align=left
|align=center|2
|Sep 19
|I'll be in {{Home link|Talks/Strasbourg-1109/|Strasbourg}}, class was be taught by [http://www.math.toronto.edu/selick/ Paul Selick]. See my {{Home link|classes/1112/1100-AlgebraI/The_Selick_Week.html|summary}}.
|- align=left
|align=center|3
|Sep 26
|[[11-1100/Class Photo|Class Photo]], [[11-1100/Homework Assignment 1| HW1]], [[11-1100/Homework Assignment 1 Submissions| HW1 Submissions]], [[11-1100/Homework Solutions#Sample solutions to Homework Assignment 1| HW 1 Solutions]]
|- align=left
|align=center|4
|Oct 3
|[[11-1100/The Simplicity of the Alternating Groups| The Simplicity of the Alternating Groups]]
|- align=left
|align=center|5
|Oct 10
|[[11-1100/Homework Assignment 2|HW2]]
|- align=left
|align=center|6
|Oct 18
|
|- align=left
|align=center|7
|Oct 24
|[[11-1100/Term Test|Term Test]]
|- align=left
|align=center|8
|Oct 31
|[[11-1100/Homework Assignment 3|HW3]]
|- align=left
|align=center|9
|Nov 7
|Monday-Tuesday is November Break
|- align=left
|align=center|10
|Nov 14
|[[11-1100/Homework Assignment 4|HW4]]
|- align=left
|align=center|11
|Nov 21
|
|- align=left
|align=center|12
|Nov 28
|[[11-1100/Homework Assignment 5|HW5]]
|- align=left
|align=center|13
|Dec 5
|UofT Fall Semester ends Wednesday; our [[10-1100/Final Exam|Final Exam]] will be on Friday
|- align=left
|colspan=3 align=center|[[11-1100/Register of Good Deeds|Register of Good Deeds]]
|- align=left
|colspan=3 align=center|[[Image:11-1100-ClassPhoto.jpg|310px]] [[11-1100/Class Photo|Add your name / see who's in!]]
|- align=left
|colspan=3 align=center|[[Image:10-1100-Splash.png|310px]] See {{Home Link|classes/1112/1100-AlgebraI/NCGE.html|Non Commutative Gaussian Elimination}}
|}

11-1100/Homework Solutions

2011-10-13T15:54:09Z

Tholden:

11-1100/Homework Solutions

2011-10-13T15:53:04Z

Tholden: Made section headers linkable

==Sample solutions to Homework Assignment 1==

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Smith || Jerrod || [[User:Smith36j|Smith36j]] || [[Media:Smith-HW1Soln.pdf | here]]
|-
| Holden || Tyler || [[User:Tholden|tholden]] || [[Media:HoldenAlgHW1.pdf | Solutions]]
|-
|}

==Sample solutions to Homework Assignment 2==

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Last ||First|| User || Link
|-
|}

Talk:11-1100/Homework Solutions

2011-10-13T15:52:07Z

Tholden:

==Changing Format==

I like the idea of this page, though I think I may change its format a little bit. In particular, if we add hyperlinks from the navigation bar, it would be useful if they went directly to the pertinent assignment. To do this, it will be necessary to change the section headers to be linkable. [[User:Tholden|Tholden]] 11:52, 13 October 2011 (EDT)

User:Josh.seaton

2011-10-13T15:42:09Z

Tholden:

[[Assignment I - Permutation Counting]]

==Messages==

Hey. Not sure if you were in lecture today, but Dror warned that pages without the 11-1100 tag would be removed. Consequently, I have moved your HW1 Submission page so that it will not be deleted.[[User:Tholden|Tholden]] 11:42, 13 October 2011 (EDT)

Assignment I - Permutation Counting

2011-10-13T15:39:56Z

Tholden: Assignment I - Permutation Counting moved to 11-1100/Assignment I - Permutation Counting: Adding class tag so page will not be deleted.

#redirect [[11-1100/Assignment I - Permutation Counting]]

11-1100/Assignment I - Permutation Counting

2011-10-13T15:39:56Z

Tholden: Assignment I - Permutation Counting moved to 11-1100/Assignment I - Permutation Counting

The puzzle that I have chosen is a 2x2x3 variant of the Rubik's cube. Below is a sketch of how I have labelled it.

[[2x2x3 Permutation Puzzle]]

Here are the generators:

g1 = [1,2,3,4,12,22,7,8,6,11,21,28,13,14,15,16,17,18,5,10,20,27,23,24,25,26,9,19,29,30,31,32] <math> \equiv </math> (28,19,5,12)(9,6,22,27)(10,11,21,20)

g2 = [1,2,13,23,5,6,7,4,9,10,11,12,30,14,15,16,17,3,19,20,21,22,29,24,25,26,27,28,8,18,31,32] <math> \equiv </math> (18,3,13,30)(8,4,23,29)

g3 = [14,24,3,4,5,6,2,8,9,10,11,12,13,32,16,26,1,18,19,20,21,22,23,31,15,25,27,28,29,30,7,17] <math> \equiv </math> (32,17,1,14)(24,31,7,2)(16,26,25,15)

g4 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,22,23,24,25,26,17,18,19,20,21,32,31,30,29,28,27] <math> \equiv </math> (17,22)(18,23)(24,19)(25,20)(26,21)(32,27)(28,31)(29,30)

This is the Python code used to implement the NCGE algorithm for the 2x2x3 puzzle.

[[NCGE Python Code]]

First, the class of permutations is defined, along with how to multiply them and take their inverses. Then, algorithm is spelled out.

The algorithm yields that their are '''39016857600''' different configurations of the 2x2x3 puzzle. The implementation was subsequently checked with the Rubik's cube generators given on [http://www.math.toronto.edu/~drorbn/Talks/Mathcamp-0907/NCGE.pdf the handout] and the correct numbers were outputted.

11-1100/Homework Solutions

2011-10-13T14:31:57Z

Tholden: Added my solution set.

Sample solutions to Homework Assignment 1

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Smith || Jerrod || [[User:Smith36j|Smith36j]] || [[Media:Smith-HW1Soln.pdf | here]]
|-
| Holden || Tyler || [[User:Tholden|tholden]] || [[Media:HoldenAlgHW1.pdf | Solutions]]
|-
|}

Sample solutions to Homework Assignment 2

{| border="1" align = "center"
|+ Please Input Your Information Here
! scope="col" | Last Name
! scope="col" | First Name
! scope="col" | User ID
! scope="col" | Link to Submission
|-
| Last ||First|| User || Link
|-
|}

User:Tholden

2011-10-11T14:16:12Z

Tholden:

Hello and welcome to my user page.

I will be using this page to publish my course notes, as well as a hyperlink to pages made before going live.

==Course Notes ==

[http://individual.utoronto.ca/tholden/CourseNotes/Algebra.pdf Tyler's Course Notes]

==Assignments==

[[Media:HoldenAlgHW1.pdf|First Homework Assignment]]

==User Sub-Pages ==

[[User:Tholden/11-1100 Simplicity of the Alternating Group ]]

[[User:Tholden/Simplicity Redirect]]

[[User:Tholden/11-1100/Homework Part 1]]

[[User:Tholden/11-1100/File Repository]]

==Messages ==

Please leave messages for me here.

File:HoldenAlgHW1.pdf

2011-10-11T14:15:10Z

Tholden:

MATLAB Code for Non-Commutative Gaussian Elimination

2011-10-10T22:36:05Z

Tholden: MATLAB Code for Non-Commutative Gaussian Elimination moved to 11-1100/MATLAB Code for Non-Commutative Gaussian Elimination: Adding class tag

#redirect [[11-1100/MATLAB Code for Non-Commutative Gaussian Elimination]]

11-1100/MATLAB Code for Non-Commutative Gaussian Elimination

2011-10-10T22:36:05Z

Tholden: MATLAB Code for Non-Commutative Gaussian Elimination moved to 11-1100/MATLAB Code for Non-Commutative Gaussian Elimination

I wrote a MATLAB script to carry out the non-commutative Gaussian elimination algorithm. Specifically, I have chosen to use the problem of the 2x2x2 pocket cube; however, this algorithm may be easily adapted for finding the solution to other combinatorial puzzles. The structure of the script is very similar to Dror's code. I call the "Feed" script for each generator of the puzzle, but the built in recursion takes care of finding an empty spot in the table, as well as all the messiness of feeding all products of everything in the table.

My solution is slightly different, however, in that I carry out group operations using matrix representations of the generators. I picked a representation of the group in which every matrix was comprised of only 1's and 0's. This is useful, because it easily allows me to compute products, inverses, and find pivot points. The representation of which I write can be constructed by considering the action of <math>S_{n}</math> on an n-dimensional vector space. As an example, consider the permutation <math>g = (1 2 3) \in S_{3}</math>. This permutation takes 1 -> 2, 2 -> 3, and 3 -> 1; thus, the matrix representation of this operation is:

[[Image:Matrix.jpg]]

From a computational standpoint this is kind of a bad idea, but I figured it was something different and no one else was likely to try this solution.

First, I needed to define the problem for the computer. I picked an enumeration of the faces of the 2x2x2 cube, and wrote out the generators of the group based on this enumeration. The rotations of the faces are the generators for the group operations. Since the cube has six faces which can be rotated, there are six generators. The group I am dealing with is a subgroup of the permutations on 24 elements because a 2x2x2 cube has 6*4 = 24 faces. The following figure shows how I chose my enumeration of the cube faces:

[[Image:cubelayout.jpg]]
(A) This sub-figure demonstrates the enumeration of the faces that I adopted. (B) An image of the Pocket Cube. (C) A list of the group generators (face rotations).

Note that since the pocket cube has no faces which would fix its overall orientation, there are actually 24 equivalent cube configurations per permutation; thus, whatever answer is obtained at the end needs to be divided by 24 to give the actual group order.

I split the program into 3 parts. BG2.m is a short script which builds the matrix representations of the generators. Feed.m is a script which carries out the non-commutative Gaussian elimination algorithm. Finally, PocketCube.m is a parent script in which the generators of the pocket cube problem are defined, the Feed algorithm is called for each generator, and once the lookup table is finally constructed, the order of the group is output.

[[Image:BG2.jpg]]
[[Image:Feed.jpg]]
[[Image:PocketCube.jpg]]

At the MATLAB prompt, the following set of commands were used to run my program:

[[Image:output.jpg]]
[[Image:pivot.jpg]]

The above plot is displaying the non-zero entries in the NCGE table. I calculate the order of the Pocket Cube group to be 3,674,160. I also ran the program using a restricted subset of the generators. Interestingly, the entire pocket cube group can be generated using only 3 of the face rotations!

User:Dsoukup

2011-10-10T22:31:55Z

Tholden:

==Message==

Hey Dan. Hope you don't mind, but I jacked your [[11-1100/Homework Assignment 1 Submissions|solution's page]] and reformatted it so that everybody could use it. [[User:Tholden|Tholden]] 18:31, 10 October 2011 (EDT)

11-1100/Navigation

2011-10-10T22:22:35Z

Tholden: Changed Solutions -> Submissions

<noinclude>Back to [[11-1100]]. </noinclude>
{| border="1px" cellpadding="1" cellspacing="0" width="100%" style="font-size: small; align: left"
|- align=left
!#
!Week of...
!Notes and Links
|- align=left
|align=center|1
|Sep 12
|[[11-1100/About This Class|About This Class]], [[11-1100/Classnotes for Tuesday September 13|Tuesday]] - Non Commutative Gaussian Elimination, [[11-1100/Classnotes for Thursday September 15|Thursday]] - NCGE completed, the category of groups, images and kernels.
|- align=left
|align=center|2
|Sep 19
|I'll be in {{Home link|Talks/Strasbourg-1109/|Strasbourg}}, class was be taught by [http://www.math.toronto.edu/selick/ Paul Selick]. See my {{Home link|classes/1112/1100-AlgebraI/The_Selick_Week.html|summary}}.
|- align=left
|align=center|3
|Sep 26
|[[11-1100/Class Photo|Class Photo]], [[11-1100/Homework Assignment 1| HW1]], [[11-1100/Homework Assignment 1 Submissions| HW1 Submissions]]
|- align=left
|align=center|4
|Oct 3
|[[11-1100/The Simplicity of the Alternating Groups| The Simplicity of the Alternating Groups]]
|- align=left
|align=center|5
|Oct 10
|[[11-1100/Homework Assignment 2|HW2]]
|- align=left
|align=center|6
|Oct 18
|
|- align=left
|align=center|7
|Oct 24
|[[11-1100/Term Test|Term Test]]
|- align=left
|align=center|8
|Oct 31
|[[11-1100/Homework Assignment 3|HW3]]
|- align=left
|align=center|9
|Nov 7
|Monday-Tuesday is November Break
|- align=left
|align=center|10
|Nov 14
|[[11-1100/Homework Assignment 4|HW4]]
|- align=left
|align=center|11
|Nov 21
|
|- align=left
|align=center|12
|Nov 28
|[[11-1100/Homework Assignment 5|HW5]]
|- align=left
|align=center|13
|Dec 5
|UofT Fall Semester ends Wednesday; our [[10-1100/Final Exam|Final Exam]] will be on Friday
|- align=left
|colspan=3 align=center|[[11-1100/Register of Good Deeds|Register of Good Deeds]]
|- align=left
|colspan=3 align=center|[[Image:11-1100-ClassPhoto.jpg|310px]] [[11-1100/Class Photo|Add your name / see who's in!]]
|- align=left
|colspan=3 align=center|[[Image:10-1100-Splash.png|310px]] See {{Home Link|classes/1112/1100-AlgebraI/NCGE.html|Non Commutative Gaussian Elimination}}
|}

11-1100/Homework Assignment 1 Solutions

2011-10-10T22:21:41Z

Tholden: 11-1100/Homework Assignment 1 Solutions moved to 11-1100/Homework Assignment 1 Submissions: Possible naming conflict if official solutions are posted.

#redirect [[11-1100/Homework Assignment 1 Submissions]]

Talk:11-1100/Homework Assignment 1 Solutions

2011-10-10T22:20:42Z

Tholden: Talk:11-1100/Homework Assignment 1 Solutions moved to Talk:11-1100/Homework Assignment 1 Submissions: Possible name conflict in the event official solutions to the problem sets are posted.

#redirect [[Talk:11-1100/Homework Assignment 1 Submissions]]

Talk:11-1100/Homework Assignment 1 Submissions

2011-10-10T22:20:42Z

Tholden: Talk:11-1100/Homework Assignment 1 Solutions moved to Talk:11-1100/Homework Assignment 1 Submissions

==Moving Page==

I don't think this is appropriately named. If Dror wants to post actual solutions, then we'll have a naming conflict. I'm going to change this page to submissions instead. [[User:Tholden|Tholden]] 18:20, 10 October 2011 (EDT)

Talk:11-1100/Homework Assignment 1 Submissions

2011-10-10T22:20:10Z

Tholden:

User:Tholden/11-1100/Homework Part 1

2011-10-10T18:43:31Z

Tholden: /* 2x2x2 Rubik's cube */

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

User:Tholden/11-1100/File Repository

2011-10-10T18:37:58Z

Tholden:

Any files located on any of my pages can be found below. In particular, since the wiki server does not like adding .m files, these are hyperlinked to my ftp page.

[http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/addCycle2Img.m addCycle2Img.m] - A Matlab M-file that converts from cycle notation to "image" notation.

[http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/Dodecahedron2.m Dodecahedron.m] - A Matlab M-file that generates the renders a three-dimensional image of the dodecahedron along with a star pattern on each face and a numbering scheme.

[http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/Dodecahedron2.m Dodecahedron2.m] - A Matlab M-file that generates the input parameters for use in solving the Megaminx problem in conjunction with NonCommGaussElim.m.

[http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/SimpleCube.m SimpleCube.m] - A Matlab M-file that generates the renders a three-dimensional image of the pocket cube along with a numbering scheme.

[http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/SimpleCube2.m SimpleCube2.m] - A Matlab M-file that generates the input parameters for use in solving the <math> 2 \times 2 \times 2 </math> Rubik's cube problem in conjunction with NonCommGaussElim.m.

[http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/RotatingCube.gif RotatingCube Animation] - A GIF file that animates the sticker choice for the pocket cube.

[http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/MegaminxNumbering.gif RotatingCube Animation] - A GIF file that animates the sticker choice for the Megaminx permutation problem.

User:Jmracek

2011-10-10T18:32:00Z

Tholden:

Hello all, and welcome to my user page. Here you will find notes, my assignment solutions, and assorted other bits that I find interesting.

[[MATLAB Code for Non-Commutative Gaussian Elimination]]

==Messages ==

Hey buddy. You might want to move your page so that that it has 11-1100 as the prefix. [[User:Tholden|Tholden]] 14:32, 10 October 2011 (EDT)

User:Tholden/11-1100/Homework Part 1

2011-10-10T18:30:41Z

Tholden: /* Megaminx */

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:

>> 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

User:Tholden/11-1100/Homework Part 1

2011-10-10T18:28:52Z

Tholden: /* Megaminx */

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:

>> 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>.

File:Megaminx.jpg

2011-10-10T17:52:41Z

Tholden: Picture of Megaminx Permutation Puzzle

Picture of Megaminx Permutation Puzzle

User:Tholden/11-1100/Homework Part 1

2011-10-10T17:47:41Z

Tholden: /* 2x2x2 Rubik's cube */

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:

>> 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==

User:Tholden/11-1100/Homework Part 1

2011-10-10T17:42:48Z

Tholden: /* <math> 2 \times 2 \times 2 </math> Rubik's cube */

User:Tholden/11-1100/Homework Part 1

2011-10-10T17:42:23Z

Tholden: /* <math> 2 \times 2 \times 2 </math> Rubik's cube */

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);

==<math> 2 \times 2 \times 2 </math> 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>

==Megaminx==

User:Tholden/11-1100/File Repository

2011-10-10T17:33:58Z

Tholden:

File:2x2x2CubeSmall.jpg

2011-10-10T17:20:09Z

Tholden: A high resolution picture of the 2x2x2 Rubik's cube.

A high resolution picture of the 2x2x2 Rubik's cube.

User:Tholden/11-1100/Homework Part 1

2011-10-10T16:27:25Z

Tholden:

User:Tholden/11-1100/File Repository

2011-10-10T16:19:19Z

Tholden:

User:Tholden

2011-10-10T16:15:58Z

Tholden:

User:Tholden/11-1100/Homework Part 1

2011-10-10T15:56:00Z

Tholden: