Exact SVD algorithm of matrix with symbolic entries

Question

I am making a library with symbolic computations which supports matrices. A matrix may have symbolic entries (eg be over the ring of polynomials of a variable $x$ ie $\mathbb{Q}[x]$).

I have implemented almost all useful linear algebra algorithms and decompositions using exact/symbolic computations (and in some cases fraction-free algorithms) (eg REF, RREF, SNF, INVERSE, PSEUDO-INVERSE, LU, QR, RANK factorisations/decompositions, ROWSPACE, COLUMNSPACE, NULLSPACE etc). The only needed algorithm which I cannot do with exact/symbolic computations is SVD/EVD. I only find numerical algorithms which solve the problem numericaly / approximately and employing "irrational" computations (eg square roots) which are not exact (note: I dont mind if an exact/symbolic algorithm employs square roots, since I can handle these symbolicaly if needed without actually computing square roots).

Any exact/symbolic algorithm for SVD/EVD or any way to compute SVD using one of the decompositions I already have and which are exact?

Note: the library supports arbitrary precision arithmetic (although slow).

An online demo of the library (which is implemented in pure JavaScript and works in browser and node.js) is over here

Answer 1

To answer my own question, it seems the answer is:

no exact/symbolic algorithm exists (or is likely to exist) for SVD/EVD

Essentialy the problem is equivalent to the eigenvalue problem:

$$Ax = \lambda x$$

This problem is equivalent to:

$$det(A-\lambda I)=0$$

which is a polynomial equation of $n$th degree in $\lambda$ and according to Abel-Ruffini theorem there is no general exact/closed form solution involving elementary functions and operations (which is what I need in my case, but there is no general closed form solution even if more complex functions are allowed).

Since every monic polynomial can be the characteristic polynomial of a matrix, this means that there is no exact/closed form solution to the eigenvalue problem and no exact/closed form solution to the SVD problem (which can be rephrased as eigenvalue problem) except numerical approximations which unfortunately cannot be used with symbolic entries.