# Singular value decomposition over finite fields?

What is the definition of a singular value over a finite field $\mathcal{F}$ of a matrix ${\bf A}$ in $\mathcal{F}^{m\times n}$? Is there a geometric intuition in the same manner as with the real case where the eigenvalues are the radii of the ellipse $\frac{\|{\bf A}{\bf x}\|^2}{\|{\bf x}\|^2}$?

-
The entire notion and utility of the SVD depends on the concept of positive definite matrices, which makes little or no sense over an unordered field. –  Harald Hanche-Olsen Nov 28 '09 at 1:05
You can still use an unordered field, you just need that the inner-product maps to non-negative reals. –  user1447 Nov 28 '09 at 1:43
@gmatt: There are no interesting such inner products, because any real-valued bilinear or sesquilinear form on a vector space over a finite field is necessarily identically zero. Proof: multiply either input by the characteristic to get zero, and note that R is uniquely divisible. –  S. Carnahan Nov 28 '09 at 6:09

There is no definition of a singular value of a matrix over a finite field. You could define it to be a non-zero eigenvalue of $A^TA$, but this does not really work as you might expect.
Over the reals, the eigenvalues of $A^TA$ are non-negative and the smallest singular value is a measure of how close $A$ is to being a non-invertible matrix. Further, there are stable algorithms to compute it, whereas we cannot compute the rank of $A$ in a stable fashion.
Over the complex numbers, you would use the eigenvalues of ${\bar A}^TA$ as singular values instead the eigenvalues of $A^TA$. Over finite fields you might use $\sigma(A^T)A$, where $\sigma$ is a field automorphism. This is a problem, we have ore choice than we do over the reals and complexes.
Over finite fields, eigenvalues are of limited use. We can get the characteristic polynomial of a matrix, and factor it; the zeros of the factors are the eigenvalues. These eigenvalues would lie in some extension $E$ of your finite field $F$; if I came along with $E$ and asked which elements of $E$ were the eigenvalues, you would have a lot of work and your final answer would depend on exactly how I described $E$. (Even over the reals, eigenvalues are useful if the matrix is small, or normal, but they are much less use otherwise. Google 'pseudospectra')