7
$\begingroup$

I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs.

Conversion from a Hadamard Matrix into a Hadamard Graph

An $n$-Hadamard graph $G$ is a graph on $4n$ vertices defined in terms of a Hadamard matrix of order $n$ $H_n = h_{ij}$ as follows:

  1. Define $4n$ symbols $r_i^+$, $r_i^-$, $c_i^+$, and $c_i^-$, where $r$ stands for row and $c$ stands for column and take these as the vertices of the graph.
  2. Then add two types of edges between row vertices and column vertices based on the sign of $h_{ij}$: \begin{equation*} \text{parallel edges $(r_i^+, c_j^+)$ and $(r_i^-, c_j^-)$ if $h_{ij} = +1$} \\ \text{crossing edges $(r_i^+, c_j^-)$ and $(r_i^-, c_j^+)$ if $h_{ij} = -1$} \end{equation*}

Then the graph $G$ will be a bipartite graph where the set of vertices is partitioned into row vertex set of $2n$ vertices and column vertex set of $2n$ vertices. And there will be $2n^2$ edges.

Equivalence between Graph and Matrix

In theorem 1.8.1 in their book, they showed that $G$ is a distance-regular graph with an intersection array $\{n,n-1,\frac{n}{2},1;1,\frac{n}{2},n-1,n\}$ if and only if the matrix $H$ is Hadamard matrix of order $n$.

My Question

Their proof of this theorem seems rather brief and I have hard time in understanding the equivalence. Especially, I don't understand what role two orthogonal rows or columns in the matrix $H_n$ play in the graph $G$ so that distance-regularity is achieved. The book cited three papers for the proof, but I cannot find any of them in the Internet.

Can anyone explain what's the idea or intuition behind the proof of equivalence?

$\endgroup$

1 Answer 1

7
$\begingroup$

First, the book by Brouwer, Cohen and Neumaier is known for a degree of terseness; any one who uses it will have struggled with it at some point.

You describe a construction that, from an $n\times n$ Hadamard matrix, produces a bipartite graph on $4n$ vertices that is regular of degree $n$. This graph has diameter four; moreover for each vertex $u$ there is a unique vertex $u'$ at distance four from $u$. It follows that the the $4n$ vertices may be partitioned into $2n$ pairs.

So the way to proceed is to prove that these comments about pairs of vertices at distance four are correct and then, using this, prove that the parameters $b_i$ and $c_i$ are well-defined. This reduces to showing that if $v$ is at distance two from a vertex $u$, then $v$ has exactly $n/2$ neighbours in common with $u$. (This is where the orthogonality of the rows of $H$ enters.)

$\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.