Non-uniqueness of matrix in change of basis If two square complex normal matrices $A$ and $B$ have the same eigenvalues, counting multiplicities, they are similar, since
$$ A = P D P^{-1},\qquad B = QDQ^{-1}, $$
where $D$ is a diagonal matrix (whose eigenvalues are in a prescribed order), so $$A = [PQ^{-1}] B [PQ^{-1}]^{-1} =: R B R^{-1}$$ This matrices $R$ are not unique, but are they related only by permutation matrix? For example,
$$ D = \begin{pmatrix} -1 & & \\  & 1 &\\ & &1 \end{pmatrix} = \begin{pmatrix} 1 & & \\  &  & 1\\ & 1& \end{pmatrix} \begin{pmatrix} -1 & & \\  & 1 &\\ & &1 \end{pmatrix}  \begin{pmatrix} 1 & & \\  &  & 1\\ & 1& \end{pmatrix} = \Gamma D \Gamma^{-1} $$
so $\tilde R := P\Gamma^{-1}Q^{-1}$ is another matrix satisfying $A = \tilde R B \tilde R^{-1}$. This is the only possibilty, right?
 A: This is not the only possibility. You can easily create a counterexample by setting 
$$
\Gamma = \begin{pmatrix}
A_1 & & & \\ & A_2 & & \\ & & \ddots & \\ & & & A_r
\end{pmatrix}
$$
for a diagonal matrix
$$
D = \begin{pmatrix}
\lambda_1I_1 & & & \\ & \lambda_2I_2 & & \\ & & \ddots & \\ & & & \lambda_rI_r
\end{pmatrix}
$$
with invertible matrices $A_1,\ldots,A_r$ and identity matrices $I_1,\ldots,I_r$ which have the same sizes as $A_1,\ldots,A_r.$
A: This is not true. Suppose that $A=B=\operatorname{Id}$. Then, for any invertible matrix $R$, $A=RBR^{-1}$.
A: If all eigenvalues of $A$ are distinct and $P$ is unitary then $P$ is unique. For non-unitary $P$, it is a freedom to multiply each column by a scalar, i.e. $\tilde P=P\Lambda$ where $\Lambda$ is any non-singular diagonal matrix.
If there are repeating eigenvalues then the freedom is not only permutations of basis. In your example, the eigenspace for  $1$ is a plane, so the freedom is to pick any basis in it. Even for orthonormal bases (unitary $P$) there are infinity many choices, e.g. not only permutations work, but also rotations etc.
