Let $G$ be a non-commutative group, and suppose we are given two elements $x, y \in G$ which are conjugate, i.e. we know there exists some $z \in G$ such that $zxz^{-1} = y$. Can we find $z$ given $x$ and $y$? When $G$ is the set of $n \times n$ invertible matrices, finding $z$ is simply a matter of finding a change of basis which takes $x$ to $y$. I'm interested in the more general case, where $G$ is an arbitrary non-commutative group. I am especially interested in the case where $G$ is the group of quaternions of unit norm.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ I'm not sure whether "can we find" makes sense in general, but if $G$ is a computable group, one has an algorithm whose input is a pair $(x,y)$, and: if $x,y$ are conjugate, outputs some $z$ with $zxz^{-1}=y$ (and if they're not conjugate possibly doesn't answer): just enumerate all $z$, test $zx=yz$ and stop when it's true. A better algorithm is when the algorithm can be improved to stop and say no (no pun intended!) when they're not conjugate. This is called solvable conjugacy problem, is well documented (and not always true for f.p. groups with solvable word problem). $\endgroup$– YCorCommented Apr 29, 2020 at 0:35
-
$\begingroup$ You seem to be just asking whether a group $G$ has a solvable conjugacy problem, which is one of the three fundamental decidability problems for groups posed by Dehn in 1911. $\endgroup$– Derek HoltCommented Apr 29, 2020 at 7:23
-
$\begingroup$ @DerekHolt no, because OP takes as an assumption that the elements are conjugate, and asks to output a conjugating element. As you know, plenty of algorithmic problems (e.g., isomorphism problem for hyperbolic groups, etc) have this kind of scheme (input X, output something about X, requiring the program to work if X satisfies some property P and possibly not halt otherwise— where usually property P is not decidable). $\endgroup$– YCorCommented Apr 29, 2020 at 7:54
-
$\begingroup$ @YCor OK, so this problem is solvable in theory for finitely (or even countably) generated groups with solvable word problem. But we seem to see a lot of questions of the type "Can we do this?" where it is not clear whether this means is this problem decidable or is there some practical algorithm to solve it. This one seems to be a mixture of both! $\endgroup$– Derek HoltCommented Apr 29, 2020 at 8:02
-
$\begingroup$ @DerekHolt (Yes, and even for recursive presentations.) Actually I don't even think that the OP considered the problem under an algorithmic angle (as in this recent question). Another example where the "algorithm" is only in principle: if we have two conjugate elements $g,h$ in a symmetric group (finite or infinite), we "choose" a length-preserving bijection between the sets of cycles of $g$ and $h$, we choose an element in each cycle, and then can induce a conjugating element. (...) $\endgroup$– YCorCommented Apr 29, 2020 at 8:45
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
2
For the case you are especially interested in, the answer is yes! The equation $zxz^{-1}=y$ is equivalent to $zx=yz$ and $z \neq 0$. For fixed unit quaternions $x,y \in \mathbb{H}^1$, this is linear in $z$ so can be solved by linear algebra. Explicitly, write $z=z_0 + z_1 i + z_2 j + z_3 ij$ with $z_i \in \mathbb{R}$ the unknowns, multiply on the right by $x$ and on the left by $y$, and setting these equal you get $4$ linear equations (in terms of the coefficients of $x,y$) in each coordinate.
If there is a nonzero solution, then the real dimension of the solution space is $2$ whenever $x,y$ are nonscalar: you can always post-conjugate by any nonzero element of $\mathbb{R}[y]$, which of course commutes with $y$, and the Skolem--Noether theorem says this all you can do.
From this solution space, you can pick your elements of norm $1$ by rescaling any nonzero solution; the total set of solutions looks like a circle.
-
$\begingroup$ This is a positive answer to the case of unit quaternions. $\endgroup$– YCorCommented Apr 29, 2020 at 0:29
-