Conference Matrices

# Conference Matrices

We will now look at another type of matrix known as a conference matrix.

 Definition: An $n \times n$ matrix $C$ is a Conference Matrix if every entry $c_{i,j}$ is either $0$, $-1$, or $1$ and $CC^T = (n-1)I_n$.

Let $C = \begin{bmatrix} 0 & 1 \\ 1 ^ 0 \end{bmatrix}$. Then $C$ is a conference matrix as every entry of $C$ is either $0$, $-1$, or $1$ and:

(1)
\begin{align} \quad CC^T = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \\ = 1I_2 \end{align}

We will now begin to develop of a method for constructing conference matrices. We will first need to define a special function first.

 Definition: Let $q$ be an odd prime power and let $(\mathbb{Z}_q, +)$ denote the additive group of integers modulo $q$. Let $D_q$ be the set of all nonzero squares modulo $q$. The Quadratic Character Function on $\mathbb{Z}_q$ is $\chi_q : \mathbb{Z}_q \to \{ -1, 0, 1 \}$ defined for all $x \in \mathbb{Z}_q$ by $\chi_q(x) = \left\{\begin{matrix} 0 & \mathrm{if} \: x = 0\\ 1 & \mathrm{if} \: x \in D \\ -1 & \mathrm{if} \: x \not \in D \end{matrix}\right.$.

For example, consider the prime $q = 7$. The set of all nonzero squares modulo $q$ is:

(2)
\begin{align} \quad D_7 = \{ 1, 2, 4 \} \end{align}

Therefore the quadratic character function on $\mathbb{Z}_7$ is:

(3)
\begin{align} \quad \chi_7(0) &= 0 \\ \quad \chi_7(1) &= 1 \\ \quad \chi_(2) &= 1 \\ \quad \chi_7(3) &= -1 \\ \quad \chi_7(4) &= 1 \\ \quad \chi_7(5) &= -1 \\ \quad \chi_7(6) &= -1 \\ \end{align}

The following theorem gives us a method for constructing a conference matrix given a prime power $q$ of the form $q = 4n - 3$

 Theorem 1: Let $q = 4n -3$ be a prime power and let $(\mathbb{Z}_q, +)$ denote the additive group of integers modulo $q$. Let $\infty$ denote a new point distinct from those in $\mathbb{Z}_q$ and preceding the ordering of $\mathbb{Z}_q$. Let $C$ be the $(q + 1) \times (q + 1)$ matrix whose entries are defined by $c_{i,j} = \left\{\begin{matrix} 1 & \mathrm{if} \: i = \infty, j \neq \infty \\ 1 & \mathrm{if} \: i \neq \infty, j= \infty \\ 0 & \mathrm{if} \: i = \infty, j = \infty \\ \chi_q(i-j) & \mathrm{if} \: i, j \in \mathbb{Z}_q \end{matrix}\right.$. Then $C$ is a conference matrix.

The condition that $q = 4n - 3$ is a prime power is equivalent to $q$ being a prime power such that $q \equiv 1 \pmod 4$.

For example, consider the prime $q = 5$. Clearly $q$ is a prime power and $q = 4(2) - 3$.

We aim to construct a $(q+1) \times (q+1) = 6 \times 6$ conference matrix. Let $D_5$ be the set of nonzero squares modulo $5$. Then:

(4)
\begin{align} \quad D_5 = \{ 1, 4 \} \end{align}

The quadratic character function $\chi_5 : \mathbb{Z}_5 \to \{ -1, 0, 1 \}$ is therefore:

(5)
\begin{align} \quad \chi_5(0) = 0 \\ \quad \chi_5(1) = 1 \\ \quad \chi_5(2) = -1 \\ \quad \chi_5(3) = -1 \\ \quad \chi_5(4) = 1 \end{align}

The matrix $C$ from Theorem 1 above will then be:

(6)
\begin{align} \quad C_{6 \times 6} &= \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & \chi_5(0-0) & \chi_5(0-1) & \chi_5(0-2) & \chi_5(0-3) & \chi_5(0-4) \\ 1 & \chi_5(1-0) & \chi_5(1-1) & \chi_5(1-2) & \chi_5(1-3) & \chi_5(1-4) \\ 1 & \chi_5(2-0) & \chi_5(2-1) & \chi_5(2-2) & \chi_5(2-3) & \chi_5(2-4) \\ 1 & \chi_5(3-0) & \chi_5(3-1) & \chi_5(3-2) & \chi_5(3-3) & \chi_5(3-4) \\ 1 & \chi_5(4-0) & \chi_5(4-1) & \chi_5(4-2) & \chi_5(4-3) & \chi_5(4-4) \\ \end{bmatrix} \\ &= \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & \chi_5(0) & \chi_5(4) & \chi_5(3) & \chi_5(2) & \chi_5(1) \\ 1 & \chi_5(1) & \chi_5(0) & \chi_5(4) & \chi_5(3) & \chi_5(2) \\ 1 & \chi_5(2) & \chi_5(1) & \chi_5(0) & \chi_5(4) & \chi_5(3) \\ 1 & \chi_5(3) & \chi_5(2) & \chi_5(1) & \chi_5(0) & \chi_5(4) \\ 1 & \chi_5(4) & \chi_5(3) & \chi_5(2) & \chi_5(1) & \chi_5(0) \\ \end{bmatrix} \\ &= \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & -1 & -1 & 1 \\ 1 & 1 & 0 & 1 & -1 & -1 \\ 1 & -1 & 1 & 0 & 1 & -1 \\ 1 & -1 & -1 & 1 & 0 & 1 \\ 1 & 1 & -1 & -1 & 1 & 0 \\ \end{bmatrix} \end{align}