patternMinor
Prove that a and b commute if and only if they are powers of the same word
Viewed 0 times
samethearecommuteprovewordthattheypowersand
Problem
Two words $a$ and $b$ commute if $ab=ba$.
How to demonstrate that $a$ and $b$ commute if and only if they are powers of
the same word ?
$ab=ba \Leftrightarrow \exists \space \tau \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'}$
The demonstration in this direction is trivial:
$\space \exists \space \tau \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'} \Rightarrow ab=ba$
But I don't manage to find an elegant solution for the other direction.
How to demonstrate that $a$ and $b$ commute if and only if they are powers of
the same word ?
$ab=ba \Leftrightarrow \exists \space \tau \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'}$
The demonstration in this direction is trivial:
$\space \exists \space \tau \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'} \Rightarrow ab=ba$
But I don't manage to find an elegant solution for the other direction.
Solution
By induction.
If $|a|=|b|$ then $a=b$ and we are done.
Otherwise, assume $|a|<|b|$.
Then $a$ is a prefix of $b$, so there is a word $c$ such that $b = ac$.
Now $ab = ba$ implies $aac=aca$, or, after deleting prefix $a$, $ac=ca$. By the inductive property $a$ and $c$ are both powers of the same word $\tau$, and so is $b$.
If $|a|=|b|$ then $a=b$ and we are done.
Otherwise, assume $|a|<|b|$.
Then $a$ is a prefix of $b$, so there is a word $c$ such that $b = ac$.
Now $ab = ba$ implies $aac=aca$, or, after deleting prefix $a$, $ac=ca$. By the inductive property $a$ and $c$ are both powers of the same word $\tau$, and so is $b$.
Context
StackExchange Computer Science Q#75378, answer score: 4
Revisions (0)
No revisions yet.