Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Meepi Group Title

Let \(k\) be a positive integer with \(k \leq |S_n|\). The symmetric group \(S_n\) acts on the set B consisting of all k-element subsets of \({1, \ldots , n}\) by \(\sigma \cdot {a_1, \ldots, a_k}={\sigma(a_1),\ldots,\sigma(a_k)}\). Determine for which values of \(k\) the actions of \(S_n\) on k-element subsets is faithul

  • 11 months ago
  • 11 months ago

  • This Question is Closed
  1. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Let k be a positive integer with \(k \leq n\). The symmetric group \(S_n\) acts on the set \(B\) consisting of all \(k\)-element subsets of \(\{1,…,n\}\) by \(\sigma⋅\{a_1,\ldots,a_k\}=\{σ(a1),\ldots,σ(ak)\}\). Determine for which values of \(k\) the actions of \(S_n\) on \(k\)-element subsets is faithul

    • 11 months ago
  2. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Egh, I can't type: \(\{\sigma(a_1), \ldots , \sigma(a_k)\}\)

    • 11 months ago
  3. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \(S_n\) is a group and it's operation is symmetric?

    • 11 months ago
  4. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \(S_n\) is the symmetric group of the set \(\{1, \ldots, n\}\)

    • 11 months ago
  5. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I know that if k = n, the operation is not faithful since any permutation will still give the n-element subset, and that if k = 1 it i's trivially faithful, but I'm stuck on proving whether or not it's faithful for 1 < k < n

    • 11 months ago
  6. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    How would it not be faithful?

    • 11 months ago
  7. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    An action is faithful if different elements of \(S_n\) induce different permutations of B, and if k = n, there is only one n-element subset, which every element of S_n maps to. ie if for different \(g, h \in S_n\), \(g\cdot x\neq h\cdot x\) for some \(x \in B\)

    • 11 months ago
  8. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Hmmm, one thing I can say is that the set of all subsets is the power set and it has cardinality \(2^k\)

    • 11 months ago
  9. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    So is \(S_n\) full of \(n\) mappings which will permute the elements in \(B\)?

    • 11 months ago
  10. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \(S_n\) is the set of n! distinct permutations of the set \(\{1, 2, ..., n\}\) it acts on B by permuting it's elements ie: if we have the permutation (1 2 3) (1 gets send to 2, 2 to 3, 3 to 1) act on {1, 2} we get \((1\,\,2\,\,\,3) \cdot \{1,2\}=\{2, 3\}\)

    • 11 months ago
  11. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Should it result in \(\{3,1\}\)?

    • 11 months ago
  12. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    the action is defined as \(\sigma \cdot \{a_1, ... , a_k\} = \{\sigma(a_1), ... ,\sigma(a_k)\}\) so in the case that \(\sigma =\)(1 2 3), \(\sigma \cdot \{1, 2\}=\{\sigma(1), \sigma(2)\}=\{2, 3\}\)

    • 11 months ago
  13. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Okay, I think I get that much now.

    • 11 months ago
  14. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I've seen this before, but the notation we use for permutation was maybe backwards.

    • 11 months ago
  15. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    The number of \(k\) element subsets in \(n\) is \(\binom nk\)

    • 11 months ago
  16. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    It's faithful if no two permutations produce equivalent sets?

    • 11 months ago
  17. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Consider what happens with some concrete examples or concrete permutations.

    • 11 months ago
  18. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    now if k =1, there exists two permutations \(\sigma\) and \(\tau\) such that \(\sigma(a) \neq \tau(a)\) if we let \(x = \{a\}\) (which is a subset of {1, ..., n} of cardinality 1) then without loss of generality we have \(\sigma \cdot x \neq \tau \cdot x\), so action is trivial if k is one, if k = n, then there is only one subset of {1, ..., n} namely that set itself so every permutation will give you that subset. now I think for 1 < k < n I will have to show that the permutation representation is injective. I think if we let \(\sigma, \tau\) be different permutations again, then without loss of generality \(\sigma(a_1) = x, \tau(a_2) = x\) then we can choose a subset z of cardinality k so that x and \(a_1\) are in the subset, but \(a_2\) isn't (since k < n, we have at least 1 element not in the subset), then \(\sigma \cdot z \neq \tau \cdot z\), since \(\sigma \cdot z\) contains x, and \(\tau \cdot z\) doesn't, so the action is faithful if k<n

    • 11 months ago
  19. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I think this works :D

    • 11 months ago
  20. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    There only needs to be two distinct permutations which don't result in the same subset?

    • 11 months ago
  21. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    No, for any two distinct permutations there must be a subset so that \(\sigma \cdot x \neq \tau \cdot x\). In this proof i think i managed to show that we can always construct at least 1 subset of length k which does this

    • 11 months ago
  22. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    So if I get this right: If the permutations are distinct, there has to be an output where the permutations have a different input to output it. You then find a subset which has the input for one of the permutations but lacks the needed input for the second permutation. Thus there is an output which one has and the other doesn't.

    • 11 months ago
  23. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yes

    • 11 months ago
  24. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    and such a subset always exists, since there is at least 1 element from {1, ..., n} not in the subset

    • 11 months ago
  25. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You can ensure an excluded input is excluded, and you can also ensure the necessarily included input gets included?

    • 11 months ago
  26. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, since we only consider 2 elements, a1 and x, and for 1 < k < n, k is at least 2 :)

    • 11 months ago
  27. wio Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    What if a1 and a2 are greater than k, does that matter?

    • 11 months ago
  28. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Not really, since k is just how much elements are in the subset

    • 11 months ago
  29. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ie if we have k = 2, and two permutations \(\sigma(7) = 8\) and \(\tau(8)=8\) then we choose a subset which doesn't have 7 in it, but contains 8 and any other element, say 5 so we get {5, 8} now even if the 2 permutations map 5 to the same element, 8 still gets mapped to a different one

    • 11 months ago
  30. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    two permutations such that*

    • 11 months ago
  31. Meepi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Thanks for the help by the way, trying to explain it to someone else always helps it seems :)

    • 11 months ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.