Won’t that be equivalent to solving the characteristic polynomials and so it won’t be possible for n>5 by Abel’s Theorem to do symbolically? I haven’t thought about it too much but @YingboMa might have an idea.

See symbolic diagonalization of a matrix - MathOverflow for a discussion of the general case. Maybe something more specific can be said about normal matrices. With symbolic matrices, I guess one needs to add some constraints on the terms in order to guarantee that they are normal.

Agree, but even for n<5 that diagonalization can prove to be useful. On the other hand, there are some special matrices which can be solved also exactly, I guess one needs to keep a little database of those guys somewhere.