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).

Deja Bradshaw

Deja Bradshaw

Answered question

2022-10-22

Exact SVD algorithm of matrix with symbolic entries
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 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?

Answer & Explanation

wespee0

wespee0

Beginner2022-10-23Added 15 answers

Step 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:
A x = λ x
This problem is equivalent to:
d e t ( A λ I ) = 0
which is a polynomial equation of nth degree in λ 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).
Step 2
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

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?