Show that two matrices with the same eigenvalues are similar First assume that $A$ and $B$ are $p \times p$ matrices and that $\lambda_1,\ldots , \lambda_p$ are distinct eigenvalues of $A$ and $B$. I want to show that $A$ and $B$ are similar.

Here is my approach: 
The goal is to show that there is a nonsingular $p \times p$ matrix  $P$ such that $B = P^{-1}A P$.
We know the following is satisfied for each eigenvalue
$$ A \textbf x_j = \lambda_j \textbf x _j  \text { where } j = 1,\ldots,p$$
and $\textbf x_j$ are the eigenvectors. Since $A$ and $B$ share the same eigenvectors, $B$ must satisfy the following 
$$ B \textbf x_j = \lambda_j \textbf x _j  \text { where } j = 1,\ldots,p$$
Thus we have
$$ B \textbf x_j = A \textbf x_j$$
We can take the $\textbf x_j$ as the columns of the matrix $P$ and get
$$BP=AP$$
we know that the columns of $P $ are linearly independent so the matrix must be non singular. Unfortunately this means that 
$$A=B$$
but this is not what we wanted to show. Am I on the right track? Is there an obvious mistake I am making?
The idea in your approach almost works. But you cannot assume that $A$ and $B$ have the same eigenvectors! So you will have
$$
Ax_j=\lambda_jx_j,\ \ \ By_j=\lambda_jy_j. 
$$
As $\lambda_1,\ldots,\lambda_p$ are distinct, $x_1,\ldots,x_p$ and $y_1,\ldots,y_p$ are each linearly independent, so they are bases. Let $P$ be the change of basis $y\to x$, i.e. $P$ is the matrix such that $Py_j=x_j$, $j=1,\ldots,n$. It is clearly nonsingular: if $P(c_1y_1+\cdots+c_py_p)=0$, then
$$
0=c_1P(y_1)+\cdots+c_pP(y_p)=c_1x_1+\cdots+c_px_p,
$$
so $c_1=\cdots=c_p=0$. Now, for each $j$,
$$
PBy_j=\lambda_j Py_j=\lambda_jx_j=Ax_j=APy_j.
$$
As the $y$ are a basis, we get that $PB=AP$, i.e. $PBP^{-1}=A$.
Two matrices with same eigenvalues are similar if they are non-singular! If the matrices are singular they may or may not be similar!

eg:
  $$M_1=
\begin{bmatrix}
   1 &amp; 0 &amp; 0 \\
   0 &amp; 0 &amp; 1 \\
   0 &amp; 0 &amp; 0 \\
  \end{bmatrix}$$
 $$ M_2=
\begin{bmatrix}
   1 &amp; 0 &amp; 0 \\
   0 &amp; 0 &amp; 0 \\
   0 &amp; 0 &amp; 0 \\
  \end{bmatrix}$$

here $M_1$ &amp; $M_2$ have the same set of eigenvalues! but they are not similar.