Detecting unitary $U$ if $U^* AU$ is given Let $\phi: M_n (\mathbb C) \rightarrow M_n (\mathbb C)$ be a given map of which we know that it is of the form $A \mapsto U^* AU$ where $U \in M_n (\mathbb C)$ is a unitary. I guess the unitary $U$ will be unique up to multiplication with elements of the circle $\mathbb T \subseteq \mathbb C$. Is there an algorithm to find out how $U$ has to look like for a certain $\phi$?

We can extract all the information we need from $\phi$ by plugging in matrices of the form $E_{jk} = e_je_k^*$ (the matrix with a $1$ in the $j,k$ entry and zeros everywhere else).  We can construct a suitable $U$ as follows:
If $v_1,\dots,v_n$ denote the columns of $U^*$, then we find
$$
\phi(E_{ij}) = U^*e_je_k^*U = v_jv_k^*
$$
With that in mind, proceed as follows: for $j = 1,\dots,n$, compute $\phi(E_{jj}) = v_jv_j^*$.  The matrix $\phi(E_{jj})$ has at least one non-zero column; normalize this column to produce $v_j$.  With that, we now have $n$ vectors $v_1,\dots,v_n$, and taking the matrix $U$ such that the columns of $U^*$ are $v_1,\dots,v_n$ will almost give us a $U$ which induces the transformation $\phi$.
From there, we need to multiply each $v_j$ by a suitable scalar.  In particular, it is necessary that the $v_j$ satisfy $\phi(E_{ij})(p,q) = v_i(p)\overline{v_j(q)}$.
That is, we could apply the following steps:


*

*Find a non-zero column of $\phi(E_{11})$; normalize it to produce $v_1$

*For $j = 2,\dots,n$: 


*

*Find a non-zero column of $\phi(E_{1j})$; set it equal to $v_j$

*Find a non-zero entry of the matrix $\phi(E_{1j})$, say it's the $p,q$ entry. 

*Multiply $v_j$ by a constant in order to ensure that
$$
[\phi(E_{1j})](p,q) = v_1(p)v_j(q)
$$




Notably, we find that if $U$ and $V$ are unitary matrices which induce the same map, then
$$
U^*AU = V^*AV \qquad \text{for all }A \iff\\
AUV^* = UV^*A \qquad \text{for all }A
$$
which implies that $UV^*$ is a multiple of the identity.  That is, $U$ and $V$ will induce the same map $\phi$ if and only if $UV^* = \omega I$ for some $\omega \in \Bbb T$.  So, we must have $U = \omega V$ for some $\omega \in \Bbb T$.
