Given two similar matrices $A$, $B$, is there a way to find an invertible matrix $P$ such that $A=P^{-1}BP$? I was wondering if given two similar square matrices $A$ and $B$ would always be possible to find an matrix $P\in GL(n)$ such that $A=P^{-1}BP$.
thank you!
 A: The short answer will be no. For example, let $A\neq I$ and $B=I$. Then clearly $P^{-1}BP=P^{-1}IP=I\neq A$ for all $P\in GL_n(F)$.
You are looking for matrix similarity, and you can read about the conditions in the link above.
     --
Edit: As the question was edited, now the answer is yes: For every matrix $A$ one can find its Jordan canonical form, $J_A$. Find the base change matrix $P_A$. Since $A$, $B$ are similar if and only if $J_A=J_B$, we have $J=P_AAP_A^{-1}=P_BBP_B^{-1}$. So $A=(P_B^{-1}P_A)^{-1}B(P_B^{-1}P_A)$
A: Let $J$ the Jordan canonical matrix similar to $A$ and $B$ so we can find the change basis matrices $Q$ and $S$ such that
$$A=QJQ^{-1}\quad;\quad B=SJS^{-1}$$
hence with $P=Q^{-1}S$ we have $A=P^{-1}BP$.
A: Let $K$ be a subfield of $\mathbb{C}$. We assume that $A,B\in M_n(K)$ are similar (that is,  there is $P\in M_n(K)$ s.t. $\det(P)\not= 0$ and $PA=BP$). Note that we can always choose $P$ in $M_n(K)$.
Of course, it is important not to calculate Jordan's forms of $A,B$.
METHOD 1.
i) Solve the linear system $PA=BP$; the set of solutions $E$ is a sub-vector space of $M_n(K)$ of dimension $k=dim(C(A))\geq n$. Note that, using the tensor product, there are methods that permit to solve such a system with complexity in $O(n^3)$ (and not in $O(n^6)$).
Since there is $P\in E$ s.t. $\det(P)\not= 0$, $\{P\in GL_n(K);PA=BP\}$ is Zariski open dense in $E$.
ii) Thus, it suffices to randomly choose the $k$ parameters that define an element of $E$ to obtain a required solution with probability $1$.
METHOD 2.
We can also use the Frobenius form over $K$. Indeed, $A,B$ have same Frobenius form $F$:
$A=QFQ^{-1},B=RFR^{-1}$ and the sequel is easy. 
EDIT. Here is a quick history of the progress made in calculating the Frobenius form.
i) in "Nearly  optimal  algorithms  for  canonical  matrix  forms. SIAM  Journal  on Computing, 24:948–969, 1995"
M. Giesbrech gives a randomized method: a Las  Vegas  algorithm  can  be  used  to  compute  both
the Frobenius form and a Frobenius transition matrix for a given $n\times n$ matrix over a field $F$ using an expected number of operations over $F$ that is in $O(n^3)$, with standard matrix and polynomial arithmetic, whenever $F$ has at least $n^2$ elements (to ensure a probability of success at least
$1/2$), and using an expected number of
operations in $O(n^3\log_q(n))$ if $F$ is a finite field with size $q$.
ii) Storjohann [1997] exposed a deterministic method  whose complexity is $O(n^3)$. cf.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2505
However, the previous method does not give, at the same time, the matrix of change of basis.
iii) In  "Algorithms for similarity transforms.  In
Seventh Rhine Work-shop on Computer Algebra
, Bregenz, Austria, March 2000"
A. Storjohann and G. Villard obtain (with the same complexity), at the same time, the Frobenius form $F$ and the transform matrix $V$ .
There is a gap. None of the previous methods allow to use the fast multiplication of Strassen (in $O(n^{2.81})$). 
iv) W. Eberly, in "Asymptotically efficient algorithms for the
Frobenius form. Technical report, Department of
Computer Science, University of Calgary, 2000"
gives $F,V$ thanks to a Las Vegas algorithm (using Strassen) that has complexity $O(n^{2.81}\log(n))$.
Note that, unlike an urban legend, the methods of Coppersmith-Winograd and of Le Gall are practically useless. 
v) In 2007, C. Pernet and A. Storjohann, in "Faster Algorithms for the Characteristic Polynomial. ISSAC"
give $F$ (but not $V$) with a Las Vegas algorithm in $O(n^{2.81})$.
This is the state of play in 2011-2013. I don't know if an algorithm giving $F, V$ in $O(n^{2.81})$ was found in recent years.
