Linear Algebra over \(\mathbb{F}_2\)

GF2++ is a header-only C++ library that provides classes for boolean vectors and 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), addition/subtraction and multiplication/division operations are all done mod 2 which keeps everything closed in the set {0,1}.

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

Some things are different!

Over \(\mathbb{R}\) the only vector of size zero in the zero vector itself. If \(\mathbf{x}\) is a vector over \(\mathbb{R}\) then

\[\mathbf{x} \cdot \mathbf{x} = 0 \iff \mathbf{x} = \mathbf{0},\]

Put anther way, the only self-orthogonal vector over \(\mathbb{R}\) is the zero vector.

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

For example, if \(\mathbf{v} = \{1, 1\}\) is considered 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 clearly non-zero but yet it is 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}\]

so 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. This means that

\[\mathbf{v} \cdot \mathbf{v} = \begin{cases} 0 & \text{if the number of ones in } \mathbf{v} \text{ is even}, \\ 1 & \text{if the number of ones in } \mathbf{v} \text{ is odd}. \end{cases}\]

Hence half of all vectors over \(\mathbb{F}_2\) will be self-orthogonal!

Some of the best known algorithms for linear algebra over \(\mathbb{R}\) rely on the Gram Schmidt process. 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}}\). This is not going to work in \(\mathbb{F}_2\) as 50% of the time that norm will be zero. All those algorithms need to be modified to work for vectors and matrices over \(\mathbb{F}_2\).

Some things are simpler

We recall that if \(A x = b\) represents a system of linear equations over \(\mathbb{R}\) then quite a lot can be accomplished by just using elementary row operations on the matrix \(A\). Those operations are:

  1. Swap the positions of any two rows.

  2. Multiply a row by a non-zero number.

  3. Add (a possibly scale multiple of) one row to another row.

The scalar in that last step might be \(-1\) so that operation also encompasses the possibility of subtracting two rows.

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

  1. Swap the positions of any two rows.

  2. Add one row to another row.

If \(A x = b\) now represents a system of linear equations that we are trying to solve in \(\mathbb{F}_2\)

Gaussian elimination: \(A\) is an \(n \times n\) matrix over \(\mathbb{F}_2\) and \(b\) is \(n\)-element vector over \(\mathbb{F}_2\)
for each column j = 1:n do
    s = j
    while A(s,j) == 0 do
        s = s + 1
    end while
    if s > n then
        continue outer for loop at the next j
    end if
    if s != j then
        swap(A.row(s), A.row(j))
        swap(b(s), b(j))
    end if
    for each row i = j+1:n
        if A(i,j) == 1 then
            A.row(i) = A.row(i) + A.row(j)
            b(i) = b(i) + b(j)
        end if
    end for
end for