Proof about cycle with odd length

In summary, it is shown that if a cycle ##\alpha## has an odd length, then it can be written as the square of an integer power of itself. This is proven by showing that ##\alpha = \alpha^{s+1}## and using the fact that ##s## is odd to write ##\alpha## as the square of ##\alpha^{k+1}##.
  • #1
fishturtle1
394
82

Homework Statement


In the following problems let ##\alpha## be a cycle of length ##s##, and say
##\alpha = (a_1a_2 . . . a_s)##.

5) If ##s## is odd, ##\alpha## is the square of some cycle of length s. (Find it. Hint: Show ##\alpha = \alpha^{s+1}##)

Homework Equations

The Attempt at a Solution


I know ##(12345)(12345) = (12345)## and ##(1234)(1234) = (13)(24)##. And I think I can prove this is true for any integer n, such that if a cycle ##\alpha## has an odd length, then squaring it produces another cycle of odd length, and ##\alpha## has an even length, s, then its square is the product of two disjoint cycles, each of length s/2. I guess I've pretty much restated the problem... I'm stuck.

For the hint.. I know ##\alpha## of length ##s## has ##\alpha## distinct powers but I'm not sure how to prove it.

Sorry this is so bare bones, thank you for any help
 
Physics news on Phys.org
  • #2
fishturtle1 said:
I know ##(12345)(12345) = (12345)##
That doesn't look right. I get ##(12345)(12345)=(13524)##.
The 'square root' of (12345) is (13524) because (13524)(13524)=(12345).

The hint is a good one. Have you tried proving it?
What is the position in the cycle to which the ##k##th element ##a_k## is mapped by one application of ##\alpha## (in other words, find an expression in terms of ##k## for the index ##j## such that ##\alpha a_k=a_j##).

Then what about two applications of ##\alpha##. What about ##s## applications? What about ##s+1##?
 
  • #3
andrewkirk said:
That doesn't look right. I get ##(12345)(12345)=(13524)##.
The 'square root' of (12345) is (13524) because (13524)(13524)=(12345).

The hint is a good one. Have you tried proving it?
What is the position in the cycle to which the ##k##th element ##a_k## is mapped by one application of ##\alpha## (in other words, find an expression in terms of ##k## for the index ##j## such that ##\alpha a_k=a_j##).

Then what about two applications of ##\alpha##. What about ##s## applications? What about ##s+1##?
Thanks for the help and correction, I agree that (12345)12345) = (13524)

So we can write ##\alpha^na_i = a_j## where ##j = (i + n) \mod s##
Therefore ##\alpha a_i = a_{((i + 1) \text{mod s})}##
and ##\alpha^{s+1}a_i = a_{((s+1+i) \text{mod s})}##
Since (i + 1) = (s + 1 + i) (mod s)
we have ##\alpha a_i = \alpha^{s+1}a_i##
##\alpha a_ia_i^{-1} = \alpha^{s+1}a_ia^{-1}##
##\alpha e = \alpha^{s+1}e##
##\alpha = \alpha^{s+1}##
[]

##\alpha^sa_i = a_{i + s} = a_i##
##\alpha^{s+1}a_i = a_{i + s + 1} = a_{i + 1}##

I'm not sure how to apply this to the original problem but ill keep thinking.. I also thought of this which I think is a proof in response to the "Find it" part of the hint.

Proof: Suppose ##\alpha## is a cycle of length ##s## where ##s## is an odd integer. Then we can write ##\alpha## as ##(a_1a_3...a_sa_2a_4...a_{s-1}).## But ##(a_1a_3...a_sa_2a_4...a_{s-1}) = (a_1a_2...a_s)(a_1a_2...a_s).## Let ##\beta = (a_1a_2..a_s).## Note that ##\beta## is a cycle of length s. Then ##\alpha = \beta^2##. This concludes the proof.
 
  • #4
Give that ##\alpha=\alpha^{s+1}## and ##s## is odd, how can you write ##\alpha## as the square of an integer power of itself?
 
  • #5
andrewkirk said:
Give that ##\alpha=\alpha^{s+1}## and ##s## is odd, how can you write ##\alpha## as the square of an integer power of itself?
s is odd, so we can write s = 2k + 1, where k is an integer.
We note that ##\alpha^n## is a cycle of length s for all integers n.
Then ##\alpha = \alpha^{s+1} = \alpha^{2(k+1)} = \alpha^{k+1}\alpha^{k+1}##.
so ##\alpha## is the square of ##\alpha^{k+1}##.
 

1. What is a cycle with odd length?

A cycle with odd length is a type of graph, where the number of edges in a closed path or cycle is an odd number. This means that there are an odd number of vertices connected in a loop, with no repeating edges or vertices.

2. How do you prove that a cycle has an odd length?

To prove that a cycle has an odd length, you can use the fact that the sum of all the degrees (number of edges connected to a vertex) in a graph is always an even number. Since a cycle has no endpoints, each vertex will have at least two edges connected to it. Therefore, the sum of degrees in a cycle will always be an even number, unless the cycle has an odd length.

3. Can a cycle have an even length?

Yes, a cycle can have an even length. In fact, cycles can have any positive integer length. However, if a cycle has an even length, it is not considered an "odd length" cycle.

4. How is the length of a cycle related to its properties?

The length of a cycle is related to its properties in that it can determine whether the graph is bipartite (can be divided into two sets of vertices with no edges connecting vertices within the same set) or not. A cycle with an even length will always be bipartite, while a cycle with an odd length will never be bipartite.

5. Why is it important to understand cycles with odd length?

Cycles with odd length are important in graph theory, as they have various applications in computer science, electrical engineering, and other fields. They can also help determine the properties of a graph and aid in solving certain problems, such as finding the shortest path between two points.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Special and General Relativity
3
Replies
75
Views
3K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
932
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
Back
Top