Computing the multiplicity of an eigenvalue of a 0-1 symmetric matrix... When we want to compute the multiplicity of an eigenvalue of a 0-1 symmetric matrix (viewed as the adjacency matrix of an undirected regular graph), we commonly resort to the know lemma of Feit and Higman which states the following:
Let $\theta$ be a simple root of the polynomial $p(x)$, and set $p_{\theta}=p(x)/(x-\theta)$. If $M$ is a matrix satisfying $p(M)=0$, then the multiplicity of $\theta$ as an eigenvalue of $M$ is given by $\frac{tr(p_\theta(M))}{p_\theta(\theta)}$, where $tr$ gives the trace.
The complication with this approach is the computation of the traces, especially when the degree of $p(x)$ is much higher than the girth of the corresponding graph. 
If the graph is distance-regular then an alternative (and simpler) approach could be used.
My question is the following:
Is there any other way to compute the multiplicity of an eigenvalue for such a matrix if we know the girth, diameter and degree of the corresponding graph (and possibly other properties)? 
[EDIT:] I think it is best if I now give a bit more information of what I actually have.
My hypothetical graph is bipartite of degree $d$, diameter $k$ and girth $g=2k-2$. Furthermore, every vertex is contained in exactly two $(2k-2)$-cycles, and its eigenvalues satisfy the following polynomial equations:
$n/4-1$ eigenvalues coming from $H_{k-1}(x)-2$,
$n/4-1$ eigenvalues coming from $H_{k-1}(x)+2$, and
$n/2$ eigenvalues coming from $H_{k-1}(x)$, where 
$H_{0}(x)=1$, $H_{1}(x)=x$ and $H_i(x)=xH_{i-1}(x)-(d-1)H_{i-2}(x)$ for $i\ge 2$.
Thus, the polynomial $p(x)=(x^2-d^2)H_{k-1}(x)(H_{k-1}(x)-2)(H_{k-1}(x)+2)$ is a multiple of the minimal polynomial of the graph. 
Feit and Higman's method would have been fine if the degree of $p(x)$ were close to the girth of the graph as the trace computation would then be manageable.  
I would appreciate any help I could get in this regard...
Thanks in advance, and regards,
Guillermo 
 A: I suspect there are few short cuts in general and that computing multiplicities for 01-matrices
will not be easier than computing them for real symmetric matrices.  The approach usually used for distance-regular graphs extends to walk-regular graphs. This described in a paper by me and Brendan McKay "Feasibility conditions for the existence of walk-regular graphs" which appeared in LAA (1980). (There may be a copy on Brendan's web page.) Brendan used this to compute eigenvalue multiplicities for smallish vertex-transitive graphs.
If the classes of graphs you are interested in usually have eigenvalues with multiplicities
greater than  one, then I expect they would have other interesting properties, which could possibly help.
A: The multiplicity of $\lambda$ is $n$ minus the rank of $\lambda I - A$, which you can find using Gaussian elimination.  If you need to use floating-point arithmetic, you'll need to make decisions on when tiny numbers are actually zero, which is a pain. I'm not sure of the best way with exact arithmetic.
