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

Improve this question
$\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$
    – Chris Godsil
    Commented 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$
    – Guillermo Pineda-Villavicencio
    Commented Jan 20, 2012 at 0:34

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Guillermo Pineda-Villavicencio
    Commented 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$
    – Brendan McKay
    Commented Jan 19, 2012 at 13:16
  • $\begingroup$ Guillermo: Do you have the actual eigenvalue(s)? What sort of graphs are dealing with. $\endgroup$
    – Chris Godsil
    Commented 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$
    – Aaron Meyerowitz
    Commented 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .