Does the singular value decomposition (SVD) require a complete field? SVD clearly can't work on $\mathbb Q$, since we need square roots. But can it work on $\mathbb E$, the smallest Euclidean field containing $\mathbb Q$?
I ask because, to my surprise, my synthetic geometry proof of polar decomposition required completeness, and would not, as far as I can tell, work for $\mathbb E$. (This is startling, because, it is generally accepted, as Dedekind himself wrote when introducing his cuts, that Euclidean geometry does not require, and would not be changed, by completeness, as long as it includes all constructible numbers.)
Additionally, when proving SVD, Trefethen & Bau make use of compactness to show the existence of a maximum, which of course requires a complete field.
And, from Harvard's fabled 55a, another use of completeness:
Compactness… gives us another way to prove the spectral theorem: we can find an eigenvector for $T$ by seeing where the function $w \mapsto \langle Tw,w \rangle$ achieves its maximum on the unit sphere.
Thus, can the SVD be done in a field that admits square roots but is not complete? And, if yes: What aspect of complete fields finds its way into all three of these proofs? Is SVD somehow different or "stronger" in complete fields?
Best Answer
Every matrix over a Euclidean field $K$ has a SVD over $K$ iff every symmetric matrix over $K$ has all its eigenvalues in $K$. In one direction, the usual proof of existence of SVDs from the spectral theorem (e.g., here) uses only the existence of square roots and the spectral theorem for symmetric matrices. Conversely, if $A$ is a symmetric matrix over $K$, the existence of a SVD for $A$ gives a diagonalization of $A^*A=A^2$, which can be square-rooted to get a diagonalization of $A$ since $K$ is Euclidean.
In particular, this is not true of the constructible numbers $\mathbb{E}$ (for instance, the symmetric matrix $\begin{pmatrix} 0&1&1 \\ 1&0&0 \\ 1&0&1\end{pmatrix}$ has irreducible characteristic polynomial over $\mathbb{Q}$ so its eigenvalues are not constructible). So, the existence of SVDs requires some amount of "completeness" beyond just the existence of square roots. It requires much less than completeness in the analytic sense, though; in particular, it only involves having roots of polynomials, so it suffices to have a real closed field. In fact, it is strictly weaker than being real closed. For instance, the smallest such field can be obtained from $\mathbb{Q}$ by alternating taking Euclidean closures and the closure under taking eigenvalues of symmetric matrices infinitely many times. If $f$ is an irreducible cubic over $\mathbb{Q}$ with exactly one real root, then $f$ will remain irreducible in each stage of this process: taking Euclidean closures only gives extensions of degree a power of $2$ so cannot add a root of $f$, and taking eigenvalues of symmetric matrices only adjoins roots to polynomials whose roots are all real (see this answer). So the smallest Euclidean field over which SVDs exist does not contain the real root of $f$, and so is not real closed.
(If you work over an ordered field that is not necessarily Euclidean, I don't know whether the existence of SVDs is equivalent to the existence of eigenvalues of symmetric matrices. The argument above only gives eigenvalues of symmetric matrices of the form $A^*A$ in one direction, and in the other direction it seems to require not just eigenvalues of symmetric matrices of the form $A^*A$ but the square roots of these eigenvalues.)