In the theory of (algebraic) combinatorics association schemes play an important role. Association schemes may be seen as colorings of the edges of the complete graph satisfying nice regularity conditions, and they are used in coding theory, design theory, graph theory and group theory. Many chapters of books or complete books are devoted to association schemes (see [1-3]).

We start with a brief introduction to association schemes. For (more) basic results on association schemes and their proofs we refer to [1].

Let $V$ be a finite set of vertices. A $d$-class association scheme on $V$ consists of a set of $d+1$ symmetric relations $R_0,R_1,\cdots,R_d$ on $V$, with identity relation $R_0=\{(x,x)|x\in V\},$ such that any two vertices are in precisely one relation. Furthermore, there are intersection numbers $p^k_{ij}$ such that for any $(x,y)\in R_k$, the number of vertices $z$ such that $(x,z)\in R_i$ and $(z,y)\in R_j$ equals $p^k_{ij}$.

The nontrivial relations can be considered as graphs, which in our case are undirected. One immediately sees that the respective graphs are regular with degree $n_i=p_{ii}^0$. For the corresponding adjacency matrices $A_i$ the axioms of the scheme are equivalent to

$\sum\limits_{i=0}^dA_i=J,\ A_0=I,\ A_i=A_i^T,\ A_iA_j=\sum\limits_{k=0}^dp_{ij}^kA_k.$

It follows that the adjacency matrices generate a $d+1$-dimensional commutative algebra $\mathfrak{A}$ of symmetric matrices. This algebra was first studied by Bose and Mesner (see [5]) and is called the Bose-Mesner algebra of the scheme. The corresponding algebra of a coherent configuration is called a coherent algebra, or by some authors a cellular algebra or cellular ring (with identity) (see [6]).

Kaishun Wang, Jun Guo, Fenggao Li (see [7]) constructed association schemes by attenuated spaces. Their construction stimulates us to consider the construction of association schemes by dihedral group.

In this paper, we provide a new family of symmetric association schemes, and obtain the following results:

Theorem 1.1  For $n=2m$, suppose that $D_{2n}=\{1,a,a^2,\cdots,a^{n-1},b,ba,ba^2,\cdots,ba^{n-1}\}$ be a dihedral group. Let us define

(1) $R_0=\{(x,x)|x\in D_{2n}\};$

(2) $R_i=\{(a^l,a^{2m+l-i})|l=0,1,\cdots,2m-1 \}\cup\{(a^l,a^{l+i})|l=0,1,\cdots,2m-1 \}$ $\cup\{(ba^l,ba^{2m+l-i})|l=0,1,\cdots,2m-1 \}\cup\{(ba^l,ba^{l+i})|l=0,1,\cdots,2m-1 \},$ where $i=1,2,\cdots,m-1;$

(3) $R_{m}=\{(a^l,a^{m+l})|l=0,1,\cdots,2m-1\}\cup\{(ba^l,ba^{m+l})|l=0,1,\cdots,2m-1\};$

(4) $R_{m+1}=\{(a^l,ba^{l+2j})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}\cup\{(ba^l,a^{2m+l-2j})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\};$

(5) $R_{m+2}=\{(a^l,ba^{l+2j+1})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}\cup\{(ba^l,a^{2m+l-2j-1})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}.$

Then we obtain a family of symmetric association scheme $\chi=(D_{2n},\{R_i\}_{0\leq i\leq m+2})$ with parameters

$d=m+2;v=2n;n_i=\left\{\begin{array}{ll} 1,&i=0,\ {\rm or}\ i=m,\\ 2,&1\leq i\leq m-1,\\ 0,&i=m+1\ {\rm or}\ i=m+2, \end{array}\right.$

intersection numbers $p_{ij}^k$ given by (1).

In this section we give some lemmas, which are needed in the proof of Theorem 1.1.

We assume that $D_{2n}=\{1,a,a^2,\cdots,a^{n-1},b,ba,ba^2,\cdots,ba^{n-1}\}$ is a dihedral group. It is know that $a^jb=ba^{-j}$ and $(ba^j)^{-1}=ba^j.$ Here $j\in \{0,1,\cdots,n-1\}.$

Lemma 2.1  For $n=2m,$ the conjugacy classes of the dihedral group $D_{2n}$ are the following.

$C_0=\{1\};\ C_i=\{a^i,a^{2m-i}\},i=1,2,\cdots,m-1;\ C_{m}=\{a^m\} $

and

$ C_{m+1}=\{b,ba^2,\cdots,ba^{2m-2}\};\ C_{m+2}=\{ba,ba^3,\cdots,ba^{2m-1}\}.$

Proof For any $a^j\in D_{2n}$ and $ba^j\in D_{2n},j=0,1,\cdots,2m-1$, pick $a^i\in D_{2n},i=1,2,\cdots,m-1$. We have $a^ja^i(a^j)^{-1}=a^{j+i-j}=a^i$ and $(ba^j)a^i(ba^j)^{-1}=ba^{j+i}ba^j=a^{-i}=a^{2m-i}.$ Therefore the conjugacy class containing $a^i$ is

$C_{i}=\{a^i,a^{2m-i}\},i=1,2,\cdots,m-1.$

Picking $a^m\in D_{2n}$, we have $a^ja^m(a^j)^{-1}=a^{j+m-j}=a^m$ and $(ba^j)a^m(ba^j)^{-1}=ba^{j+m}ba^j=a^{-m}=a^{m}.$ Therefore the conjugacy class containing $a^m$ is

$C_{m}=\{a^m\}.$

Picking $b\in D_{2n}$, we have $a^jb(a^j)^{-1}=ba^{-2j}$ and $(ba^j)b(ba^j)^{-1}=ba^{2j}.$ Therefore the conjugacy class containing $b$ is

$C_{m+1}=\{b,ba^2,\cdots,ba^{2m-2}\}.$

Picking $ba\in D_{2n}$, we have $a^jba(a^j)^{-1}=ba^{-2j+1}$ and $(ba^j)ba(ba^j)^{-1}=ba^{2j-1}.$ Therefore the conjugacy class containing $ba$ is

$C_{m+2}=\{ba,ba^3,\cdots,ba^{2m-1}\}.$

Let $C_0=\{1\}.$ Since

$\bigcup_{i=0}^{m+2}C_i=D_{2n},$

the lemma holds.

Let $C_0,C_1,\cdots,C_{m+2}$ be the set of all the conjugacy classes of the group $D_{2n}$ as Lemma2.1. We define $X=D_{2n}$ and $(x,y)\in R_i\Longleftrightarrow yx^{-1}\in C_i.$ Then $(X,\{R_i\}_{0\leq i\leq m+2})$ becomes an association scheme.

Lemma 2.2  For $n=2m,$ let $D_{2n}$ be a dihedral group. Suppose that $(x,y)\in R_i\Longleftrightarrow yx^{-1}\in C_i,i=0,1,\cdots,m+2.$ Then

(1) $R_0=\{(x,x)|x\in D_{2n}\}.$

(2) $R_i=\{(a^l,a^{2m+l-i})|l=0,1,\cdots,2m-1 \}\cup\{(a^l,a^{l+i})|l=0,1,\cdots,2m-1 \}\\ \cup\{(ba^l,ba^{2m+l-i})|l=0,1,\cdots,2m-1 \}\cup\{(ba^l,ba^{l+i})|l=0,1,\cdots,2m-1 \},$ where $i=1,2,\cdots,m-1.$

(3) $R_{m}=\{(a^l,a^{m+l})|l=0,1,\cdots,2m-1\}\cup\{(ba^l,ba^{m+l})|l=0,1,\cdots,2m-1\}.$

(4) $R_{m+1}=\{(a^l,ba^{l+2j})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}\cup\{(ba^l,a^{2m+l-2j})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}.$

(5) $R_{m+2}=\{(a^l,ba^{l+2j+1})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}\cup\{(ba^l,a^{2m+l-2j-1})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}.$

Proof Let $b^ka^l\in D_{2n}.$ If $b^ka^lx^{-1}\in C_i,i=1,\cdots,m-1$, then $b^ka^lx^{-1}=a^i$ or $b^ka^lx^{-1}=a^{2m-i}$. Therefore

$x=a^{2m-i}b^ka^l=b^ka^{(-1)^k(2m-i)+l}=\left\{ \begin{array}{ll} a^{2m+l-i},&\hbox{if}\ k=0,\\ ba^{l+i},&\hbox{if} \ k=1, \end{array} \right. $

or

$x=(a^{2m-i})^{-1}b^ka^l=b^ka^{(-1)^ki+l}=\left\{ \begin{array}{ll} a^{l+i},&\hbox{if}\ k=0,\\ ba^{2m+l-i},&\hbox{if} \ k=1. \end{array} \right. $

Hence

$\begin{array}{ll} R_i=&\{(a^l,a^{2m+l-i})|l=0,1,\cdots,2m-1 \}\cup\{(a^l,a^{l+i})|l=0,1,\cdots,2m-1 \}\\ &\cup\{(ba^l,ba^{2m+l-i})|l=0,1,\cdots,2m-1 \}\cup\{(ba^l,ba^{l+i})|l=0,1,\cdots,2m-1 \}, \end{array}$

where $i=1,2,\cdots,m-1.$

If $b^ka^lx^{-1}\in C_{m}$, then $b^ka^lx^{-1}=a^m.$ Therefore

$x=(a^m)^{-1}b^ka^l=a^mb^ka^l=\left\{ \begin{array}{ll} a^{m+l},&\hbox{if}\ k=0\\ ba^{l-m},&\hbox{if}\ k=1 \end{array} \right. =\left\{ \begin{array}{ll} a^{m+l},&\hbox{if}\ k=0,\\ ba^{m+l},&\hbox{if}\ k=1. \end{array} \right. $

Hence

$R_{m}=\{(a^l,a^{m+l})|l=0,1,\cdots,2m-1\}\cup\{(ba^l,ba^{m+l})|l=0,1,\cdots,2m-1\}.$

If $b^ka^lx^{-1}\in C_{m+1}$, then $b^ka^lx^{-1}=ba^{2j},j=0,1,\cdots,m-1.$ Therefore

$x=(ba^{2j})^{-1}b^ka^l=b^{k+1}a^{(-1)^k2j+l}=\left\{ \begin{array}{ll} ba^{l+2j},&\hbox{if}\ k=0,\\ a^{2m+l-2j},&\hbox{if}\ k=1. \end{array} \right. $

Hence

$\begin{array}{ll} R_{m+1}=&\{(a^l,ba^{l+2j})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}\\ &\cup\{(ba^l,a^{2m+l-2j})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}. \end{array}$

If $b^ka^lx^{-1}\in C_{m+2}$, then $b^ka^lx^{-1}=ba^{2j+1},j=0,1,\cdots,m-1.$ Therefore

$x=(ba^{2j+1})^{-1}b^ka^l=b^{k+1}a^{(-1)^k(2j+1)+l}=\left\{ \begin{array}{ll} ba^{l+2j+1},&\hbox{if}\ k=0,\\ a^{2m+l-2j-1},&\hbox{if}\ k=1. \end{array} \right. $

Hence

$\begin{array}{ll} R_{m+2}=&\{(a^l,ba^{l+2j+1})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}\\ &\cup\{(ba^l,a^{2m+l-2j-1})|l=0,1,\cdots,2m-1,j=0,1,\cdots,m-1\}. \end{array}$

In this section we shall prove Theorem1.1 and compute all the parameters of the corresponding association scheme.

By Lemma 2.2, for $n=2m$, we have that $\chi=(D_{2n},\{R_i\}_{0\leq i\leq m+2})$ is an association scheme, and obtain the following propositions.

Proposition 3.1  Suppose that $n=2m$. Then the set of the adjacency matrices of the association scheme $\chi$ is given by the following matrices.

(1) $A_0=I$;

(2) $A_i=\left[\begin{array}{cc} S^{n-i}+S^i&0\\ 0&S^{n-i}+S^i \end{array} \right],i=1,\cdots,m-1;$

(3) $A_{m}=\left[\begin{array}{cc} S^m&0\\ 0&S^m \end{array} \right];$

(4) $A_{m+1}=\left[\begin{array}{cc} 0&\sum\limits_{i=0}^{m-1}S^{2i}\\ \sum\limits_{i=0}^{m-1}S^{2i}&0 \end{array} \right];$

(5) $A_{m+2}=\left[\begin{array}{cc} 0&\sum\limits_{i=0}^{m-1}S^{2i+1}\\ \sum\limits_{i=0}^{m-1}S^{2i+1}&0 \end{array} \right].$ Here $S=\left[\begin{array}{cc} 0&I_{n-1}\\ 1&0 \end{array} \right]$.

Proposition 3.2  Suppose that $n=2m$. Then the intersection numbers of the association scheme $\chi$ are as following.

$\begin{aligned} p_{ij}^k=\left\{\begin{array}{ll} 1,{\rm if}\ \{i,j\}=\{0,l\}\ {\rm and}\ k=l,l=0,1,\cdots,m+2,\\ 1,{\rm if}\ 1\leq i+j\leq m\ {\rm and}\ k=i+j,1\leq i,j\leq m-1,\\ 1,{\rm if}\ m+1\leq i+j\leq 2m-1\ {\rm and}\ k=n-(i+j),1\leq i,j\leq m-1,\\ 1,{\rm if}\ i\neq j\ {\rm and}\ k=|i-j|,1\leq i,j,k\leq m-1,\\ 2,{\rm if}\ 1\leq i=j\leq m-1\ {\rm and}\ k=0,\\ 1,{\rm if}\ \{i,j\}=\{m,l\}\ {\rm and}\ k=m-l,l=1,2,\cdots,m-1,\\ 2,{\rm if}\ \{i,j\}=\{m+1,l\}\ {\rm and}\ k=m+1,l=2,4,\cdots,2m-2,\\ 2,{\rm if}\ \{i,j\}=\{m+1,l\}\ {\rm and}\ k=m+2,l=1,3,\cdots,2m-1,\\ 2,{\rm if}\ \{i,j\}=\{m+2,l\}\ {\rm and}\ k=m+2,l=2,4,\cdots,2m-2,\\ 2,{\rm if}\ \{i,j\}=\{m+2,l\}\ {\rm and}\ k=m+1,l=1,3,\cdots,2m-1,\\ 1,{\rm if}\ \{i,j\}=\{m,m+1\}\ {\rm and}\ k=m+1,m\ \mbox{is even},\\ 1,{\rm if}\ \{i,j\}=\{m,m+1\}\ {\rm and}\ k=m+2,m\ \mbox{is odd},\\ 1,{\rm if}\ \{i,j\}=\{m,m+2\}\ {\rm and}\ k=m+2,m\ \mbox{is even},\\ 1,{\rm if}\ \{i,j\}=\{m,m+2\}\ {\rm and}\ k=m+1,m\ \mbox{is odd},\\ m,{\rm if}\ \{i,j\}=\{m+1,m+2\}\ {\rm and}\ k=m+2,\\ 1,{\rm if}\ i=j=m\ {\rm and}\ k=0,\\ m,{\rm if}\ i=j=k=m+1,\\ m,{\rm if}\ i=j=m+2,k=m+1,\\ 0,{\rm otherwise}.\\ \end{array} \right. \end{aligned}$

(1)

Proof By Proposition3.1, we obtain the results as following. If $0\leq i\leq m+2$, we have

$A_0A_i=A_iA_0=A_i.$

If $1\leq i,j\leq m-1$, we have

$\begin{array}{ll} &A_iA_j=A_jA_i\\ =&\left[\begin{array}{cc} S^{n-(i+j)}+S^{n+j-i}+S^{n+i-j}+S^{i+j}&0\\ 0&S^{n-(i+j)}+S^{n+j-i}+S^{n+i-j}+S^{i+j} \end{array} \right]\\ =&\left[\begin{array}{cc} S^{n-(i+j)}+S^{i+j}&0\\ 0&S^{n-(i+j)}+S^{i+j} \end{array} \right]+\left[\begin{array}{cc} S^{n+j-i}+S^{n+i-j}&0\\ 0&S^{n+j-i}+S^{n+i-j} \end{array} \right]\\ =&\left\{\begin{array}{ll} A_{i+j}+A_{i-j},&i>j,\\ A_{i+j}+A_{j-i},&i<j,\\ A_{2i}+2A_0,&i=j.\\ \end{array}\right. \end{array}$

If $1\leq i\leq m-1$, we have

$A_iA_{m+1}=A_{m+1}A_i=\left\{\begin{array}{ll} 2A_{m+1},\mbox{if}\ i\ \mbox{is even}, \\ 2A_{m+2},\mbox{if}\ i\ \mbox{is odd}, \end{array} \right.$

and

$A_iA_{m+2}=A_{m+2}A_i=\left\{\begin{array}{ll} 2A_{m+2},\mbox{if}\ i\ \mbox{is even}, \\ 2A_{m+1},\mbox{if}\ i\ \mbox{is odd}. \end{array} \right.$

Note that

$A_mA_{m+1}=A_{m+1}A_m=\left\{\begin{array}{ll} A_{m+1},\mbox{if}\ m\ \mbox{is even}, \\ A_{m+2},\mbox{if}\ m\ \mbox{is odd}, \end{array} \right.$

$A_mA_{m+2}=A_{m+2}A_m=\left\{\begin{array}{ll} A_{m+2},\mbox{if}\ m\ \mbox{is even}, \\ A_{m+1},\mbox{if}\ m\ \mbox{is odd}. \end{array} \right.$

$A_m^2=A_0,$

$A_{m+1}A_{m+2}=A_{m+2}A_{m+1}=\left[\begin{array}{cc} 0&m\sum\limits_{i=0}^{m-1}S^{2i+1} \\ m\sum\limits_{i=0}^{m-1}S^{2i+1}&0 \end{array} \right]=mA_{m+2},$

and

$A_{m+1}^2=A_{m+2}^2=\left[\begin{array}{cc} 0&m\sum\limits_{i=0}^{m-1}S^{2i}\\ m\sum\limits_{i=0}^{m-1}S^{2i}&0 \end{array} \right]=mA_{m+1}.$

Therefore the desired result follows.

The proof of Theorem1.1 is completed.

Bannai and Ito (see [1]) introduced strongly regular graphs. In this section we construct a family of strongly regular graphs from above association schemes $\chi=(D_{2n},\{R_i\}_{0\leq i\leq m+2})$. A simple graph $(X,R)$ is called a strongly regular graph with parameters $(n,k,\lambda,\mu)$ if the following conditions are satisfied:

(a) $|X|=n$;

(b) For each $x\in X$, we have $|\{y\in X|(x,y)\in R\}|=k$;

(c) For each pair of $x,y$ with $(x,y)\in R$, we have $|\{z\in X|(x,z)\in R,(y,z)\in R\}|=\lambda;$

(d) For each pair of $x,y$ with $(x,y)\not\in R$, we have $|\{z\in X|(x,z)\in R,(y,z)\in R\}|=\mu.$

Let

$\begin{eqnarray*}&& X=D_{2n},\\ && R=R_1=\{(a^l,a^{2m+l-1})|l=0,1,\cdots,2m-1 \}\cup\{(a^l,a^{l+1})|l=0,1,\cdots,2m-1 \}\\ && \cup\{(ba^l,ba^{2m+l-1})|l=0,1,\cdots,2m-1 \}\cup\{(ba^l,ba^{l+1})|l=0,1,\cdots,2m-1 \}. \end{eqnarray*}$

By Theorem 1.1, we obtain the following theorem.

Theorem 4.1 The graph $\Gamma=(X,R)$ is a strongly regular graph with parameters $(2n,2,0,2)$.