I am interested in a class of $2n\times 2n$ unitary matrices with complex entries (if you prefer, we can replace "unitary" with "self-adjoint").
I know that all the eigenvalues of matrices in this class have (algebraic) multiplicity one or two. Some very interesting phenomena happens when all the eigenvalues have multiplicity two. Is there a way for me to tell when that happens based on the entries of the matrix, other than computing them by brute force?
Assuming it is feasible to compute the characteristic polynomial, $p(x)$, in your situation, (which can certainly be done in principle if you know the matrix entries) there is a simple strategy. Given the information you already have, all roots have multiplicity two if and only if ${\rm gcd}(p(x),p^{\prime}(x))$ has degree $n.$ Note that this does not require factorization of $p(x),$ it only requires the Euclidean algorithm for polynomials, which is simple to implement computationally (here, $p^{\prime}(x)$ just denotes the derivative of $p(x)$).
I'm assuming that your are working over an algebricaly closed field of characteristic zero (because you seem to be working $\mathbb{C}$). This will also work over $\mathbb{R}$ for self-adjoint matrix.
All the zeros of a polynomial $P$ have multiplicity greater than one if and only if $P$ divide $(P')^2$.
So you can take $P$ to be the characteristic polynomial of your matrix and compute $(P')^2$ in $K[X]/(P)$.
I don't says it is algorithmically more efficient than the previous answer, but it has the advantage of producing for each $n$ a family of $n$ algebraic equations on the coefficient which says if your $2n \times 2n$ matrix satisfy the condition or not...
