Drorbn - User contributions [en]

File:Study notes.pdf

2011-12-09T02:01:08Z

Jmracek:

11-1100

2011-12-09T02:00:54Z

Jmracek:

__NOEDITSECTION__
__NOTOC__
{{11-1100/Navigation}}
==Core Algebra I==
===Department of Mathematics, University of Toronto, Fall 2011===

{{11-1100/Crucial Information}}

===Texts===
Lang's ''Algebra'', Selick's [http://www.math.toronto.edu/mat1100/ lecture notes for this class], Dummit and Foote's ''Abstract Algebra'', Hungerford's ''Abstract Algebra''.

===Further Resources===

* [http://www.math.utoronto.ca/cms/graduate-program/ Graduate Studies] at the [http://www.math.toronto.edu/ UofT Math Department]. In particular, [http://www.math.utoronto.ca/cms/tentative-2010-2011-graduate-course-descriptions/ Graduate Course Descriptions].

* My {{Pensieve Link|Classes/11-1100/|11-1100 notebook}}.

* My [[10-1100|2010 Class]].

* Paul Selick's [http://www.math.toronto.edu/mat1100/ 2007 class] ([[11-1100/Errata_to_Prof._Selick's_Notes|Errata]]).

* Some (mostly complete) notes from last year's class: [[10-1100-Notes]].

* Some blackboard shots start at {{BBS Link|11_1100-111024-110239.jpg}}.

{{Template:11-1100:Dror/Students Divider}}

* Student solutions to homework problems: [[11-1100/Homework Solutions]].

* Student notes from class: [[11-1100/Notes]].

* Very cool video explaining how to visualize some concepts in group theory ([[User:jmracek]]): [http://web.bentley.edu/empl/c/ncarter/vgt/VisualizingGroupTheory-320x240.mov]

* Summary of the course ([[User: Lp.thibault]]): [[Media:11-1100_Summary6.pdf|Summary of the course]].

* Read Along on material covering Modules (Dummit Foote and Lang): [[User:Vanessa.foster]]

* A rough and ready Perl script for [[Computing GCDs over the Gaussian Integers]]. (I provide no proof of correctness, all faults are my own, etc. -- [[User:pgadey]])

* Some [[Media:study_notes.pdf]] summarizing the proofs we did in class pertaining to rings (jmracek)

[[Image:xkcdsettheory.jpg]]
Link: [[http://xkcd.com/982/]]

11-1100

2011-12-09T01:59:45Z

Jmracek:

__NOEDITSECTION__
__NOTOC__
{{11-1100/Navigation}}
==Core Algebra I==
===Department of Mathematics, University of Toronto, Fall 2011===

{{11-1100/Crucial Information}}

===Texts===
Lang's ''Algebra'', Selick's [http://www.math.toronto.edu/mat1100/ lecture notes for this class], Dummit and Foote's ''Abstract Algebra'', Hungerford's ''Abstract Algebra''.

===Further Resources===

* [http://www.math.utoronto.ca/cms/graduate-program/ Graduate Studies] at the [http://www.math.toronto.edu/ UofT Math Department]. In particular, [http://www.math.utoronto.ca/cms/tentative-2010-2011-graduate-course-descriptions/ Graduate Course Descriptions].

* My {{Pensieve Link|Classes/11-1100/|11-1100 notebook}}.

* My [[10-1100|2010 Class]].

* Paul Selick's [http://www.math.toronto.edu/mat1100/ 2007 class] ([[11-1100/Errata_to_Prof._Selick's_Notes|Errata]]).

* Some (mostly complete) notes from last year's class: [[10-1100-Notes]].

* Some blackboard shots start at {{BBS Link|11_1100-111024-110239.jpg}}.

{{Template:11-1100:Dror/Students Divider}}

* Student solutions to homework problems: [[11-1100/Homework Solutions]].

* Student notes from class: [[11-1100/Notes]].

* Very cool video explaining how to visualize some concepts in group theory ([[User:jmracek]]): [http://web.bentley.edu/empl/c/ncarter/vgt/VisualizingGroupTheory-320x240.mov]

* Summary of the course ([[User: Lp.thibault]]): [[Media:11-1100_Summary6.pdf|Summary of the course]].

* Read Along on material covering Modules (Dummit Foote and Lang): [[User:Vanessa.foster]]

* A rough and ready Perl script for [[Computing GCDs over the Gaussian Integers]]. (I provide no proof of correctness, all faults are my own, etc. -- [[User:pgadey]])

* Some [[Media:study notes]] summarizing the proofs we did in class pertaining to rings (jmracek)

[[Image:xkcdsettheory.jpg]]
Link: [[http://xkcd.com/982/]]

File:Xkcdsettheory.jpg

2011-11-25T18:45:38Z

Jmracek:

11-1100

2011-11-25T18:44:54Z

Jmracek:

__NOEDITSECTION__
__NOTOC__
{{11-1100/Navigation}}
==Core Algebra I==
===Department of Mathematics, University of Toronto, Fall 2011===

{{11-1100/Crucial Information}}

===Texts===
Lang's ''Algebra'', Selick's [http://www.math.toronto.edu/mat1100/ lecture notes for this class], Dummit and Foote's ''Abstract Algebra'', Hungerford's ''Abstract Algebra''.

===Further Resources===

* [http://www.math.utoronto.ca/cms/graduate-program/ Graduate Studies] at the [http://www.math.toronto.edu/ UofT Math Department]. In particular, [http://www.math.utoronto.ca/cms/tentative-2010-2011-graduate-course-descriptions/ Graduate Course Descriptions].

* My {{Pensieve Link|Classes/11-1100/|11-1100 notebook}}.

* My [[10-1100|2010 Class]].

* Paul Selick's [http://www.math.toronto.edu/mat1100/ 2007 class] ([[11-1100/Errata_to_Prof._Selick's_Notes|Errata]]).

* Some (mostly complete) notes from last year's class: [[10-1100-Notes]].

* Some blackboard shots start at {{BBS Link|11_1100-111024-110239.jpg}}.

{{Template:11-1100:Dror/Students Divider}}

* Student solutions to homework problems: [[11-1100/Homework Solutions]].

* Student notes from class: [[11-1100/Notes]].

* Very cool video explaining how to visualize some concepts in group theory ([[User:jmracek]]): [http://web.bentley.edu/empl/c/ncarter/vgt/VisualizingGroupTheory-320x240.mov]

* Summary of the course ([[User: Lp.thibault]]): [[Media:11-1100_Summary.pdf|Summary of the course]].
* Read Along on material covering Modules (Dummit Foote and Lang): [[User:Vanessa.foster]]

[[Image:xkcdsettheory.jpg]]
Link: [[http://xkcd.com/982/]]

11-1100

2011-10-25T05:22:49Z

Jmracek:

11-1100

2011-10-25T05:22:22Z

Jmracek:

11-1100

2011-10-25T05:21:36Z

Jmracek:

User:Jmracek

2011-10-23T03:19:29Z

Jmracek:

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

[[11-1100 HW1 pt. 1 submission: MATLAB Code for Non-Commutative Gaussian Elimination]]

== How to visualize normal subgroups ==

I was trying to find an intuitive way to just be able to instinctively tell whether or not a given subgroup is normal. I came across a few articles on the web that give some great insights, so I thought I would share them. I first came across an answer here:

http://forums.xkcd.com/viewtopic.php?f=17&t=26793

And then through reading the responses on the forum, was naturally led to an email exchange between John Baez and Sean Fitzpatrick:

http://math.ucr.edu/home/baez/normal.html

Let me summarize the main idea. Basically, one can tell whether or not a given subgroup is normal by finding other subgroups which, very roughly, "look the same". As an example, consider the permutations of vertices of the tetrahedron. One subgroup of order 3 can be pictured by rotating about an axis that goes through a vertex and the center of an opposing face; however, one could have equally well picked any of the other vertices of the tetrahedron to fix the axis. In fact, this subgroup is not normal.

The way I understand it is from the standpoint of linear algebra. Since we can picture the subgroup I mentioned as rigid body rotations in R^{3}, the most obvious representation is a subgroup of SO(3) that can be constructed by putting the center of mass of the tetrahedron at the origin, then finding the action of the group elements on an orthonormal basis. In this picture, conjugation by a group element can be roughly thought of as a coordinate change to some rotated frame of reference (because group conjugation is a similarity transformation in the matrix representations); so, if you can find a change of coordinates that makes the action of any two subgroups "look the same" then you know that it cannot be normal. In the previous example, one can see that any 4 of the subgroups of order 3 are essentially the same rotations, just looking down a different axis of the tetrahedron. I haven't worked it out in detail, but I think that the subgroup generated by <(234)> can be turned into the subgroup generated by <(123)> if you conjugate by (14).

== More on how to visualize concepts in group theory ==

A very cool video explaining how to use Cayley graphs to visualize some group theoretic concepts. I especially enjoyed the part about the semidirect product.

http://web.bentley.edu/empl/c/ncarter/vgt/VisualizingGroupTheory-320x240.mov

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

2011-10-22T01:15:53Z

Jmracek:

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

[[11-1100 HW1 pt. 1 submission: MATLAB Code for Non-Commutative Gaussian Elimination]]

== How to visualize normal subgroups ==

I was trying to find an intuitive way to just be able to instinctively tell whether or not a given subgroup is normal. I came across a few articles on the web that give some great insights, so I thought I would share them. I first came across an answer here:

http://forums.xkcd.com/viewtopic.php?f=17&t=26793

And then through reading the responses on the forum, was naturally led to an email exchange between John Baez and Sean Fitzpatrick:

http://math.ucr.edu/home/baez/normal.html

Let me summarize the main idea. Basically, one can tell whether or not a given subgroup is normal by finding other subgroups which, very roughly, "look the same". As an example, consider the permutations of vertices of the tetrahedron. One subgroup of order 3 can be pictured by rotating about an axis that goes through a vertex and the center of an opposing face; however, one could have equally well picked any of the other vertices of the tetrahedron to fix the axis. In fact, this subgroup is not normal.

The way I understand it is from the standpoint of linear algebra. Since we can picture the subgroup I mentioned as rigid body rotations in R^{3}, the most obvious representation is a subgroup of SO(3) that can be constructed by putting the center of mass of the tetrahedron at the origin, then finding the action of the group elements on an orthonormal basis. In this picture, conjugation by a group element can be roughly thought of as a coordinate change to some rotated frame of reference (because group conjugation is a similarity transformation in the matrix representations); so, if you can find a change of coordinates that makes the action of any two subgroups "look the same" then you know that it cannot be normal. In the previous example, one can see that any 4 of the subgroups of order 3 are essentially the same rotations, just looking down a different axis of the tetrahedron. I haven't worked it out in detail, but I think that the subgroup generated by <(234)> can be turned into the subgroup generated by <(123)> if you conjugate by (14).

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

File:JmracekHW2.pdf

2011-10-20T09:13:01Z

Jmracek:

11-1100/Homework Solutions

2011-10-20T09:12:44Z

Jmracek: /* Sample solutions to Homework Assignment 2 */

{{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
|-
| Mracek || James || [[User:jmracek|jmracek]] || [[Media:jmracekHW2.pdf | Solutions]]
|-
|}

File:JmracekHW1.pdf

2011-10-13T15:54:31Z

Jmracek:

11-1100/Homework Solutions

2011-10-13T15:54:22Z

Jmracek:

{{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 | here]]
|-
| 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
|-
| Last ||First|| User || Link
|-
|}

11-1100 HW1 pt. 1 submission: MATLAB Code for Non-Commutative Gaussian Elimination

2011-10-10T22:33:47Z

Jmracek:

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

2011-10-10T22:33:24Z

Jmracek:

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

[[11-1100 HW1 pt. 1 submission: 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)

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

2011-10-09T22:17:33Z

Jmracek:

File:Output.jpg

2011-10-09T22:15:59Z

Jmracek:

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

2011-10-09T22:15:37Z

Jmracek:

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!

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

2011-10-09T22:07:50Z

Jmracek:

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:

>> [Order, NCGE_Table] = PocketCube();
>> Order
Order =
88179840
>> Order/24
ans =
3674160
>> spy(NCGE_Table)

[[Image:pivot.jpg]]

User:Jmracek

2011-10-09T22:06:33Z

Jmracek:

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

File:Pivot.jpg

2011-10-09T22:04:50Z

Jmracek:

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

2011-10-09T21:59:04Z

Jmracek:

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:

>> [Order, NCGE_Table] = PocketCube();
>> Order
Order =
88179840
>> Order/24
ans =
3674160
>> spy(NCGE_Table)

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

2011-10-09T21:54:05Z

Jmracek:

File:Cubelayout.jpg

2011-10-09T21:52:23Z

Jmracek:

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

2011-10-09T21:52:04Z

Jmracek:

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

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

2011-10-09T21:12:28Z

Jmracek:

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

2011-10-09T21:11:55Z

Jmracek:

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

2011-10-09T21:11:08Z

Jmracek:

File:Matrix.jpg

2011-10-09T21:07:48Z

Jmracek:

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

2011-10-09T21:07:07Z

Jmracek:

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

2011-10-09T21:06:03Z

Jmracek:

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

2011-10-09T21:03:47Z

Jmracek:

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

2011-10-09T21:02:59Z

Jmracek:

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

2011-10-09T21:02:42Z

Jmracek:

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

2011-10-09T20:58:41Z

Jmracek:

File:PocketCube.jpg

2011-10-09T20:42:35Z

Jmracek:

File:BG2.jpg

2011-10-09T20:42:10Z

Jmracek:

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

2011-10-09T20:41:58Z

Jmracek:

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

File:Feed.jpg

2011-10-09T20:32:37Z

Jmracek: jmracek's algorithm for NCGE

jmracek's algorithm for NCGE

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

2011-10-09T20:31:57Z

Jmracek:

[[Image:Feed.jpg]]

User:Jmracek

2011-10-09T19:35:03Z

Jmracek:

I think this is my user page. I'm not sure what I'm doing yet.

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

User:Jmracek

2011-10-08T02:44:12Z

Jmracek:

I think this is my user page. I'm not sure what I'm doing yet.

Talk:11-1100/Homework Assignment 1

2011-09-30T20:53:24Z

Jmracek:

"...that any morphism from G into an Abelian group factors through G / G' "

Is this just another way of asking to show that [; \frac{G}{\ker \phi} ;] is normal in [; \frac{G}{G'} ;]? The wording of this question is a little unclear to me.

-James

Talk:11-1100/Homework Assignment 1

2011-09-30T20:49:29Z

Jmracek:

"...that any morphism from G into an Abelian group factors through G / G' "

Is this just another way of asking to show that $\frac{G}{\ker \phi}$ is normal in $\frac{G}{G'}$? The wording of this question is a little unclear to me.

-James

11-1100/Class Photo

2011-09-27T17:08:22Z

Jmracek: /* Who We Are... */

Our class on September 27, 2011:

[[Image:11-1100-ClassPhoto.jpg|thumb|centre|800px|Class Photo: click to enlarge]]
{{11-1100/Navigation}}

Please identify yourself in this photo! There are two ways to do that:

* [[Special:Userlogin|Log in]] to this Wiki and edit this page. Put your name, userid, email address and location in the picture in the alphabetical list below.
* Send [[User:Drorbn|Dror]] an email message with this information.

The first option is more fun but less private.

===Who We Are...===

{| align=center border=1 cellspacing=0
|-
!First name
!Last name
!UserID
!Email
!In the photo
!Comments
{{Photo Entry|last=Bar-Natan|first=Dror|userid=Drorbn|email=drorbn@ math.toronto.edu|location=facing everybody, as the photographer|comments=Take this entry as a model and leave it first. Otherwise alphabetize by last name. Feel free to leave some fields blank. For better line-breaking, leave a space next to the "@" in email addresses.}}
{{Photo Entry|last=Glynn-Adey|first=Parker|userid=pgadey|email=parker.glynn.adey@ math.toronto.edu|location=Fifth from the right in the back row|comments=Glowing bald guy with yellow shirt.}}
{{Photo Entry|last=Mracek|first=James|userid=jmracek|email=jmracek@math.toronto.edu|location=7th from the right (or left) in the back row|comments=Glasses with black and white t-shirt.}}

|}