One method is to reduce the computation to that of computing matrix multiplication of $n \times n$ matrices. In particular, the determinant of a symbolic matrix can be computed in $O(n^{\omega})$ arithmetic operations, where $\omega < 2.376$ is the matrix multiplication exponent, and from a symbolic determinant of course one can recover all eigenvalues. However, since the operations here will be over polynomials of degree $n$ with coefficients in $m$ bits, this method would take about $O(n^{1+\omega} m)$ time to get $m$ bits of the eigenvalues.

More complex methods can get you the eigenvalues in $O(n^3 + n^2 \log^2 n \log b)$ time, where the eigenvalues are approximated to within $2^{-b}$. For some structured matrices you can get about $O(n^{\omega})$. See

>	Victor Y. Pan, Zhao Q. Chen: The Complexity of the Matrix Eigenproblem. STOC 1999: 507-516

(Actually it appears this paper never appeared in a journal form, so study it very carefully if you are serious about this problem.)

I don't (yet) see a simple way to exploit the fact that (a) it is symmetric and (b) you just want to find a single nonzero eigenvalue.