CLR cover

Problem 11: Conjugates and Rotations of Words

Two words $x$ and $y$ are conjugate if there exist two words $u$ and $v$ for which $x=uv$ and $y=vu$. They are also called rotations or cyclic shifts of one another. It is clear that conjugacy is an equivalence relation between words but it is not compatible with the product of words.

Show that two non-empty words of the same length are conjugate if and only if their (primitive) roots are conjugate.

A more surprising property of conjugate words is stated in the next question.

Show that two non-empty words $x$ and $y$ are conjugate if and only if $xz=zy$ for some word $z$.

References

  • M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Reprinted in 1997.