How do I tell if matrices are similar? I have two $2\times 2$ matrices, $A$ and $B$, with the same determinant. I want to know if they are similar or not.
I solved this by using a matrix called $S$:
$$\left(\begin{array}{cc}
a& b\\
c& d
\end{array}\right)$$
and its inverse in terms of $a$, $b$, $c$, and $d$, then showing that there was no solution to $A = SBS^{-1}$. That worked fine, but what will I do if I have $3\times 3$ or $9\times 9$ matrices? I can't possibly make system that complex and solve it.  How can I know if any two matrices represent the "same" linear transformation with different bases?
That is, how can I find $S$ that change of basis matrix?
I tried making $A$ and $B$ into linear transformations... but without the bases for the linear transformations I had no way of comparing them.
(I have read that similar matrices will have the same eigenvalues... and the same "trace" --but my class has not studied these yet. Also, it may be the case that some matrices with the same trace and eigenvalues are not similar so this will not solve my problem.)
I have one idea. Maybe if I look at the reduced col. and row echelon forms that will tell me something about the basis for the linear transformation? I'm not really certain how this would work though? Please help.

If you have two specific matrices, A and B, here is a method that will work. It's messy, but it will work for any two matrices, regardless of size. First, rewrite the similarity equation in the form AS=SB, where S is a matrix of variables. Multiply out both matrices to obtain a set of n-squared linear equations in n-squared unknowns. Solve the system using Gaussian-Jordan elimination. You need to use the form of the Gaussian-Jordan algorithm that produces matrices in row-echelon form when there is no single solution to the system. The system of equations always has a solution, the zero matrix. If the Gaussian-Jordan elimination produces a single solution, the matrices are not similar. If there is more than one solution, the row-echelon matrix can be solved for a set of basis vectors of the solution space. Since the constant terms are all zero, any matrix generated by the basis vectors is a similarity matrix for A and B.
