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