2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I think there might be a typo in the expression for $p(x)$, the last three of the four terms seem to have the same degree, namely $n/2$. Also $H_i(x)$ is a re-scaled Chebyshev polynomial, so its zeros are simple. $\endgroup$ Jan 20, 2012 at 0:17
  • $\begingroup$ I can't see any problem with the expression $p(x)$. Yes, the last three terms have the same degree $k-1$. And yes, $H_{k-1}$ and $H_{k-1}\pm2$ have all simple roots. $\endgroup$ Jan 20, 2012 at 0:34

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks Chris. Unfortunately, the graph class I am interested in is not walk-regular. What other interesting properties may help with the computation of an eigenvalue multiplicity? $\endgroup$ Jan 19, 2012 at 4:43
  • $\begingroup$ Actually the method works for all graphs, but requires eigenvector computations which will not be convenient for your application. $\endgroup$ Jan 19, 2012 at 13:16
  • $\begingroup$ Guillermo: Do you have the actual eigenvalue(s)? What sort of graphs are dealing with. $\endgroup$ Jan 19, 2012 at 13:57
  • $\begingroup$ What properties do you have? It might be easy to work with a bipartite graph where the number of walks between two vertices dependent only on their distance and which half they are in (for even distance). Have an automorphism group (especially a large one) with with few orbits could help as well. Various products of nice graphs might be tractable. $\endgroup$ Jan 19, 2012 at 17:27
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.