2 added 31 characters in body

Here is a simple idea, with no complexity analysis. Compute a basis $v_1$, ..., $v_{n-r}$ for the kernel of $A$; this can be done with exact arithmetic in $n^3$ operations by Gaussian elimination. Compute a basis $w_1$, ..., $w_{r}$ for the othogonal complement: Again, doable in exact arithmetic with $n^3$ operations. $\mathrm{Span}(w_1, ..., w_r)$ is the orthogonal complement to the $0$-eigenspace of $A$ and hence, since $A$ is symmetric, it is the span of the nonzero eigenspaces of $A$. So $A$ maps $\mathrm{Span}(w_1, \ldots, w_r)$ to itself. Let $X$ be the $r \times r$ matrix of this map. This is again a matrix of rational numbers, computable with exact arithmetic in reasonable time, whose eigenvalues are the same as the nonzero eigenvalues of $A$. Note, however, that $X$ is not symmetric.

Invert $X$ and find its largest eigenvalue by one of the standard methods.

What I am gambling here is that the advantages of working in exact arithmetic are greater than the disadvantages of passing to a nonsymmetric matrix.

1

Here is a simple idea, with no complexity analysis. Compute a basis $v_1$, ..., $v_{n-r}$ for the kernel of $A$; this can be done with exact arithmetic in $n^3$ operations by Gaussian elimination. Compute a basis $w_1$, ..., $w_{r}$ for the othogonal complement: Again, doable in exact arithmetic with $n^3$ operations. $\mathrm{Span}(w_1, ..., w_r)$ is the orthogonal complement to the $0$-eigenspace of $A$ and hence, since $A$ is symmetric, it is the span of the nonzero eigenspaces of $A$. So $A$ maps $\mathrm{Span}(w_1, \ldots, w_r)$ to itself. Let $X$ be the $r \times r$ matrix of this map. This is again a matrix of rational numbers, computable with exact arithmetic in reasonable time, whose eigenvalues are the same as the nonzero eigenvalues of $A$. Note, however, that $X$ is not symmetric.

Invert $X$ and find its largest eigenvalue.

What I am gambling here is that the advantages of working in exact arithmetic are greater than the disadvantages of passing to a nonsymmetric matrix.