Sufficient way for finding similar matrices Similar matrices share few properties, I was wondering,is there a sufficient way for making sure two matrices are similar?
Is the process of finding the minimal polynomial is the way?
 A: Over the complex numbers or an algebraically closed field
(over a general field, one can apply the above over an algebraic closure):

The matrices $A,B$ are similar if and only if the characteristic polynomials are the same and for $P$  the (shared) characteristic polynomial
  $$\operatorname{rank} Q(A) =\operatorname{rank} Q(B) $$
  for every polynomial $Q$ diving $P$.

One can replace "characteristic" by "minimal."
In a way, this is an 'obfuscated' version of the criterion Omnomnomnom gave.
A: Unfortunately, even two matrices with the same characteristic polynomial and the same minimal polynomial are not necessarily similar. Consider:
$$\begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$
Characteristic polynomials are $(x-1)^4$, minimal polynomials are $(x-1)^2$.
Two matrices will be similar if and only if they are both similar to the same matrix in Jordan Canonicial Form (up to rearrangement of the Jordan blocks). 
A: One nice characterization over $\Bbb C$ is as follows: the matrices $A$ and $B$ are similar if and only if for every $k = 1,2,3,\dots$ and every $\lambda \in \Bbb C$,
$$
\DeclareMathOperator{\rk}{rank}
\rk((A-\lambda I)^{k-1}) - \rk((A-\lambda I)^{k}) = 
\rk((B-\lambda I)^{k-1}) - \rk((B-\lambda I)^{k})
$$
For a given $\lambda$ and $k$, the number $\rk((A-\lambda I)^k) - \rk((A-\lambda I)^{k-1})$ can be characterized in terms of Jordan form as "the number of Jordan blocks associated with $\lambda$ that have size at least $k$".  Note that we define $A^0 = B^0 = I$.
