

General OffTopic
Everything not about BMWs. Posts must be "primetime" safe and in good taste. You must be logged in to see subforums. Click here to browse all new posts. 

Thread Tools  Search this Thread  Rate Thread  Display Modes 
04082014, 10:06 AM  #1 
drunken science

Zell, Mash, anyone else good with higher math...
Is there an intuitive way to picture the stabilizer and orbit of a group? I can easily find them, but don't really understand what they're doing. Like for the kernel and image, I knew how to find them, but didn't really understand what they were until I saw this:
__________________

04082014, 10:13 AM  #2 
Registered User

Going to sidebar this thread for a moment to compliment your stellar photography. Enjoyed looking through that. Carry on.

04082014, 11:19 AM  #3 
drunken science

Pretty sure I have it figured out but if you guys can think of a better metaphor, feel free. S is a list of things, say, colored balls. G is a machine that matches the balls together and contains every possible combination of colors. The stabilizer for a given color is the method by which G outputs the same color you feed in. And the orbit will be the method that produces every possible combination for the color you feed in, including the stabilizer.
__________________

04082014, 11:31 AM  #4 
E46Fanatic
Join Date: Sep 2002
Location: City of Angels
Posts: 6,509
My Ride: 2003 Technik S1 M3

__________________
"I catch you in my dreams, just me and you. But you seem confused, I'm not trying to break the rules. So why do you feel the way that you do? So why do you feel the way that you do?" 2014 LA Autoshow FB Gallery 
04082014, 11:51 AM  #5 
Registered User

If you were talking about planets, I could help you.
__________________

04082014, 11:54 AM  #6  
Registered User

Quote:


04082014, 11:57 AM  #7  
drunken science

Quote:
Permutation groups niqqa edit: Where the fvck is Zell, I know he knows this stuff.
__________________
Last edited by cowmoo32; 04082014 at 12:04 PM. 

04082014, 12:04 PM  #8 
Registered User


04082014, 12:07 PM  #9 
Is not Persian
Join Date: Apr 2003
Location: Approximately La Crescenta, CA
Posts: 870
My Ride: '01 TiAg M3 Vert

I have a confession to make, most of the higher level math I know (group theory stuff) is from physics classes, I haven't taken many formal higher level math courses, and even those were a long time ago and I haven't used them much since. I can't help you here
__________________
Last edited by my ass; Yesterday at 11:15 PM. 
04082014, 12:08 PM  #10 
Registered User

I'll read iiiiit, I r been busy lately. THIS THREAD HAS BEEN NOTED
__________________

04082014, 12:10 PM  #11 
Registered User

Since I have a little time on my hands I'll try to help you out a little. Let me start with a question and then go through some proofs that will hopefully help you to understand.
How many rotational symmetries does a cube have? This question can be answered in a number of ways. Perhaps the one that most readily occurs to people is this: each vertex can end up in one of eight places; once you’ve decided where to put it, there are three places you can put one of its neighbours; once you’ve decided where to put that, the rotation is determined, so the total number of rotations is 8\times 3=24. Here’s another proof. Take one of the faces. It can go to one of six other faces, and once you’ve decided which face it will go to, one of the vertices on the face has four places it can go, and once you’ve decided that you’ve fixed the rotation. So the total number of rotations is 6\times 4=24. And here’s another. Take one of the midpoints of the twelve edges. There are twelve places it can end up, and once you’ve decided where to put it, there are two choices for how you send the two endpoints of the original edge to the endpoints of the new edge. So the total number of rotations is 12\times 2=24. And here’s yet another. Take a point half way between the centre of one of the faces and one of the vertices. (If the cube is the set of all points (x,y,z) such that x, y and z all lie in the closed interval [1,1], then we could, for instance, take the point (1/2,1/2,1).) There are 24 places that that point can end up — the 24 points that are half way between the centre of some face and one of the vertices of that face. There is only one rotational symmetry that takes the original point to any given one of those 24 points. Therefore, the number of rotations of the cube is 24\times 1=24. If you understood those arguments, then you basically understand the orbitstabilizer theorem, even if you think you don’t. To try to convince you of that, I’ll first show how to convert one of the proofs into a proof that explicitly uses the orbitstabilizer theorem. I’ll then discuss how much you have to remember in order to remember the proof of the orbitstabilizer theorem. As usual, I shall aim to show that the answer is “very little indeed”. However, routine proofs in abstract algebra have a somewhat different flavour from routine proofs in set theory and analysis, and as this one is a good representative example, it bears discussing in some detail. (Later I may try the same with the first isomorphism theorem, which you should be meeting fairly soon.) To illustrate how to count symmetries using the orbitstabilizer theorem, let me convert the 6\times 4 proof that used faces. The obvious way to capture the idea of “which face a particular face goes to” is to let the symmetry group of the cube act on the faces of the cube. Then the set of places that a particular face can go to is nothing other than the orbit of that face. How does the group act on the faces? Well, any rotation of the cube will permute the faces, and that permutation is the one that corresponds to the rotation. In the earlier version of the argument, we said that our chosen face can go to any one of six other faces. The fancy way of saying that is that the orbit of the chosen face is the set of all faces, which has size 6. And in the earlier version of the argument, we said that once we had decided which face our chosen face would go to, there were four ways of lining up the vertices. This doesn’t quite correspond to a statement about stabilizers, but let us note for now that if the chosen face maps to itself, then we have four choices. So the stabilizer of our chosen face has size 4. Multiplying those two numbers together gives us 24. The content of the orbitstabilizer theorem is basically that if a group G acts on a set X, then once you know how many ways there are of sending an element x of X to itself, you also know how many ways there are of sending it to any other element in its orbit. In the facesofthecube example, knowing that there are four ways of rotating the cube so that a face F ends up where it was before tells us that there are also four ways of sending it to some other face F'. And that is because “all faces look basically the same” from the point of view of the rotation group. In general, “all points of the orbit of x look basically the same” from the point of view of the transformations performed by the elements of G. I’m going to give a few different proofs of the orbitstabilizer theorem, not because they are fundamentally different, but because they have certain stylistic features that are worth commenting on. Also, it may be interesting to see how much variety is possible even when presenting a proof, even when the underlying argument is the same. First, I’ll remind you of the statement we are trying to prove. Theorem. Let G be a group that acts on a set X, let x be an element of X, let O_x be the orbit of x and let S_x be the stabilizer of x. Then O_xS_x=G. In words, the size of the group is the size of the orbit times the size of the stabilizer. Proof 1. For this proof I want to try to capture as closely as possible our intuition in the cube example that the set of rotations that takes one face to another is “just like the set of rotations that fix that face, but over at another place”. However, I’ll argue in general. What am I trying to show in the abstract? I want to show that if y belongs to the orbit of x, then the set of g\in G such that gx=y is the same size as S_x, which is the set of g\in G such that gx=x. (Here I’m slipping into the condensed notation and writing gx instead of \phi(g,x) or \phi(g)(x). But it’s important to bear in mind that the “product” gx is not the group operation, since it’s only g that belongs to a group. Rather, it is what one might call the group action operation, which has some nice grouplike properties such as (gh)x=g(hx) and ex=x.) What is the most natural way to show that two sets have the same size? It’s to produce a bijection between them. (It isn’t the only way. Another is to calculate their sizes, possibly by completely different methods, and show that you get the same answer in both cases. But that is not an appropriate method here, since we’re not given enough information to calculate anything.) Let me write S_{xy} for the set of g\in G that take x to y. If I’m given an element of S_x, how do I turn it into an element of S_{xy}? Well, in the facesofcube example, what I might do is this. I fix, once and for all, a rotation \rho that takes my initial face to the given face. And then, given a rotation that fixes the initial face, I compose it with \rho to get a rotation that takes the initial face to the given face. Let’s try that with S_x and S_{xy}. Since y belongs to the orbit of x (by assumption), there is some h such that hx=y. Now let me define a map from S_x to S_{xy} by mapping g to hg. Note that hg takes x first to x (since g\in S_x) and then to y (since h\in S_{xy}). Thus, hg really does belong to S_{xy}. However, is the map we’ve just defined a bijection? Let’s see if we can prove that it’s an injection and a surjection. No, let’s not do that. Let’s try to find an inverse. Given an element u of S_{xy}, how might we convert it into an element of S_x? There’s only one thing we can even dream of trying at this point. Since u takes x to y and h also takes x to y, h^{1}u takes x to x, as we want. So the map u\mapsto h^{1}u takes S_{xy} to S_x. Does it invert the previous map? Yes of course it does. We’ve shown that for each y\in O_x there are precisely S_x elements of G that take x to y. But every element of G takes x to something in the orbit, so G=O_xS_x, as we were trying to prove. \square In case you found that offputtingly long, here it is stripped of all the accompanying chat. The real Proof 1. Let y be an arbitrary element of O_x, and let S_{xy}=\{g\in G:gx=y\}. Pick h\in S_{xy} and define a map \phi:S_x\to S_{xy} by \phi:g\to hg. The map \psi:S_{xy}\to S_x defined by \psi:u\to h^{1}u inverts \phi, so S_x=S_{xy} for every y\in O_x. But the sets S_{xy} with y\in O_x form a partition of G. It follows that G=S_xO_x. \square I cheated slightly there by not checking carefully that \phi really does take S_x to S_{xy} and that \psi really does take S_{xy} to S_x. But those facts are easy enough to be left to the reader to do in his/her head. That proof is so short that one might wonder why another proof could possibly be desirable. Well, it’s mostly an aesthetic point, at least as far as this proof is concerned, but there’s something a bit ugly about choosing that h. Why? Because I didn’t say how to do it. So, for example, the way I chose h for one y might be completely unrelated to the way I chose it for another y. Wouldn’t it be nicer if there were some natural way of defining h in terms of y? Well, yes it would, but it’s not that easy to do. Just think of the cube example. Suppose I take a face F and I ask you to define, for each other face F', a rotation of the cube that takes F to F'. I want you to do it in a nice systematic way. How might you do it? Well, if F'=F then probably the most natural thing to do is take the identity. How about if F' is one of the neighbouring faces to F? Perhaps the most natural thing there is to take a 90degree rotation about an axis through the centre of the cube that’s parallel to the edge where F and F' meet. But then what about the face opposite F? There are four ways of rotating the cube so that F lands up at the opposite face, and they are of two kinds: two of them are half turns about axes that go through the midpoints of two opposite faces, and the other two are half turns about axes that go through the midpoints of two opposite edges. (If you draw a diagram, I hope you’ll be able to see what I’m talking about here. It’s one of those things that may be easier to work out for yourself.) Anyhow, for each of these two types of half turn, there is absolutely nothing to choose between the two half turns of that type. So there just isn’t a natural way to choose a rotation for each face. As mathematicians might say, there isn’t a canonical choice. So is that the end of the story? Not quite. There’s a useful principle that sometimes applies in this kind of situation. It says this. If you can’t make a canonical choice, then make all choices at once. This meme was embedded in my brain as a result of a nice Mathoverflow question, though I suppose I was aware of it less consciously before that. Let’s see how it plays out with our proof. If I don’t choose just one h\in S_{xy}, then what do I do instead? I choose all h that belong to S_{xy}. A problem then arises when I try to define a bijection from S_x to S_{xy}. Never mind, though. Let’s just define a map from S_{xy}\times S_x to S_{xy} by sending (h,g) to hg. Note that this is like what we did before, but we’re doing it for every h and not just one chosen h. And what’s nice about it is that we are now doing precisely the same thing for every y. Let’s call our map \phi. Obviously, \phi is not a bijection, but that doesn’t matter. We’re trying to show that it’s a bit like a putting together of S_{xy} bijections. So what we’d like to show is that every element of S_{xy} has exactly S_{xy} preimages under \phi. That will tell us that S_{xy}S_x=S_{xy}^2, which will imply that S_{xy}=S_x. So let’s take u\in S_x. How many preimages has it got? Well, a preimage of u is a pair (h,g) such that hg=u. So I want to show that there are precisely S_{xy} solutions of the equation hg=u with h\in S_{xy} and g\in S_x. But that’s easy: for each h\in S_{xy} there is precisely one possible g, namely h^{1}u, which does indeed belong to S_x. Let me again give the condensed version, just to convince you that what I’ve written doesn’t add up to a long proof. In fact, I don’t even need to bother to define the function \phi. Proof 2. Let y be an arbitrary element of O_x and let S_{xy}=\{g\in G:gx=y\}. For every u,h\in S_{xy} there is exactly one g\in S_x such that hg=u, namely h^{1}u. It follows that every u\in S_{xy} can be written in S_{xy} ways as hg with h\in S_{xy} and g\in S_x. Also, hg\in S_{xy} for every h\in S_{xy} and every g\in S_x. It follows that S_{xy}S_x=S_{xy}^2. Therefore, S_x=S_{xy}. But the sets S_{xy} with y\in O_x form a partition of G. It follows that G=S_xO_x. \square Here is a variant of the above argument that I like better. Proof 3. Let y be an arbitrary element of O_x and let S_{xy}=\{g\in G:gx=y\}. Let u\in S_{xy} and let us see in how many ways we can write u=hg with h\in S_{xy} and g\in S_x. Well, for each h\in S_{xy}, there is exactly one g\in S_x such that hg=u, namely h^{1}u. So we can write u=hg in S_{xy} ways. But also, for each g\in S_x there is exactly one h\in S_{xy} such that hg=u, namely ug^{1}. This shows that we can write u=hg in S_x ways. Therefore, S_x=S_{xy}. But the sets S_{xy} with y\in O_x form a partition of G. It follows that G=S_xO_x. \square Or do I like it better? It’s starting to look, with its noncanonical choice of u\in S_{xy}, a bit too like the first argument. I still don’t feel as though I’ve arrived at the neatest and most symmetrical argument, and I’ve also not satisfied another urge, which is to prove that G=O_xS_x by finding a nice bijection between G and O_x\times S_x. There are good reasons for the second problem, as I’ve already discussed, but I might be able to satisfy my urge by finding not a onetoone correspondence, but something a bit more general and multivalued. So let’s take a point (y,g)\in O_x\times S_x. What can we do with it? We can use it to define the element gy of X, but that doesn’t seem very exciting or helpful. What we’d really like is to define an element of G, which earlier we did by fixing some h\in S_{xy} and taking hg. But that felt too noncanonical, so instead we preferred to take all h. If we take all h, then that’s saying that we can get from x to y in several different ways. So we seem to get a map from G\times S_x to G, which is very simple: it takes (h,g) to hg. But what’s the point of it? And where does O_x come in? One way of making O_x come in is to go one step further and let hg act on x to create hgx=hx. So now we’ve got a map from G\times S_x to O_x, the map that takes (h,g) to hx. How many preimages does an element y have? I’m not going to answer that question (though I could) because once we’ve got to the point of mapping G\times S_x to O_x using the map above, we see that g isn’t really playing a role, so why not just focus on the map from G to O_x that takes g (which I was calling h above) to gx? If y\in O_x, then how many preimages does y have? I won’t bother to answer that question either: it’s the same as asking how big the set S_{xy} is, and we’ve established already that that is S_x, so it wouldn’t be a particularly new proof that resulted. However, one remark that’s worth making is that the set S_{xy} is a left coset of S_x. Probably the proof you were given in lectures was this. Proof 4. We shall show that there is a bijection between O_x and the set of left cosets of S_x. To do this, we map the left coset gS_x to gx. We must show that this is welldefined. But if gS_x=hS_x, then h^{1}gS_x=S_x, and therefore, since S_x is a subgroup, h^{1}g\in S_x. From that it follows that h^{1}gx=x, so gx=hx. Since the number of left cosets of S_x is G/S_x, we are done. \square If the phrase “welldefined” worries you in the above argument, then I recommend a post I once wrote about what it means. Here’s a different way of writing the above proof, where we think more about equivalence relations than about partitions. Proof 5. Here are two equivalence relations on G. For the first, I define g\sim_1h if gx=hx. For the second, I define g\sim_2h if h^{1}g\in S_x. Note that this is the same as saying that g^{1}h\in S_x and also the same as saying that gS_x=hS_x. Now gx=hx if and only if h^{1}gx=x if and only if h^{1}g\in S_x. So the two equivalence relations are the same. The number of equivalence classes for the first relation is obviously O_x and the size of each equivalence class for the second relation is obviously S_x, so the result is proved. \square Let me make one final remark about the orbitstabilizer theorem. Why, one might ask, is it a useful result? A rather general answer is that it gives us a relationship between three quantities, namely G, S_x and O_x, that allows us to determine any one of them from the other two. Situations crop up quite frequently in group theory where it is not very easy to see what one of these quantities is directly, but quite easy to calculate the other two. The orbitstabilizer theorem then gives us the hard one too. For example, in the case of counting rotational symmetries of a cube, it isn’t easy to think of all the rotations unless you partition them in some nice way, such as looking at what they do to a particular vertex or face, which, as we saw before, amounts to counting orbits and stabilizers. It’s not always G that’s the tough one to get a handle on. For example, in question 10 of Examples Sheet 3 it’s the size of the orbit that isn’t obvious. (In general with the bunch of questions around there, I recommend thinking to yourself, “What is the orbitstabilizer theorem giving me?”) 
04082014, 12:14 PM  #12  
drunken science

Quote:
I hope I never deal with it again in this type of setting. It's interesting because all of modern cryptography has a base in it, and I know things like SL(2) and GL(2) pop up in physics, but I hate writing proofs with a passion. Apply it and I'm fine, but math for math's sake is awful.
__________________


04082014, 12:15 PM  #13 
Registered User

Well, I don't think you're gonna get a better answer than that
__________________

04082014, 12:15 PM  #14  
Registered User

Quote:
BTW 217 doesn't know anything about this. He copied this blog post: http://gowers.wordpress.com/2011/11/...rem/#more3720
__________________
Last edited by WDE46; 04082014 at 12:18 PM. 

04082014, 12:20 PM  #15  
Registered User

Quote:


04082014, 12:20 PM  #16 
Registered User

prove it
__________________

04082014, 12:24 PM  #17 
drunken science

If you can't explain it to your grandmother then you don't know it well enough, so there has to be a better answer. Anyway, I've found some stuff about the Rubik's Cube Group that helped elucidate the idea. My idea was close, but I missed it a little. The stabilizer lives in G so my picture isn't quite right, but it's good enough for me. All I need is a picture and I can remember the formula.
Like I sad before, this stuff underlies all of modern cryptography. It has applications but they're more abstract than classical physics.
__________________
Last edited by cowmoo32; 04082014 at 12:26 PM. 
04082014, 12:29 PM  #18  
Registered User

Quote:
I'm sure it's got applications. Most math does. This just isn't particularly practical for many people to learn.
__________________
Last edited by WDE46; 04082014 at 12:29 PM. 

04082014, 12:40 PM  #19  
drunken science

Quote:
__________________


04082014, 12:48 PM  #20 
Registered User

__________________
2 easy 2 make hp turbos all cash 
Thread Tools  Search this Thread 
Display Modes  Rate This Thread 

