# symbolic diagonalization of a matrix

Hi,

I am looking for algorithms that can perform a diagonalization, in a symbolic way, of a given matrix. I need to find a similarity transformation, if it exists. Desired features of the algorithms are: 1) Not using symbolic software like MATHEMATICA, MAPLE, etc. I need to program the algorithms in C++. 2) Not necessarily general. They may be limited to relatively simple cases, for example the case when eigenvalues of the matrix cannot be expressed analytically may not be covered, or they may be restricted to some simple class of expressions for the elements of the similarity matrix. 3) Described in scientific publications. I need references.

I would appreciate any pointers.

Leslaw

-
This includes as a special case the symbolic expression of the zeros of a polynomial, which you know is problematic for degree ${}\ge 5$. Even if the matrix entries are just integers, there is no algorithm using only basic operations like plus, times, divide, square root that finishes in a finite number of steps. All numerical algorithms are iterations which (hopefully) converge towards a solution, so you can't expect more than that symbolically unless you are willing to express the answer in terms of symbolic eigenvalues. –  Brendan McKay Dec 16 '11 at 12:06
Mathematica and Maple sidestep the problem of "symbolic expression" of roots by using a data structure containing the minimal integer-coefficient polynomial that corresponds to those roots, and an index. For actual general expressions for roots of polynomials with degree $\geq 5$, you need theta functions. Which is a pretty deep rabbit hole... –  J. M. Dec 16 '11 at 12:31
In addition, if you assume that polynomial root finding as a black box, you can write a rather short program to compute the diagonalization. –  Igor Rivin Dec 16 '11 at 12:38
In addition to polynomial root finding, you need to be able to decide whether polynomial expressions involving a root and the matrix entries are 0 in order to tell whether the matrix is diagonalizable. –  Robert Israel Dec 16 '11 at 17:53
MATHEMATICA has a built-in function JordanDecompose[] which seems to do exactly what I need. Surely, if we want to find the eigenvalues exactly, there can be problems with characteristic polynomials of orders higher than 4. But, the above function seems not to operate in this way, since it gives exact symbolic answers in cases when the eigenvalues are expressed by simple expressions of the symbols representing matrix elements, even of the characteristic polynomial is of higher order. So, I'd be happy to learn how the JordnDecompose[] operates; what is the algorithm behind it. Any ideas? –  user20434 Jan 8 '12 at 11:24