2 Preliminaries
We write \([N] = \{ 1, \dots , N\} \). For a vector \(c \in \mathbb {F}^N\), the support is \(\operatorname{supp}(c) := \{ i \in [N] : c_i \neq 0 \} \). For two vector spaces \(V, W\) over \(\mathbb {F}\) we write \(V \le W\) to mean \(V\) is a subspace of \(W\). (Standard; recalled so later nodes can depend on it.)
The dual code \(C^{\perp } \le \mathbb {F}^N\) of a linear code \(C \le \mathbb {F}^N\) is the subspace of all vectors orthogonal (under the standard dot product \(\langle u, v\rangle = \sum _{i=1}^N u_i v_i\)) to every codeword of \(C\). Elements of \(C^{\perp }\) are called dual codewords (of \(C\)).
For a linear code \(C \le \mathbb {F}^N\) one has \(\dim C^{\perp } = N - \dim C\). In particular, for a code with systematic encoding the dimension of \(C^{\perp }\) equals the redundancy \(N - n\) of \(C\).
Suppose \(C \le \mathbb {F}^N\) is a linear code with a systematic encoding, and there exist an index \(i \in [N]\), a set \(R \subset [N] \setminus \{ i\} \), and a linear function \(g\) such that \(g(c|_R) = c_i\) for all codewords \(c \in C\). Then there exists a nonzero dual codeword \(c^{\perp }\) such that \(\operatorname{supp}(c^{\perp }) \subset R \cup \{ i\} \) and \(i \in \operatorname{supp}(c^{\perp })\).
Since \(g\) is linear, write \(g(c|_R) = \sum _{j \in R} \alpha _j c_j\) for scalars \(\alpha _j \in \mathbb {F}\). The hypothesis \(g(c|_R) = c_i\) gives, for all codewords \(c \in C\),
Thus the vector \(c^{\perp }\in \mathbb {F}^N\) defined by \(c^{\perp }_j = -1\) if \(j = i\), \(c^{\perp }_j = \alpha _j\) if \(j \in R\), and \(c^{\perp }_j = 0\) otherwise satisfies \(\langle c^{\perp }, c\rangle = 0\) for every codeword \(c\), so \(c^{\perp }\) is a dual codeword. By construction \(\operatorname{supp}(c^{\perp }) \subseteq R \cup \{ i\} \), and \(c^{\perp }_i = -1 \neq 0\) gives \(i \in \operatorname{supp}(c^{\perp })\); in particular \(c^{\perp }\) is nonzero.
Let \(e_i\) denote the standard basis vector of \(\mathbb {F}^N\), so \((e_i)_i = 1\) and \((e_i)_j = 0\) for \(j \neq i\). For \(v^{(1)}, \dots , v^{(s)} \in \mathbb {F}^N\), the tensor product \(v^{(1)} \otimes \cdots \otimes v^{(s)} \in \mathbb {F}^{N^s}\) is the vector indexed by tuples \((i_1, \dots , i_s) \in [N]^s\) with
A tensor of this form is a simple tensor; a tensor is any linear combination of simple tensors.
The set of simple tensors
forms a basis for \(\mathbb {F}^{N^s}\), the standard tensor basis. Consequently every vector in \(\mathbb {F}^{N^s}\) has a unique expression as a linear combination of standard tensor basis elements, the standard basis representation; we say it contains a basis element when the corresponding coefficient is nonzero.
Let \((e^{(1)}, w^{(1)}), \dots , (e^{(D)}, w^{(D)})\) be pairs of tensors in \(\mathbb {F}^{N^s}\) such that, for all \(i = 1, \dots , D\), the tensor \(e^{(i)}\) is in the standard tensor basis and the standard basis representation of \(w^{(i)}\) contains \(e^{(i)}\) and none of \(e^{(i+1)}, \dots , e^{(D)}\). Then \(w^{(1)}, \dots , w^{(D)}\) are linearly independent.
Suppose for contradiction that \(\sum _{i=1}^{D} \alpha _i w^{(i)} = 0\) is a nontrivial linear relation. Let \(j\) be the largest index with \(\alpha _j \neq 0\); then \(\alpha _i = 0\) for \(i {\gt} j\), so the relation reads \(\sum _{i=1}^{j} \alpha _i w^{(i)} = 0\). By hypothesis the standard basis representation of \(w^{(j)}\) contains \(e^{(j)}\), so we may write \(w^{(j)} = \beta \, e^{(j)} + w'\) for some \(\beta \neq 0\) and some \(w' \in \mathbb {F}^{N^s}\) whose standard basis representation does not contain \(e^{(j)}\). For each \(i {\lt} j\), since \(j {\gt} i\) we have \(e^{(j)} \in \{ e^{(i+1)}, \dots , e^{(D)}\} \), so by hypothesis the standard basis representation of \(w^{(i)}\) does not contain \(e^{(j)}\). Hence the coefficient of \(e^{(j)}\) in
equals \(\alpha _j \beta \), because none of \(w^{(1)}, \dots , w^{(j-1)}, w'\) contributes to \(e^{(j)}\). Since \(\alpha _j, \beta \neq 0\) this coefficient is nonzero, contradicting \(\sum _{i=1}^{j} \alpha _i w^{(i)} = 0\).
For a subspace \(V \le \mathbb {F}^N\) and a positive integer \(s\), let \(V^{\otimes s}\) denote the subspace of \(\mathbb {F}^{N^s}\) spanned by the simple tensors \(v^{(1)} \otimes \cdots \otimes v^{(s)}\) with \(v^{(1)}, \dots , v^{(s)} \in V\).
For every subspace \(V \le \mathbb {F}^N\) and positive integer \(s\), \(\dim V^{\otimes s} = (\dim V)^s\).