Sum of codevectors of a linear code

Question

Given a linear $(n,M,d)_q$ code, and its generator matrix $G$, I was wondering if there was a way to compute the sum of all the non-zero codevectors without computing every single one? Is there a quick way to do this?

Answer 1

TL: DR version

For a linear $[n,k]_q$ code over the finite field $\mathbb F_q$, the sum of all the codewords is the all-zeroes codeword $\mathbf 0$ except when $q=2, k=1$ and the code has two distinct codewords, in which case the sum equals the (unique) nonzero binary codeword. (Thanks to @leonbloy for pointing out that I had missed this exceptional case).

---

The proof is based on the result that in each of the $n$ coordinate positions, the $q^k$ codewords either (i) all have value $0$, or (ii) for each $\alpha \in \mathbb F_q$, exactly $q^{k-1}$ codewords have value $\alpha$ in that coordinate position.

Fix the coordinate position under consideration, and let $\mathcal C(\alpha) \subset \mathcal C$ be the set of codewords that have value $\alpha \in\mathbb F_q$ in the chosen coordinate position. Note that $\mathcal C(0)$ is nonempty since at least one codeword ($\mathbf 0$, of course!) is known to have value $0$ in the chosen position; there may be other codewords too that enjoy this property. Now, if $\mathcal C(0) = \mathcal C$, that is, all the codewords have value $0$ in the chosen coordinate position, then the sum of all the codewords (which is a codeword) also has value $0$ in the chosen position. Note that the assumption $\mathcal C(0) = \mathcal C$ implies that $\mathcal C(\alpha) = \emptyset$ for all nonzero $\alpha \in \mathbb F_q$.

Now suppose that there is a codeword $\mathbf C^{\beta)}$ that has nonzero value $\beta \in \mathbb F_q$ in the chosen position, and consider the set of codewords $\{\mathbf C^{\beta)}+\mathbf C \colon \mathbf C \in \mathcal C(0)\}$. Each of these $\big|\mathcal C(0)\big|$ codewords has value $\beta+0 = \beta$ in the chosen coordinate position and thus is a member of $\mathcal C(\beta)$. Of course, one of the codewords in $\{\mathbf C^{\beta)}+\mathbf C \colon \mathbf C \in \mathcal C(0)\}$ is $\mathbf C^{(\beta)} + \mathbf 0 = \mathbf C^{(\beta)}$ itself. We conclude that $\{\mathbf C^{\beta)}+\mathbf C \colon \mathbf C \in \mathcal C(0)\}$ is a subset of $\mathcal C(\beta)$ and that $$\big|\{\mathbf C^{\beta)}+\mathbf C \colon \mathbf C \in \mathcal C(0)\}\big| =\big|\mathcal C(0)\big| \leq \big|\mathcal C(\beta)\big|. \tag{1}$$ Conversely, every one of the $\big|\mathcal C(\beta)\big|$ codewords in $\{\mathbf C^{\beta)}-\mathbf C^\prime \colon \mathbf C^\prime \in \mathcal C(\beta)\}$ is a codeword in $\mathcal C(0)$, one of them being $\mathbf C^{\beta)}-\mathbf C^{\beta)} = \mathbf 0$. Thus, $\{\mathbf C^{\beta)}-\mathbf C^\prime \colon \mathbf C^\prime \in \mathcal C(\beta)\} \subset \mathcal C(0)$ and we have that $$\big|\{\mathbf C^{\beta)}+\mathbf C^\prime \colon \mathbf C^\prime \in \mathcal C(\beta)\}\big| =\big|\mathcal C(\beta)\big| \leq \big|\mathcal C(0)\big|. \tag{2}$$ From $(1)$ and $(2)$ we have that $$\big|\mathcal C(\beta)\big| = \big|\mathcal C(0)\big|. \tag{3}$$ Next, note that since the code is linear, for each nonzero $\alpha \in \mathbb F_q$, the scalar multiple $(\alpha\beta^{-1})\mathbf C^{(\beta)}$ of $\mathbf C^{(\beta)}$ is a codeword $\mathbf C^{(\alpha)}$ that has value $\alpha$ in the chosen position. A repetition of the above argument shows that $\big|\mathcal C(\alpha)\big|$ also equals $\big|\mathcal C(0)\big|.$ In short, all $q$ subsets $\mathcal C(\alpha), \alpha \in \mathbb F_q$, have the same cardinality and we conclude that for each $\alpha \in \mathbb F_q$, exactly $q^{k-1}$ codewords have value $\alpha$ in the chosen position, as claimed above.

It follows that the sum of all $q^k$ codewords has value $$\sum_{\alpha \in \mathbb F_q} (\underbrace{\alpha + \alpha + \cdots + \alpha)}_{q^{k-1}~\text{terms}}\tag{4}$$ in the chosen position. Now,

• If $k \geq 2$, the number of terms in each summand in $(4)$ is a multiple of $q$ and hence of $p$, the characteristic of the field. Consequently, each summand has value $0$ and so does the sum in $(4)$ have value $0$.

• If $k = 1$, each summand in $(4)$ has value $\alpha$ and so $(4)$ is just the sum of all the elements of $\mathbb F_q$. Now, the elements of $F_q$ are the roots of the polynomial $x^q - x \in \mathbb F_q[x]$. The sum of the roots is the negative of the coefficient of $x^{q-1}$ in $x^q - x$ which coefficient is readily perceived to be $0$ when $q > 2$ and to have value $-1$ when $q=2$. In summary,

In a linear $[n,k]_q$ code over $\mathbb F_q$, the sum of the $q^k$ codewords equals $\mathbf 0$ except when $q=2$ and $k=1$. In this exceptional case, the sum of the two binary codewords $\mathbf 0$ and $\mathbf C$ of length $n$ equals $\mathbf C.$