Proving t a^-1 = b: Permutations & Cycles Homework

In summary, S is a set of elements and t is an element of S defined as the cycle (1,2...k) of length k with k<=n. Part a) proves that if a is an element of S, then ata^-1=(a(1),a(2),...,a(k)) is also a cycle of length k. Part b) states that for any cycle of length k, there exists a permutation a in S such that ata^-1 is equal to that cycle.
  • #1
kathrynag
598
0

Homework Statement


Let t be an element of S be the cycle (1,2...k) of length k with k<=n.
a) prove that if a is an element of S then ata^-1=(a(1),a(2),...,a(k)). Thus ata^-1 is a cycle of length k.
b)let b be any cycle of length k. Prove there exists a permutation a an element of S such that ata^-1=b.




Homework Equations





The Attempt at a Solution


We assume t is an element of S and a is an element S.
By definition of elements of S if t is in S, we have a determined by t(1), t(2),...,t(n)
Furthermore if a is in S, we have a(1), a(2)...a(n).
That's as far as I get.
 
Physics news on Phys.org
  • #2
hi kathrynag! :smile:

just read out that equation in English …
kathrynag said:
ata^-1=(a(1),a(2),...,a(k))

… so what, for example, does ata^-1 do to a(2) ? :wink:
 
  • #3
Does it go to 2?
 
  • #4
Ok if a is defined by 1--->a(1), 2-----a(2),k--->a(k), then a^-1 is defined as a(1)-->1,a(2)--->2, a(k)--->k
Then ata^-1 for a(2) is a(t(2))=a(2)
 
  • #5
kathrynag said:
Does it go to 2?

a-1 sends it to 2 …

so what does ata-1 send it to?
 
  • #6
a(t(2))
t(2)=2
a(2)
 
  • #7
kathrynag said:
Let t be an element of S be the cycle (1,2...k)
kathrynag said:
a(t(2))
t(2)=2
a(2)

ah! no, you're misunderstanding the notation for a cycle …

(1,2...k) means that it sends 1 to 2, 2 to 3, … and k to 1. :wink:

so t(2) = … ?​
 
  • #8
3
so we are left with a(3)=4
 
  • #9
kathrynag said:
3
so we are left with a(3)=4

no!

you're not told anything about a, are you?

a(3) is just a(3) ! :bigginr:

(and I'm off to bed :zzz: … see you tomorrow!)
 
  • #10
I thought I could do this:
By definition of elements of S if t is in S, we have a determined by t(1), t(2),...,t(n)
Furthermore if a is in S, we have a(1), a(2)...a(n).
 
  • #11
So I have ata^-1=at(n)
because a^-1 sends a(1)--->1,a(2)--->2,...a(n)--->n
By defininition of t, we have a(1), a(2), a(3)...a(k). We go to k because our definition of t says k<=n.


For b,
Let b be any cycle of length k.
We have (1,2...k). I'm not sure how to show the rest.
 
  • #12
hi kathrynag! :smile:

(just got up :zzz: …)
kathrynag said:
So I have ata^-1=at(n)
because a^-1 sends a(1)--->1,a(2)--->2,...a(n)--->n
By defininition of t, we have a(1), a(2), a(3)...a(k).

do you mean we have (a(1), a(2), a(3),...a(k))?

anyway, before we go any further, i need to know: what exactly is S? :confused:
 

1. What is the definition of a^-1 in permutations and cycles?

In permutations and cycles, a^-1 represents the inverse of a permutation or cycle. This means that when a permutation or cycle is applied to a set of elements, a^-1 will undo the changes made by a, returning the elements to their original order.

2. How do you prove that a^-1 = b in permutations and cycles?

To prove that a^-1 = b in permutations and cycles, you need to show that a and b have the same effect when applied to a set of elements. This can be done by applying both a and b to the same set of elements and showing that the resulting permutation or cycle is the same.

3. Can a^-1 ever equal b in permutations and cycles?

Yes, it is possible for a^-1 to equal b in permutations and cycles. This can happen when a and b are both identity permutations or cycles, meaning they have no effect when applied to a set of elements.

4. Are there any special cases where proving a^-1 = b is more difficult?

Yes, proving a^-1 = b can be more difficult in cases where a and b have different cycle lengths or when they have different element orders. In these cases, it may be necessary to break down a and b into smaller cycles and apply the definition of a^-1 to each one individually.

5. How can I use the concept of a^-1 = b in real-world applications?

The concept of a^-1 = b in permutations and cycles can be used in various real-world applications, such as cryptography and data encryption. It can also be used in computer algorithms for efficient sorting and organizing of data. Additionally, understanding this concept can help with problem-solving and critical thinking skills.

Similar threads

Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
499
Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
2
Views
261
Mastering Combinatorics: Exploring the Formula for Permutations
    • Calculus and Beyond Homework Help
Replies
1
Views
597
Proof that T is bounded below with ##inf T = 2M##
    • Calculus and Beyond Homework Help
Replies
4
Views
234
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
573
Lemma: Extracting a convergent subsequence
    • Calculus and Beyond Homework Help
Replies
11
Views
1K
Prove ##a + b = b + a## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
808
Proving ##(cof ~A)^t ~A = (det A)I##
    • Calculus and Beyond Homework Help
Replies
4
Views
959
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
    • Calculus and Beyond Homework Help
Replies
4
Views
494
Prove: Limit Point of H ∪ K if p is Limit Point of H or K
    • Calculus and Beyond Homework Help
Replies
5
Views
887

Hot Threads

Recent Insights

Back
Top