Working in GF(2)

Introduction

bit is a header-only C++ library that provides classes for bit-vectors and bit-matrices.

In the jargon of professional mathematics, the classes make it possible to perform linear algebra over GF(2), the simplest [Galois field] with just two elements 0 & 1. In GF(2), also commonly known as $\mathbb{F}_2$, addition/subtraction and multiplication/division operations are all done mod two, which keeps everything closed in the set {0,1}.

This document contains some technical notes on the joys and travails of mathematics using vectors and matrices where the elements are all just zeros and ones and where all arithmetic is mod 2.

Some things are different!

Over $\R$, the only self-orthogonal vector is the zero vector.
If $\mathbf{x}$ is a vector over $\R$ then \[ \mathbf{x} \cdot \mathbf{x} = 0 \iff \mathbf{x} = \mathbf{0}, \] Put another way, the only vector of size 0 over $\R$ is the zero vector.

That is not true for vectors over $\mathbb{F}_2$.

For example, if $\mathbf{v} = \{1, 1\}$ is thought of as a vector over $\mathbb{F}_2$ then \[ \mathbf{v} \cdot \mathbf{v} = \{1, 1\} \cdot \{1, 1\} = 1 + 1 = 2 \rightarrow 0 \text{ mod 2}. \] So $\mathbf{v}$ is non-zero but self-orthogonal.

Let $\mathbf{v}$ be a general $n$-dimensional vector over $\mathbb{F}_2$ then \[ \mathbf{v} \cdot \mathbf{v} = v_1 v_1 + v_2 v_2 + \cdots v_n v_n. \] Now \[ v_i v_i = \begin{cases} 1 & \text{if} & v_i = 1, \\ 0 & \text{if} & v_i = 0 \end{cases} \] It follows that \[ \mathbf{v} \cdot \mathbf{v} = v_1 + v_2 + \cdots v_n, \] where of course those additions in $\mathbb{F}_2$ are done modulo 2. Hence \[ \mathbf{v} \cdot \mathbf{v} = \begin{cases} 0 & \text{if the number of ones in the vector is even}, \\ 1 & \text{if the number of ones in the vector is odd}. \end{cases} \] Half of all vectors over $\mathbb{F}_2$ will be self-orthogonal!

Some of the best-known algorithms for linear algebra over $\R$ rely on Gram-Schmidt. A critical step in Gram-Schmidt is to normalize a vector by simply dividing each element by the norm $\lVert \mathbf{x} \rVert = \sqrt{\mathbf{x} \cdot \mathbf{x}}$. However, this will never work in $\mathbb{F}_2$ as that norm will be zero 50% of the time. All those algorithms must be modified to work for vectors and matrices over $\mathbb{F}_2$.

Some things are simpler

Recall that if $A x = b$ represents a system of linear equations over $\R$, you can accomplish quite a lot using three elementary row operations.

Elementary Row Operations for $\R$

swap rows:: Swap the positions of any two rows.
scale row:: Multiply a row by a non-zero number.
add or subtract rows:: Add one row to another row.

However, in $\mathbb{F}_2$, the only non-zero scalar is one, and addition is the same as subtraction, so for matrices over $\mathbb{F}_2$, there are just two elementary row operations:

Elementary Row Operations for $\mathbb{F}_2$

swap rows:: Swap the positions of any two rows.
add rows:: Add one row to another row.

Gaussian Elimination in $\mathbb{F}_2$

Suppose that $A$ is an $n \times n$ matrix over $\mathbb{F}_2$ and $b$ is a compatibly sized bit-vector where we are interested in finding an $x$ satisfying $A \cdot x = b$. Then the pseudocode for Gaussian elimination looks like:

\begin{algorithm} \caption{Gaussian Elimination in $F_2$} \begin{algorithmic} \Procedure{Solve}{$A, b, n$} \For {$j = 0$ \To $n - 1$} \State $s = j$ \While {$A(s,j) = 0$} \State $s = s + 1$ \EndWhile \If {$s > n$} \Continue \EndIf \If {$ s \ne j$} \State swap rows $s$ and $j$ in the matrix $A$ \State swap elements $s$ and $j$ in the vector $b$ \EndIf \For {$i = j+1$ \To $n$} \If {$A(i,j) == 1$} \State replace row $i$ in $A$ with the sum of rows $i$ and $j$ \State replace element $i$ in $b$ with the sum of elements $i$ and $j$ \EndIf \EndFor \EndFor \EndProcedure \end{algorithmic} \end{algorithm}

Introduction

Some things are different!

Some things are simpler

Gaussian Elimination in \(\mathbb{F}_2\)