Let $\l_1,\ldots,\l_m$ be all pairwise distict eigen-values of $A$ with eigen-spaces $E_1,\ldots,E_m$. These are pairwise orthogonal and the eigen-spaces of $B=PAP^{-1}$ are $P(E_j)$. Since $B$ is unitary these spaces form a direct orthogonal decomposition of $\C^n$; it follows that there are isometries $U_j:E_j\rar P(E_j)$. Put $U|E_j=U_j$, then $UAU^{-1}=B$.