Example

$ \def\sa#1{\tt{#1}} $

The word $\sa{abaab}=\sa{aba}\cdot\sa{ab}$ is a conjugate of $\sa{ababa}=\sa{ab}\cdot\sa{aba}$.

Below are the seven conjugates of $\sa{aabaaba}$ (left) and the three conjugates of $\sa{aabaabaab}$ (right).

$\sa{aabaabaab}=(\sa{aab})^3$ and $\sa{baabaabaa}=(\sa{baa})^3$ are conjugate, like their respective roots $\sa{aab}$ and $\sa{baa}$.

In the preceding example (left), $\sa{aabaaba}$ and $\sa{baabaaa}$ are conjugate and $\sa{aabaaba}\cdot\sa{aa}=\sa{aa}\cdot\sa{baabaaa}$.

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.

125 Problems in Text Algorithms

Example

Problem 11: Conjugates and Rotations of Words

References