Matrix is conjugate to its own transpose Mariano mentioned somewhere that everyone should prove once in their life that every matrix is conjugate to its transpose.
I spent quite a bit of time on it now, and still could not prove it. At the risk of devaluing myself, might I ask someone else to show me a proof?
 A: Theorem 66 of [1] proves that a square matrix (over an arbitrary field) is conjugate to its transpose via a symmetric matrix.
[1] Kaplansky, Irving Linear algebra and geometry. A second course. Allyn and Bacon, Inc., Boston, Mass. 1969 xii+139 pp.
A: A different approach, by the principle of irrelevance of algebraic inequalities:
a) Over an infinite field:
1) Diagonalizable matrices: If $A$ is diagonalizable to $D$ via $P$ then it is similar to its transpose, since $D$ being symmetric implies
$PAP^{-1}=D=D^T=(PAP^{-1})^T = P^{-T}A^TP^T,$
so that
$$A^T=QAQ^{-1}, Q:=P^TP.$$
2) Similarity is polynomial: Two matrices A,B are similar iff they have the same invariant factors $\alpha_i(A)=\alpha_i(B)$, which are polynomials in the entries of the matrices.
3) Extension to all matrices: Let $f_i$ be the polynomial $\alpha_i(A)-\alpha_i(A^T)$ on the entries of $A$.
Consider the set of matrices with pairwise different eigenvalues, which are diagonalizable. These are precisely those which do not annihilate the discriminant of their characteristic polynomial, which is a polynomial $g$ in the entries of the matrix.
Thus we have that $g(A)\neq0$ implies $f_i(A)=0$. By the irrelevance of algebraic inequalities, $f_i(A)=0$ for all matrices, i.e., $A^T$ is similar to $A$.
b) Over a finite field:
Matrices over a finite field $K$ can be seen as matrices over the infinite field $K(\lambda)$ ($\lambda$ trascendental over $K$), so by part a) they also satisfy the result.
A: This question has a nice answer using the theory of modules over a PID. Clearly the Smith normal forms (over $K[X]$) of $XI_n-A$ and of $XI_n-A^T$ are the same (by symmetry). Therefore $A$ and $A^T$ have the same invariant factors, thus the same rational canonical form*, and hence they are similar over$~K$.
*The Wikipedia article at the link badly needs rewriting.
A: I had in mind an argument using the Jordan form, which reduces the question to single Jordan blocks, which can then be handled using Ted's method ---in the comments.
There is one subtle point: the matrix which conjugates a matrix $A\in M_n(k)$ to its transpose can be taken with coefficients in $k$, no matter what the field is. On the other hand, the Jordan canonical form exists only for algebraically closed fields (or, rather, fields which split the characteristic polynomial)
If $K$ is an algebraic closure of $k$, then we can use the above argument to find an invertible matrix $C\in M_n(K)$ such that $CA=A^tC$. Now, consider the equation $$XA=A^tX$$ in a matrix $X=(x_{ij})$ of unknowns; this is a linear equation, and over $K$ it has non-zero solutions. Since the equation has coefficients in $k$, it follows that there are also non-zero solutions with coefficients in $k$. This solutions show $A$ and $A^t$ are conjugated, except for a detail: can you see how to assure that one of this non-zero solutions has non-zero determinant?
A: Although this reply is not answering the original question that was asked, I think it's worth pointing out that in the original question it's very important to be working over a field: there are counterexamples if you work over the integers.  For instance, the integral matrix
$$
A =  \begin{pmatrix}1&-5\\3&-1\end{pmatrix}
$$
is not conjugate to $A^\top$ in ${\rm M}_2(\mathbf Z)$, although of course $A$ and $A^\top$ are conjugate in ${\rm M}_2(\mathbf Q)$.
More generally, two integral matrices with the same irreducible characteristic polynomial over $\mathbf Z$ need not be conjugate as integral matrices. See here, in particular Example 3.7.
This phenomenon (failure of integral matrices to be integrally conjugate to their transposes) is related to the behavior of ideals in rings of algebraic integers.
