7 Hadamard Matrices and Reed-Muller Codes

Hadamard Matrices

Definition

A Hadamard matrix of order $n$ is $(n\times n)$-matrix $H$ with entries $-1,1$ such that $H{H}^T=nI$.

Example.

Two operations. Let $H$ be a Hadamard matrix. Then

• Multiplying a row/column of $H$ by $-1$, results in a Hadamard matrix.
• Permuting rows/columns of $H$ results in a Hadamard matrix.

Hence, we can always get a form of $H$ like this

$$\left[\begin{array}{cccc}1& 1& \cdots & 1\\ 1& & & \\ ⋮& & \ast & \\ 1& & & \end{array}\right].$$

Theorem

If $H$ is a Hadamard matrix of order $n$, then $n=1$, $n=2$, or $n\equiv 0(\mathrm{mod}4)$.

\begin{proof} Let $n>2$. WLOG assume that first row $n$ are $1$‘s. Then the second row: $n/2$ $1$‘s and $n/2$ $-1$‘s. It follows that $n\equiv 0(\mathrm{mod}2)$. Similarly compute the third row and get $n\equiv 0(\mathrm{mod}4)$. For more details, see A course in combinatorics - 2001 - van Lint, Wilson.pdf, Theorem 18.1. \end{proof}

Hadamard Conjecture.

The condition in ^09ce21 is sufficient.

Still open question. It has been verified $⩽668,716$.

Hadamard, 1893

$M=(m_{ij})\in {\mathbb{C}}^{n\times n}$, $|m_{ij}|⩽1$, then $|\det (M)|⩽n^{n/2}$. The equality holds iff $M{M}^{\ast }=nI$. In that case, $|m_{ij}|=1$.

Sylvester's construction

If $H$ is a Hadamard matrix, then $\left(\begin{array}{cc}H& H\\ H& -H\end{array}\right)$ is a Hadamard matrix.

\begin{proof} Easy. \end{proof}

Recall that for two matrices $A$ and $B$, $A\otimes B$ is defined here.

Theorem

If $H_m,H_n$ are Hadamard matrices of order $m,n$, respectively. Then $H_m\otimes H_n$ is a Hadamard matrix of order $mn$.

\begin{proof} Similar to ^jqjjg1. \end{proof}

Definition

A conference matrix $C$ of order $n$ is an $(n\times n)$-matrix with $0$‘s on the diagonal, and $\pm 1$ everywhere else such that $C{C}^T=(n-1)I$.

We have equivalence classes for conference matrices:

• multiplying row/column by $-1$
• permute row and column (at the same time)

Lemma

Let $C$ be a conference matrix of order $n>1$, then $2\mid n$. Furthermore,

• If $n\equiv 2(\mathrm{mod}4)$, then we can find an “equivalent” symmetric conference matrix ($C=C^T$).
• If $n\equiv 0(\mathrm{mod}4)$, then we can find an “equivalent” antisymmetric conference matrix $(C=-C^T)$.

\begin{proof} Similar to Hadamard matrices. \end{proof}

Theorem

If $C$ is an antisymmetric conference matrix, then $I+C$ is a Hadamard matrix.

\begin{proof} $(I+C)(I+C{)}^T=I+C+C^T+C{C}^T=I+C+(-C)+(n-1)I=nI$. \end{proof}

Theorem

If $C$ is a symmetric conference matrix, then $H=\left(\begin{array}{cc}I+C& -I+C\\ -I+C& -I+C\end{array}\right)$ is a Hadamard matrix.

\begin{proof} Easy. \end{proof}

Definition

Define $\chi :\mathrm{GF}(q)\to \{-1,0,1\}\subseteq \mathbb{C}$ as

$$\{\begin{array}{ll}0& \text{if }x=0,\\ 1& \text{if }x\text{ is square},\\ -1& \text{if }x\text{ is nonsquare}.\end{array}$$

Proposition

The followings hold.

• $\chi (x)\chi (y)=\chi (xy)$
• ${\sum }_{x\in \mathrm{GF}(q)}=0$
• ${\sum }_{b\in \mathrm{GF}(q)}\chi (b)\chi (b+c)=-1$

\begin{proof} i) and ii) are easy.

For iii), note that

$$\sum _{b\in \mathrm{GF}(q)}\chi (b)\chi (b+c)=\sum _{b\in \mathrm{GF}(q)}\chi (b)\chi (b)\chi (1+c{b}^{-1})=\sum _{d\in \mathrm{GF}(q),d\ne 1}\chi (d)=-1.$$

Now we finish the proof. \end{proof}

Write ${\mathbb{F}}_q=\{0,a_1,\cdots ,a_{q-1}\}$. Define the $q\times q$ matrix $Q$ by $q_{ij}=\chi (a_i-a_j)$ for all $0⩽i,j⩽q$. Hence, if $q\equiv 1(\mathrm{mod}4)$, $Q$ is symmetric; if $q\equiv 3(\mathrm{mod}4)$, $Q$ is antisymmetric.

Define a $(q+1)\times (q+1)$ matrix $C$ by

$$C=\left(\begin{array}{cccc}0& 1& \cdots & 1\\ \pm 1& & & \\ ⋮& & Q& \\ \pm 1& & & \end{array}\right)$$

such that $C$ is symmetric/antisymmetric.

By ^hx2ueq ii) and iii), we have $QJ=JQ=0$ and $Q{Q}^T=qI-J$. Hence $C$ is a conference matrix.

John Williamson, 1944

Take matrices $A_1,A_2,A_3,A_4$ such that they are symmetric and commutative. Define

$$H=\left(\begin{array}{cccc}{A}_1& A_2& A_3& A_4\\ -A_2& A_1& -A_4& A_3\\ -A_3& A_4& A_1& -A_2\\ -A_4& -A_3& A_2& A_1\end{array}\right).$$

Then $H{H}^T=I_4\otimes (A_1^2+A_2^2+A_3^2+A_4^2)$. So $H$ is Hadamard if

• $A_i$ entries in $\pm 1$;
• $A_i{A}_j=A_j{A}_i$;
• $A_1^2+A_2^2+A_3^2+A_4^2=4n{I}_n$.

Consider

$$U=\left(\begin{array}{ccccc}0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& & & \ddots & 1\\ 1& 0& 0& \cdots & 0\end{array}\right)$$

Say $a_{i0}=1$ for all $i\in \{1,\cdots ,4\}$, and $a_{ij}=a_{i,n-j}$ for $i\in \{1,\cdots ,4\}$ and $j\in \{1,\cdots ,n\}$. Define $A_i={\sum }_{j=0}^{n-1}{a}_{ij}{U}^j$, then $A_i$ is commute.

Reed-Muller Codes

In general,

• Take Hadamard matrices $H_n$, $-H_n$ and set $n=2^m$.
• By ^jqjjg1, $\left(\begin{array}{cc}{H}_n& H_n\\ H_n& -H_n\end{array}\right)$ is a Hadamard matrix.
• Replace $1$ by $0$, and replace $-1$ by $1$.
• The $2\cdot 2^m$ rows are called Reed-Muller code.

Theorem

Let $R^{\prime }(1,m)$ denote the set of row vectors in ${\mathbb{F}}_2^n$ obtained from ${\mathbf{H}}_n$ as described above. Then $R^{\prime }(1,m)$ is an $m+1$ dimensional subspace of ${\mathbb{F}}_2^n$.

Here is an example.