# 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

## 1 Answer

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.

There is no difficulty in computing ranks over matrices over finite fields anyway.

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