One of the surprising things about linear algebra over a finite field is that a non-zero vector can be orthogonal to itself.

When you take the inner product of a **real** vector with itself, you get a sum of squares of real numbers. If any element in the sum is positive, the whole sum is positive.

In a **finite field**, things don’t work that way. A list of non-zero squares can add up to zero.

In the previous post, we looked at the ternary Golay code, an error correcting code that multiplies a vector of data by a rectangular matrix mod 3. That post included the example that

[1, 0, 1, 2, 2]

was encoded as

[1 0 1 2 2 0 1 0 2 0 0].

The output is orthogonal to itself:

1² + 0² + 1² + 2² + 2² + 0² + 1² + 0² + 2² + 0² + 0² ≡ 0 (mod 3).

In fact, every output of the ternary Golay code will be self-orthogonal. To see this, let *v* be a 1 by 5 row vector. Then its encoding is *vG* where *G* is the 5 by 11 matrix in the previous post. The inner product of *vG* with itself is

*vG* (*vG*)^{T} = *vG**G*^{T}*v*^{T}.

We can easily show that *G**G*^{T} is a zero matrix using Python:

>>> (G@G.T)%3 [[0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0]]

And so

*vG**G*^{T}*v*^{T} = *v**O**v*^{T} = 0.

If a vector is not self-orthogonal, there has been an error. For example, if one of the 0s in our output turned into a 1 or a 2, the inner product of the corrupted vector with itself would be equal to 1 (mod 3) rather than 0.

Self-orthogonality is necessary but not sufficient for an encoded vector to be error-free. Correctly encoded vectors form a 5 dimensional subspace of *GF*(3)^{11}, namely the row space of *G*. The set of self-orthogonal vectors in *GF*(3)^{11} is a larger space.

A sufficient condition for a row vector *w* to be the encoding of a data vector *v* is for

*Gw ^{T}*

to be the zero vector (carrying out all calculations mod 3).

The ternary Golay code is capable of detecting and correcting corruption in up to two spots in a vector. For example, suppose we take our vector

[1 0 1 2 2 0 1 0 2 0 0]

above and corrupt it by turning the first couple 2’s to 1’s.

[1 0 1 1 1 0 1 0 2 0 0]

We’d still get a self-orthogonal vector, but the product *Gw ^{T}* would not be zero.

>>> v = np.array( [1, 0, 1, 2, 2] ) >>> w = (v@G)%3 >>> w[3] = w[4] = 1 >>> print((G@w)%3)

This prints

[0 0 0 2 2]

which lets us know that the modified version of *w* is not a valid encoding, not a part of a row space of *G*.

If we know (or are willing to assume) that

[1 0 1 1 1 0 1 0 2 0 0]

is the result of no more than two changes applied a valid code word *vG*, then we can recover *vG* by looking for the closest vector in the row space of *G*. Here closeness is measured in Hamming distance: the number of positions in which vectors differ. Every vector in *GF*(3)^{11} is within a distance of 2 from a unique code word, and so the code can correct any two errors.