Orthogonal bases of the vector space $\mathbb{Z}_2^4$

Question

Let $\mathbb{Z}_2$ be the two element field $\mathbb{Z}/2\mathbb{Z}$.

The vectors $e_0 = \langle1,1,1,1\rangle$, $e_1=\langle1,1,0,0\rangle$, $e_2 = \langle1,0,0,1\rangle$, $e_3 = \langle1,0,1,0\rangle$ in the $\mathbb{Z}_2$-vector space $\mathbb{Z}_2^4$ don't form a basis of $\mathbb{Z}_2^4$.

Compare this to $\langle1,0,0,0\rangle$, $\langle 0,1,0,0\rangle$, $\langle 0,0,1,0\rangle$, $\langle 0,0,0,1\rangle$ which do form a orthonormal basis of $\mathbb{Z}_2^4$ and to $\langle 1,1,1,1\rangle$, $\langle 1,1,-1,-1\rangle$, $\langle 1,-1,-1,1\rangle$, $\langle 1,-1,1,-1\rangle$ which form a orthogonal basis of the $\mathbb{R}$-vector space $\mathbb{R}^4$ (the Hadamard-Walsh basis).

What does this mean? Does it mean, that there is essentially only one basis of $\mathbb{Z}_2^4$?

If not so:

What are the orthogonal bases of $\mathbb{Z}_2^4$?

What are the orthogonal bases of $\mathbb{Z}_2^8$?

(Complete lists would be welcome.)

Answer 1

We call a basis $({\bf e}_1, \ldots {\bf e}_n)$ of $\Bbb F^n$ orthogonal iff

• ${\bf e}_i \cdot {\bf e}_i \neq 0$ for all $i$ and
• ${\bf e}_i \cdot {\bf e}_j = 0$ for $i \neq j$,

where ${\bf a} \cdot {\bf b} = \sum_{i = 1}^n a_i b_i$. For $\Bbb F = \Bbb Z_2$, the first condition is the same as ${\bf e}_i \cdot {\bf e}_i = 1$, so in this case orthgononal bases coincide with what we might called orthonormal bases, and a basis is orthogonal iff $$\phantom{(\ast)} \qquad \pmatrix{{\bf e}_1 & \cdots & {\bf e}_n}^\top \pmatrix{{\bf e}_1 & \cdots & {\bf e}_n} = I_n . \qquad (\ast)$$

In the case $n = 4$, the first condition implies that each basis element contains exactly one or three $1$'s. If it contains an element $\bf a$ with one $1$ and an element $\bf b$ with three $1$'s, then the second condition implies that ${\bf b} = {\bf a} + \pmatrix{1&1&1&1}^\top$, so the basis can only have one element with one $1$ and one with three $1$'s, a contradiction. Thus, any orthogonal basis consists only of elements with one $1$ or elements with three $1$'s. But there are four of each, so the only orthogonal bases are reorderings of the standard basis $({\bf e}_i)$ and its complement $\left({\bf e}_i + \pmatrix{1&1&1&1}^\top\right)$, and hence there are $48$ (ordered) bases.

More generally, one can use a clever orbit-stabilizer argument for the action of $GL(n, \Bbb Z_2)$ on the space of symmetric $n \times n$ matrices over $\Bbb Z_2$ to compute the number of orthogonal bases over $\Bbb Z_2$, equivalently, the number of matrices satisfiying $(\ast)$. We get:

• for even $n$: $$2^{n / 2} \prod_{i = 1}^{n / 2 - 1} (2^n - 4^i)$$
• for odd $n$: $$2^{(n - 1) / 2 - 1} \prod_{i = 0}^{(n - 1) / 2 - 1} (2^{n - 1} - 4^i).$$

In particular:

• for $n = 4$ we recover that the number of ordered bases is $2 \cdot 4!$ (unordered bases: $2$), and
• for $n = 8$ the number of ordered bases is $2^9 \cdot 3^2 \cdot 9!$ (unordered bases: $2^9 \cdot 3^2 = 4608$).

This number of unordered bases for general $n$ is OEIS A088437.

The details of the counting argument, which is given for general finite fields $\Bbb F_{2^k}$ of characteristic $2$ (and which is framed in terms of matrices satisfying $(\ast)$), are recorded in:

MacWilliams, J. "Orthogonal Matrices Over Finite Fields," Amer. Math. Month. 76(2) (1969), 152-164.