[proofplan] Assemble the parity conditions into a $(\delta - 1) \times n$ matrix $M$ whose rows are evaluations of $c(\alpha^m)$ for $m = 1, \ldots, \delta - 1$. Every codeword $c \in C$ satisfies $M c^\top = 0$ by definition. The key structural fact is that any $\delta - 1$ columns of $M$, once common factors are stripped, form a **Vandermonde matrix** at distinct nodes — its determinant is non-zero, so any $\delta - 1$ columns of $M$ are $\mathbb{F}$-linearly independent. A non-zero codeword $c$ gives a non-trivial linear dependence among the columns of $M$ indexed by the support of $c$; such a dependence cannot have only $\delta - 1$ or fewer terms. Hence $\operatorname{wt}(c) \geq \delta$. [/proofplan] [step:Assemble the parity conditions into a single matrix $M$] Let $\mathbb{F}$ be any field containing $\alpha$ (for instance $\mathbb{F}_q(\alpha)$). Define \begin{align*} M \in \mathbb{F}^{(\delta - 1) \times n}, \qquad M_{m, j} := \alpha^{m(j - 1)} \text{ for } 1 \leq m \leq \delta - 1,\ 1 \leq j \leq n. \end{align*} Explicitly, \begin{align*} M = \begin{pmatrix} 1 & \alpha & \alpha^2 & \cdots & \alpha^{n - 1} \\ 1 & \alpha^2 & \alpha^4 & \cdots & \alpha^{2(n - 1)} \\ \vdots & & & & \vdots \\ 1 & \alpha^{\delta - 1} & \alpha^{2(\delta - 1)} & \cdots & \alpha^{(\delta - 1)(n - 1)} \end{pmatrix}. \end{align*} For $c = (c_0, c_1, \ldots, c_{n-1}) \in \mathbb{F}_q^n$, the $m$-th entry of $M c^\top$ is \begin{align*} (M c^\top)_m = \sum_{j=1}^{n} M_{m, j}\, c_{j - 1} = \sum_{i=0}^{n-1} c_i\, \alpha^{m i} = c(\alpha^m). \end{align*} Hence \begin{align*} c \in C \iff c(\alpha^m) = 0 \text{ for } 1 \leq m \leq \delta - 1 \iff M c^\top = 0. \end{align*} [/step] [step:Show that any $\delta - 1$ columns of $M$ are $\mathbb{F}$-linearly independent] Fix column indices $1 \leq j_1 < j_2 < \cdots < j_{\delta - 1} \leq n$. Form the $(\delta - 1) \times (\delta - 1)$ submatrix $M'$ of $M$ with these columns: \begin{align*} M'_{m, \ell} = \alpha^{m (j_\ell - 1)} \quad \text{for } 1 \leq m, \ell \leq \delta - 1. \end{align*} Set $\beta_\ell := \alpha^{j_\ell - 1}$ for $1 \leq \ell \leq \delta - 1$. Then $M'_{m, \ell} = \beta_\ell^{m}$, so \begin{align*} M' = \begin{pmatrix} \beta_1 & \beta_2 & \cdots & \beta_{\delta - 1} \\ \beta_1^2 & \beta_2^2 & \cdots & \beta_{\delta - 1}^2 \\ \vdots & \vdots & & \vdots \\ \beta_1^{\delta - 1} & \beta_2^{\delta - 1} & \cdots & \beta_{\delta - 1}^{\delta - 1} \end{pmatrix}. \end{align*} Factor $\beta_\ell$ out of column $\ell$ for each $\ell$: \begin{align*} \det(M') = \left( \prod_{\ell=1}^{\delta - 1} \beta_\ell \right) \cdot \det\!\begin{pmatrix} 1 & 1 & \cdots & 1 \\ \beta_1 & \beta_2 & \cdots & \beta_{\delta - 1} \\ \vdots & \vdots & & \vdots \\ \beta_1^{\delta - 2} & \beta_2^{\delta - 2} & \cdots & \beta_{\delta - 1}^{\delta - 2} \end{pmatrix}. \end{align*} The second determinant is the standard [Vandermonde determinant](/theorems/???) at nodes $\beta_1, \ldots, \beta_{\delta - 1}$, which equals $\prod_{1 \leq \ell_1 < \ell_2 \leq \delta - 1} (\beta_{\ell_2} - \beta_{\ell_1})$. Hence \begin{align*} \det(M') = \left( \prod_{\ell=1}^{\delta - 1} \beta_\ell \right) \prod_{1 \leq \ell_1 < \ell_2 \leq \delta - 1} (\beta_{\ell_2} - \beta_{\ell_1}). \end{align*} Each factor is non-zero: - $\beta_\ell = \alpha^{j_\ell - 1} \neq 0$ because $\alpha$ is a root of unity, hence a unit. - $\beta_{\ell_2} - \beta_{\ell_1} \neq 0$ for $\ell_1 < \ell_2$. This uses primitivity: the distinct exponents $j_{\ell_1} - 1, j_{\ell_2} - 1 \in \{0, 1, \ldots, n - 1\}$ satisfy $0 \leq |(j_{\ell_2} - 1) - (j_{\ell_1} - 1)| = j_{\ell_2} - j_{\ell_1} < n$. The multiplicative order of $\alpha$ is exactly $n$ (definition of "primitive $n$-th root of unity"), so $\alpha^d \neq 1$ for any $1 \leq d < n$. Taking $d = j_{\ell_2} - j_{\ell_1} \in \{1, \ldots, n - 1\}$ gives $\alpha^{j_{\ell_2} - j_{\ell_1}} \neq 1$, equivalently $\alpha^{j_{\ell_2} - 1} \neq \alpha^{j_{\ell_1} - 1}$, i.e., $\beta_{\ell_2} \neq \beta_{\ell_1}$. Since every factor is non-zero, $\det(M') \neq 0$, so $M'$ is invertible. Therefore the columns of $M$ indexed by $j_1 < \cdots < j_{\delta - 1}$ are $\mathbb{F}$-linearly independent. [guided] We want to show that any $\delta - 1$ columns of the matrix $M$ are linearly independent. The structure $M_{m, j} = \alpha^{m(j-1)}$ makes each column a geometric progression in the exponent $m$, which is the signature of a Vandermonde matrix. Pick any columns $j_1 < j_2 < \cdots < j_{\delta - 1}$. Form the square submatrix $M'$ whose entry in row $m$ and column $\ell$ is $\alpha^{m(j_\ell - 1)} = (\alpha^{j_\ell - 1})^m$. Introducing the shorthand $\beta_\ell := \alpha^{j_\ell - 1}$, we have $M'_{m, \ell} = \beta_\ell^m$. This matrix is not quite in Vandermonde form — the standard Vandermonde has rows indexed by powers starting from $0$, not from $1$. We fix this by pulling one factor of $\beta_\ell$ out of each column $\ell$. After this factorisation, the remaining matrix has entries $\beta_\ell^{m-1}$ for $1 \leq m, \ell \leq \delta - 1$, which is the honest Vandermonde \begin{align*} \det\!\begin{pmatrix} 1 & \cdots & 1 \\ \beta_1 & \cdots & \beta_{\delta - 1} \\ \vdots & & \vdots \\ \beta_1^{\delta - 2} & \cdots & \beta_{\delta - 1}^{\delta - 2} \end{pmatrix} = \prod_{\ell_1 < \ell_2} (\beta_{\ell_2} - \beta_{\ell_1}). \end{align*} Together with the pulled-out scalar $\prod_\ell \beta_\ell$, we get $\det(M') = \big(\prod_\ell \beta_\ell\big)\!\!\prod\limits_{\ell_1 < \ell_2}\!\!(\beta_{\ell_2} - \beta_{\ell_1})$. For this to be non-zero we need two things: *(a)* Each $\beta_\ell \neq 0$. This is automatic because $\alpha$ has finite multiplicative order $n$ (it is a root of unity), so every power $\alpha^{j_\ell - 1}$ is a unit, hence non-zero. *(b)* The $\beta_\ell$ are pairwise distinct. This is **where primitivity is consumed**. A primitive $n$-th root of unity has order exactly $n$ — i.e., $\alpha^d = 1 \iff n \mid d$. The column indices satisfy $1 \leq j_1 < \cdots < j_{\delta - 1} \leq n$, so the differences $j_{\ell_2} - j_{\ell_1}$ lie in the range $\{1, 2, \ldots, n - 1\}$, never divisible by $n$. Hence $\alpha^{j_{\ell_2} - j_{\ell_1}} \neq 1$, equivalently $\beta_{\ell_2} \neq \beta_{\ell_1}$. What goes wrong without primitivity? If $\alpha$ had order $n_0 < n$, then differences in $\{n_0, 2 n_0, \ldots\}$ would give $\beta_{\ell_2} = \beta_{\ell_1}$, the Vandermonde determinant would vanish, and $\delta - 1$ columns of $M$ could be linearly dependent. The BCH bound would then fail. With both (a) and (b) in hand, $\det(M') \neq 0$, so the chosen $\delta - 1$ columns are linearly independent. [/guided] [/step] [step:Rule out non-zero codewords of weight $< \delta$] Suppose, for contradiction, there exists $c \in C$ with $c \neq 0$ and $w := \operatorname{wt}(c) < \delta$, i.e., $w \leq \delta - 1$. Let $J := \{ j \in \{1, \ldots, n\} : c_{j - 1} \neq 0 \}$ be the (1-indexed) support of $c$; then $|J| = w$. By Step 1, $M c^\top = 0$. Expanding: \begin{align*} 0 = M c^\top = \sum_{j = 1}^{n} c_{j - 1}\, M_{\cdot, j} = \sum_{j \in J} c_{j - 1}\, M_{\cdot, j}, \end{align*} where $M_{\cdot, j}$ denotes the $j$-th column of $M$. This is a non-trivial $\mathbb{F}_q$-linear dependence (with coefficients $c_{j-1} \neq 0$ for $j \in J$, by definition of $J$) among the $w \leq \delta - 1$ columns $\{ M_{\cdot, j} : j \in J \}$. In particular, embedding the relation into $\mathbb{F}$ (which contains $\mathbb{F}_q$), we have a non-trivial $\mathbb{F}$-linear dependence among $w \leq \delta - 1$ columns of $M$. Augmenting with any $\delta - 1 - w$ further columns (with coefficient zero) produces a non-trivial $\mathbb{F}$-linear dependence among $\delta - 1$ columns of $M$. This contradicts Step 2, which established that any $\delta - 1$ columns of $M$ are $\mathbb{F}$-linearly independent. Therefore no such $c$ exists, and every non-zero codeword has weight at least $\delta$. [/step] [step:Conclude the BCH bound] By Step 3, every non-zero $c \in C$ satisfies $\operatorname{wt}(c) \geq \delta$. Taking the infimum over $c \in C \setminus \{0\}$, \begin{align*} d(C) = \min\{ \operatorname{wt}(c) : c \in C \setminus \{0\} \} \geq \delta, \end{align*} completing the proof of the BCH bound. [/step]