Simultaneous diagonalization Given two symmetric matrices $A,B\in\Bbb R^n$ how can we find if they are simultaneously diagonalizable? If they have such property how can we find $U$ such that $UAU'$ and $UBU'$ are simultaneously diagonalized efficiently?
 A: It suffices to use the fact that any two commuting matrices are simultaneously upper-triangularizable. In particular, because $A$ and $B$ commute, there exists a unitary matrix $U$ such that both $UAU'$ and $UBU'$ are upper-trinagular.
Note, however, that $(UAU')' = UAU'$, and $(UBU')' = UBU'$. So, these matrices are upper triangular and symmetric.  We may therefore conclude that they are both diagonal.  Thus, $U$ is a unitary matrix that simultaneously diagonalizes $A$ and $B$.
This can be done if and only if $A$ and $B$ commute.

One method of finding this $U$ is given in Horn and Johnson, which I don't have on hand for reference.  The key is to do this recursively, noting first that any two commuting matrices have a common eigenvector.
In particular: if $A u = Bu$, with $\|u\| = 1$, then take $u$ to be the first column of the unitary matrix $U_1$.  We then have
$$
U_1AU_1' = \pmatrix{\lambda & *\\0&\tilde A} \quad 
U_1BU_1' = \pmatrix{\lambda & *\\0&\tilde B}
$$ 
Now, suppose that $\tilde V \tilde A \tilde V'$ and $\tilde V \tilde B \tilde V'$ is upper triangular for some unitary $\tilde V$. Then, define
$$
V = \pmatrix{1&0\\0&\tilde V}
$$
verify that both $(VU_1) A(VU_1)'$ and $(VU_1)B(VU_1)'$ will be upper-triangular.
A: Two diagonalizable matrices $A$ and $B$ are simultaneously diagonalizable if and only they commute, that is, $AB=BA$. For details see this answer. Note that we do not need to assume they are symmetric, only that they are diagonalizable. 
I don't know of a good answer to the question of finding a unitary operator $U$ that diagonalizes some given commuting symmetric matrices. Of course, one can just brute force find a common eigenbasis (see Theorem 5.1 in the notes referenced in the linked answer), but this seems inefficient, and I don't know of any better algorithms for when $A,B$ are large.
