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?
Best Answer
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$.