Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $A$ be the adjacency matrix of a strongly regular graph. When is it possible to sign $A$ (i.e. replace some of the +1 entries by -1) so that the resulting matrix has exactly two eigenvalues?

I know of one interesting case where this is possible. Namely, define a graph $G$ where $V(G)$ is the set of 120 lines in ${\mathbb R}^8$ given by the $E_8$ root system, and two vertices are adjacent if these lines make an angle of $\pi/3$. This graph is strongly regular with parameters $(120, 56, 28, 24)$. To sign it, choose one vector in $E_8$ from each of these lines, and let $B$ be the associated Gram matrix. Then $C = B - 2I$ is a signing of the adjacency matrix of $G$ with just two eigenvalues ($-2$ and $28$).

share|improve this question

2 Answers 2

Suppose we have a set of unit vectors $x_1,\ldots,x_m$ in $\mathbb{R}^d$ such that (for $i=j$) either $x_i^Tx_j=0$ or $|x_i^Tx_j|=a$. The Gram matrix of these vectors can be written as $I+aS$, where $S$ is symmetric, has zero diagonal, and entries in $\{0,\pm\}$. So we have a signed graph. (Hi Tom.) Replacing $x_i$ by $-x_i$ for some $i$'s does not change anything of interest, we're really dealing with sets of lines.

By results of Delsarte, Goethals and Seidel "Spherical Codes and designs" we know that $m\le \binom{n+2}3$. They mention two examples where this bound is tight: $d=8$ as in your question and 2300 lines when $d=23$. It's likely that these are the only known examples where the bound is tight. I think DGS supply enough theory to show that the underlying graph will be strongly regular in this case.

DGS also derive a bound $$ m \le \frac{d(d+2)(1-a^2)}{3-(d+2)a^2}. $$ I'd expect that sets of lines meeting these bounds will give strongly regular graphs (but I could not see exactly what I needed in a quick skim and my coffee break is coming to an end).

Forgive me if you knew all this and were really fishing for more examples.

Edit: Let $H$ be an $n\times n$ Hadamard matrix and let $A$ be given by $$ A =\begin{pmatrix}0&H^T\\\ H&0\end{pmatrix} $$ Then $A^2=nI$ and $A$ is a signing of the complete bipartite graph. These examples may appear a bit trivial, but there are a lot of them. More generally any antipodal distance-regular graph with diameter four (and antipodal fibres of size two) will give rise to examples. Unfortunately this will only produce three further examples, and the margin is too small to deal with these.

Edit2: The fact equality in the given bound implies that the graph on the lines is strongly regular appears as (part of) Proposition 3.12 in the paper by Calderbank, Cameron, Kantor and Seidel on Kerdock codes over $\mathbb{Z}_4$. They also prove that equality in the bound imples that the signed adjacency matrix has exactly to eigenvalues.

share|improve this answer
    
I am aware of the construction using lines which are all either pairwise orthogonal or at a given angle. If you have n lines spanning a d dimensional space with n > d, then the resulting matrix you construct will have smallest eigenvalue of multiplicity n-d. However, I don't understand anything about the interaction between the geometry of these lines and the behaviour of any other eigenvalues. I didn't have any secret agenda here, but I am certainly delighted to learn of this result from Delsarte Goethals and Seidel, and of another magic configuration. Thanks!! –  mdevos Mar 20 '13 at 4:38

Here are a few ideas on places to look for examples. You may not find (m)any this way.

First to eliminate a trivial case: For some people a complete graph or disjoint union of isomorphic complete graphs is a SRG. These only have two eigenvalues even without making any changes.

A SRG need not have any automorphisms but many do. This allows an easier complete search of very small cases. In a very modest search I found one legit example and a few questionable ones. Then it seems reasonable to look for ways to sign the matrix and preserve a large subgroup of the automorphism group (but I did not get anything from that.)

Essentially we are taking a graph with $e$ edges, viewing it as having $2e$ directed edges, and then giving some of them a weight of $-1$.

A 4-cycle has 4 edges or $8$ directed edges (aka $+1$ entries of the Adjacency matrix $A$)

  • Changing a single $1$ to $-1$ does not work.
  • There are $28$ ways to choose two entries, but only $6$ up to action of the Dihedral group. Changing two entries , both from the same edge, gives eigenvalues $\pm\sqrt{2}$ twice each. (That is my sole good example so enjoy it). There are also three ways to change two entries to $-1$ and get all eigenvalues $0$: the two edges leaving a vertex, the two going into a vertex, and two parallel directed edges.
  • there are no successful ways to change three entries.
  • There are $\binom84=70$ ways to choose $4$ entries to change but only $13$ up to isomorphism (maybe less but at worst I looked at some cases twice.) Four of them give all eigenvalues $0.$

Note that with two eigenvalues $\theta_1,\theta_2$ taken $k$ and $n-k$ times we need $\frac{\theta_1}{\theta2}=-\frac{n-k}{k}$ unless it is actually a single eigenvalue of $0$.

  • A pentagon amounts to $10$ directed edges, There is no way to change some of the entries of $A$ to $-1$ and get only two eigenvalues. There are $\binom{10}{5}=252$ ways to change $5$ of them but only $26$ up to isomorphism.

  • The complete bipartite graph has $18$ directed edges. Nothing works there. There would be $\binom{18}{9}=24310$ ways to change half the edges but only $681$ up to isomorphism.

I'd hoped to find an example which generalized. I did not give up after two tries but did after three. Maybe someone else will find something by looking a bit harder. Perhaps $K_{2,2,2}$ , $K_{4,4}$, or some other small case.

I also looked, without results at a few ways to weight the $2 \cdot 15=30$ directed edges from a Peterson Graph.

  • The obvious order $5$ rotation gives $3$ pairs of $5$ edge orbits so $64$ (or $32$ or $16$ depending how hard you wish to think) ways to sign some orbits $-1$. None worked ( assuming I programmed correctly).
  • Fixing a point gives orbits of sizes $3,3,6,6$ and $12$ (Probably the $12$ could be split $6,6$ but I did not try that variation. ) That does not yield anything.
  • I did not look at fixing a pair of vertices (setwise). This would give orbits of sizes $1,1,4,4,8,8,2?,2?.$

A similar attempt could be made for other graphs.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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