# Group Theory on Wikipedia



## brunson (Nov 5, 2008)

Check out todays "Featured Article" on Wikipedia: http://en.wikipedia.org/wiki/%s

It's kind of cool that they use a 4x4 rather than a 3x3 for their decoration.


----------



## Lucas Garron (Nov 5, 2008)

Yeah, qq and I were discussing that. We agreed that 4x4x4 is a worse example than 3x3x3 to present as a group.


----------



## badmephisto (Nov 5, 2008)

yea i saw that 
actually lately i like to think of cube more in terms of linear algebra than groups... A cube can be seen as a column vector, and every move is just a linear transformation... associativity, commutativity, inverses of moves, everything works. I haven't thought about it too much but I think I'd like to sometime
although there are some issues i can think of, such as the fact that the "rubik's cube space" is discrete... and finite...
edit: actually the finiteness and discreteness is not much of an issue... and all transformations could i think be modeled with swaps...
also what would be the metric on this space? 


also I tried thinking of it as a graph... each node being a state, edges for each operation you can do on a cube... solution being just a BFS search on the graph?


----------



## pjk (Nov 5, 2008)

Glad to see it.


----------



## cuBerBruce (Nov 6, 2008)

Lucas Garron said:


> Yeah, qq and I were discussing that. We agreed that 4x4x4 is a worse example than 3x3x3 to present as a group.



Yes, I agree that the Revenge was probably not the best choice to use to represent a group. Arguably the claim that the "manipulations" of the Revenge form a group is correct. The ways you can move the pieces around do form a group (the 4x4x4 supercube group) assuming you track each piece individually even if it looks the same as another piece. But the set of positions reachable, with centers of the same color considered indistinguishable, do not form a group. (Well, I suppose you could contrive a group operation such that those positions do form a group, but such a contrived group operation probably wouldn't be very meaningful.)



badmephisto said:


> edit: actually the finiteness and discreteness is not much of an issue... and all transformations could i think be modeled with swaps...


Any group is isomorphic to a permutation group. Any permutation of a finite set can be represented by a set of swaps.


badmephisto said:


> also I tried thinking of it as a graph... each node being a state, edges for each operation you can do on a cube... solution being just a BFS search on the graph?


Such a graph for a group is called a Cayley graph. Of course, a group generally has many Cayley graphs. For a specific Cayley graph, you must specify not only the group, but also a set of generators for the group.


----------



## DavidWoner (Nov 6, 2008)

Lucas Garron said:


> Yeah, qq and I were discussing that. We agreed that 4x4x4 is a worse example than 3x3x3 to present as a group.



someone must have heard you, because now I see a 3x3.


----------



## siva.shanmukh (Nov 7, 2008)

badmephisto said:


> yea i saw that
> actually lately i like to think of cube more in terms of linear algebra than groups... A cube can be seen as a column vector, and every move is just a linear transformation... associativity, commutativity, inverses of moves, everything works. I haven't thought about it too much but I think I'd like to sometime
> although there are some issues i can think of, such as the fact that the "rubik's cube space" is discrete... and finite...
> edit: actually the finiteness and discreteness is not much of an issue... and all transformations could i think be modeled with swaps...
> ...



Sounds interesting. i have tried thinking on this lines but couldn't move forward. Can you suggest a basis, a linear combination for the identity(solved cube) and a transformation for a basic turn(say a U turn)


----------



## JBCM627 (Nov 7, 2008)

siva.shanmukh said:


> badmephisto said:
> 
> 
> > yea i saw that
> ...



I've also thought about this some. I asked Bruce about this, who pointed to the book "Adventures in Group Theory", which talks about permutation matrices. Per Bruce:


> A permutation matrix is a square matrix with all 0's except for one 1 in each row and in each column. So you could use a 48x48 permutation matrix to represent Rubik's cube group elements. Each 1 in the matrix indicates a "facelet" (or facet) going from one location to another. The basic moves (such as U) move 20 facets and leave the other 28 facets fixed. So the matrix for U would have 1's on the diagonal for 28 rows/columns and 20 1's that are off the diagonal. This is a rather simple but not very compact way of representing cube group elements with a matrix. If you were considering the group where the centers can be arranged 24 different ways (such as via cube rotations), then you would need a 54x54 matrix.



This is one way of looking at it.

Another way that seems more natural to me is to simply use a column vector, where each individual element represents a piece. This works well for position of pieces, but can become a bit messy when you involve orientation.

To make things simple, consider a 2x2 (so just corners, if you like): you can label your corners from A to H (or 1 to 8 if you like) and create a vector out of this. Any moves would simply be transformations composed of elementary row operations (namely, interchanging rows in your column vector). The obvious basis for this would be your standard basis.

Including orientation makes this messier, because now you need to include extra information about each piece. The most natural way I could think of to do this is to make each element in the column vector a vector itself (namely, a 1x3 vector for corners, as there are 3 possible orientations per corner). Your transformation matrix now must contain appropriate elements, notably its elements must also be transformation matrices composed of elementary row operations.

To type out a whole example, a solved 2x2 would be:
[[A,0,0]
[B,0,0]
[C,0,0]
[D,0,0]
[E,0,0]
[F,0,0]
[G,0,0]
[H,0,0]]

And accordingly, a U could be something like:
[0,0,0,I,0,0,0,0
I,0,0,0,0,0,0,0
0,I,0,0,0,0,0,0
0,0,I,0,0,0,0,0
0,0,0,0,I,0,0,0
0,0,0,0,0,I,0,0
0,0,0,0,0,0,I,0
0,0,0,0,0,0,0,I]

Where I represents a 3x3 identity matrix, and 0 is a 3x3 0 matrix. This case, being a U turn, is slightly less messy since you can consider orientation to not be altered.

For edges, you can also use complex numbers to indicate orientation... your transformations/moves will just accordingly need to contain complex componets. So for example, you might have a position matrix:
transpose([A, B, C, D, E, F, G, H, I, J, K, L])
And a transformation matrix for an R turn (I hope I didnt make a mistake):
[1,0,0,0,0,0,0,0,0,0,0,0
0,1,0,0,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,i,0,0,0,0
0,0,0,0,1,0,0,0,0,0,0,0
0,0,0,0,0,1,0,0,0,0,0,0
0,0,0,i,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,i
0,0,0,0,0,0,0,0,1,0,0,0
0,0,0,0,0,0,0,0,0,1,0,0
0,0,0,0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,i,0,0,0,0,0]

Using something like this, although I haven't done it, I assume you can deduce many things, like the fact that the transforms F, R, U, B, L, and D are not linearly independent.


----------



## siva.shanmukh (Nov 8, 2008)

Some thing sounds wrong about there being 20 1s in each row and column. I want to show an example. Lets consider the 2x2 case. Now according to what you said, it should be 12 1s in each row and a column. and the transformation matrix itself being a 24x24 matrix. I can't think of a matrix with 12 1s in each row and column which would give a sensible transformation. It should be only a single 1 in a row and a column. 

Correct me if I am wrong and tell me if I am not clear about anything


----------



## cuBerBruce (Nov 9, 2008)

siva.shanmukh said:


> Some thing sounds wrong about there being 20 1s in each row and column. I want to show an example. Lets consider the 2x2 case. Now according to what you said, it should be 12 1s in each row and a column. and the transformation matrix itself being a 24x24 matrix. I can't think of a matrix with 12 1s in each row and column which would give a sensible transformation. It should be only a single 1 in a row and a column.
> 
> Correct me if I am wrong and tell me if I am not clear about anything



20 1s in each row and column??? Where does that come from?

What I was talking about was a 48x48 matrix of all 0s except for one 1 in each row and in each column. For the move U, 28 of those 48 1s would be on the diagonal, and the other 20 would not be on the diagonal. I didn't say anything about 20 1s in a single row or column.


----------



## siva.shanmukh (Nov 9, 2008)

Oops!!

Sorry, Its my mistake. It was 20 1s on a whole and I mistook it to 20 1s in each row and column.

anyway sequence of face turns would now give us a transformation matrix, by multiplying them in that order and we get a transformation matrix. I guess I am right about this.

Now given a scramble state, we can get the transformation matrix to transform it to identity and the challenge will be to break it into a product of basic transformations. May be I will try to do this for a 2x2 and see if we can make a mathematical procedure for this.

If someone had already done something like that, let me know.


----------



## mande (Nov 10, 2008)

Somehow, I feel it more intuitive to think of the cube as a group. Its easy to recognize the cube group as the semi direct product of the orientation subgroup and the permutation subgroup. I didn't really think thinking of it as linear transformations as I thought the calculations might have been quite cumbersome.


----------



## siva.shanmukh (Nov 11, 2008)

mande said:


> Somehow, I feel it more intuitive to think of the cube as a group. Its easy to recognize the cube group as the semi direct product of the orientation subgroup and the permutation subgroup. I didn't really think thinking of it as linear transformations as I thought the calculations might have been quite cumbersome.



Very true. And I have not understood the semi-direct product part of it.

You told that you have some material that you planned to mail me? I still owe you the fingertricks mail also though. I shall soon mail you. The only pressing thing here is that my endsems are nearing.


----------

