[proofplan] Let $G \in \mathbb{F}_2^{(n-k) \times n}$ be the generator matrix whose rows are the coefficient vectors of $g(X), X g(X), \ldots, X^{n-k-1} g(X)$ — a basis for $C$ by the theorem "Basis from Generator Polynomial". We prove two facts: (i) $G H^\top = 0$, which forces every codeword to lie in the kernel of $H$; and (ii) $\operatorname{rank}(H) = k$, which forces $\ker(H) \subseteq \mathbb{F}_2^n$ to have dimension exactly $n - k = \dim C$. Combining (i) and (ii) gives $C = \ker(H)$. Fact (i) is a coefficient-chasing computation: the $(i, j)$ entry of $GH^\top$ is a coefficient of $gh = X^n - 1$ at a power strictly between $0$ and $n$, which is zero. Fact (ii) follows from the structure of $H$: the non-zero leading coefficient $b_{n-k}$ produces a staircase of pivots. [/proofplan] [step:Set up the generator matrix $G$ of $C$] By the theorem "Basis from Generator Polynomial", the polynomials $g(X), X g(X), \ldots, X^{n - k - 1} g(X)$ form an $\mathbb{F}_2$-basis of $C$. Let $g(X) = a_0 + a_1 X + \cdots + a_k X^k$ with $a_k = 1$ (since $g$ is monic), and adopt the convention $a_\ell := 0$ for $\ell \notin \{0, \ldots, k\}$. For $0 \leq i \leq n - k - 1$, the polynomial $X^i g(X)$ has degree $i + k \leq n - 1 < n$, so it is its own reduction modulo $X^n - 1$, and its coefficient vector in $\mathbb{F}_2^n$ is \begin{align*} (\underbrace{0, \ldots, 0}_{i \text{ zeros}},\ a_0, a_1, \ldots, a_k,\ \underbrace{0, \ldots, 0}_{n - k - 1 - i \text{ zeros}}). \end{align*} Let $G \in \mathbb{F}_2^{(n-k) \times n}$ be the matrix whose $(i+1)$-th row (for $0 \leq i \leq n - k - 1$) is this vector. Concretely, \begin{align*} G_{i, j} = a_{j - i} \qquad \text{for } 1 \leq i \leq n - k,\ 1 \leq j \leq n, \end{align*} with $a_\ell = 0$ outside $\{0, \ldots, k\}$. The rows of $G$ span $C$, so $C = \{ u G : u \in \mathbb{F}_2^{n-k} \}$ and $C = \{ v \in \mathbb{F}_2^n : v^\top \in \text{row space}(G)^\top \}$. [/step] [step:Compute $GH^\top$ as coefficients of $g(X) h(X)$ and verify it vanishes] Fix $1 \leq i \leq n - k$ and $1 \leq j \leq k$. We compute the $(i, j)$ entry of $GH^\top$. Using the indexing from Step 1 and from the statement: \begin{align*} (GH^\top)_{i, j} = \sum_{\ell = 1}^{n} G_{i, \ell}\, H_{j, \ell} = \sum_{\ell = 1}^{n} a_{\ell - i}\, b_{n - k - (\ell - j)}. \end{align*} Substitute $m := \ell - i$, so $\ell = m + i$ and $m$ ranges from $1 - i$ to $n - i$: \begin{align*} (GH^\top)_{i, j} = \sum_{m = 1 - i}^{n - i} a_m\, b_{n - k - (m + i - j)} = \sum_{m = 1 - i}^{n - i} a_m\, b_{(n - k + j - i) - m}. \end{align*} Because $a_m$ is non-zero only for $m \in \{0, \ldots, k\}$ and $b_{(n - k + j - i) - m}$ is non-zero only for $(n - k + j - i) - m \in \{0, \ldots, n - k\}$, we may extend the sum over all $m \in \mathbb{Z}$ without changing its value: \begin{align*} (GH^\top)_{i, j} = \sum_{m \in \mathbb{Z}} a_m\, b_{(n - k + j - i) - m}. \end{align*} This is precisely the coefficient of $X^{n - k + j - i}$ in the polynomial product \begin{align*} g(X) h(X) = \left( \sum_m a_m X^m \right) \left( \sum_s b_s X^s \right) = \sum_{N \in \mathbb{Z}} \left( \sum_m a_m b_{N - m} \right) X^N, \end{align*} evaluated at $N = n - k + j - i$. By definition of the parity check polynomial, $g(X) h(X) = X^n - 1$ in $\mathbb{F}_2[X]$, whose non-zero coefficients occur only at exponents $0$ (coefficient $-1 = 1$ in $\mathbb{F}_2$) and $n$ (coefficient $1$). The exponent of interest is $N = n - k + j - i$. Since $1 \leq i \leq n - k$ and $1 \leq j \leq k$, \begin{align*} N &= n - k + j - i \geq n - k + 1 - (n - k) = 1 > 0, \\ N &= n - k + j - i \leq n - k + k - 1 = n - 1 < n. \end{align*} Hence $0 < N < n$, so the coefficient of $X^N$ in $X^n - 1$ is $0$. Therefore $(GH^\top)_{i, j} = 0$ for all valid $i, j$, giving \begin{align*} G H^\top = 0 \in \mathbb{F}_2^{(n-k) \times k}. \end{align*} [guided] The trick is to recognise $(GH^\top)_{i, j}$ as a convolution — exactly the kind of sum that appears when you multiply two polynomials. Each row of $G$ is a shifted copy of the coefficient vector of $g$, and each row of $H$ is a reversed-and-shifted copy of the coefficient vector of $h$. When we multiply $G$ by $H^\top$, the inner products pick up exactly the coefficients of $g(X) h(X)$. Let us carry this out carefully. From Step 1, $G_{i, \ell} = a_{\ell - i}$ (row $i$ of $G$ is the coefficient vector of $X^{i-1} g(X)$, shifted right by $i - 1$ from position $1$). From the statement, $H_{j, \ell} = b_{n - k - (\ell - j)}$ (row $j$ of $H$ starts with $b_{n-k}$ at column $j$ and runs down to $b_0$ — i.e., $h$'s coefficients in **reversed** order, shifted right by $j - 1$). So \begin{align*} (GH^\top)_{i, j} = \sum_{\ell = 1}^{n} a_{\ell - i}\, b_{n - k - \ell + j}. \end{align*} Set $m = \ell - i$: \begin{align*} (GH^\top)_{i, j} = \sum_{m} a_m\, b_{(n - k + j - i) - m}, \end{align*} where the sum extends over all integers (non-zero contributions come only from $m \in \{0, \ldots, k\}$ with $(n - k + j - i) - m \in \{0, \ldots, n - k\}$). This is the coefficient of $X^N$ in $g(X) h(X)$ where $N = n - k + j - i$. Why? Because polynomial multiplication is defined exactly this way: $[X^N](gh) = \sum_m a_m\, b_{N - m}$. Now we exploit the defining identity $g(X) h(X) = X^n - 1$. The right-hand side has only two non-zero coefficients: at $X^0$ (which is $-1 = 1$ in $\mathbb{F}_2$) and at $X^n$ (which is $1$). We need to check that $N = n - k + j - i$ never equals $0$ or $n$ for the indices $(i, j)$ in play. The index constraints are $1 \leq i \leq n - k$ and $1 \leq j \leq k$. So: \begin{align*} N_{\min} = n - k + 1 - (n - k) = 1, \qquad N_{\max} = n - k + k - 1 = n - 1. \end{align*} Thus $1 \leq N \leq n - 1$, safely avoiding both $N = 0$ and $N = n$. The coefficient of $X^N$ in $X^n - 1$ is $0$, hence $(GH^\top)_{i, j} = 0$. All entries of $GH^\top$ vanish; $GH^\top = 0$. The choice of index ranges for $H$ in the statement — namely $1 \leq i \leq k$ rows and $1 \leq j \leq n$ columns — is precisely calibrated so that the exponent $n - k + j - i$ dodges the two "bad" values $0$ and $n$. This is the coding-theory reason the matrix $H$ is given in this particular shape. [/guided] [/step] [step:Show that every codeword lies in the kernel of $H$] Let $v \in C$. Since the rows of $G$ span $C$, there exists $u \in \mathbb{F}_2^{n - k}$ such that $v = u G$, i.e., $v^\top = G^\top u^\top$. Then \begin{align*} H v^\top = H G^\top u^\top = (G H^\top)^\top u^\top = 0, \end{align*} using $GH^\top = 0$ from Step 2 and the identity $H G^\top = (GH^\top)^\top$ (transpose of a product). Therefore $C \subseteq \ker(H)$, where $\ker(H) := \{ v \in \mathbb{F}_2^n : H v^\top = 0 \}$. [/step] [step:Compute $\operatorname{rank}(H) = k$ and conclude $\dim \ker(H) = n - k$] We show the $k$ rows of $H$ are linearly independent over $\mathbb{F}_2$. First, $b_{n - k} \neq 0$. Reason: $h$ satisfies $g(X) h(X) = X^n - 1$, so comparing leading terms, the leading coefficient of $h$ is the leading coefficient of $X^n - 1$ divided by the leading coefficient of $g$, both of which equal $1$. So $b_{n-k} = 1 \neq 0$. Now suppose $\mu_1, \ldots, \mu_k \in \mathbb{F}_2$ satisfy $\sum_{i=1}^k \mu_i H_{i, \cdot} = 0 \in \mathbb{F}_2^n$, i.e., for every $1 \leq j \leq n$, \begin{align*} \sum_{i=1}^{k} \mu_i\, b_{n - k - (j - i)} = 0. \end{align*} Specialise to $j = 1$: the only index $i \in \{1, \ldots, k\}$ for which $n - k - (1 - i) = n - k - 1 + i \in \{0, \ldots, n - k\}$ with $b_{\cdot} = b_{n-k}$ (the leading coefficient) occurs when $n - k - 1 + i = n - k$, i.e., $i = 1$. For $i > 1$ we have $n - k - 1 + i > n - k$, so $b_{n - k - 1 + i} = 0$ by the convention in the statement. Thus \begin{align*} 0 = \sum_{i=1}^{k} \mu_i\, b_{n - k - 1 + i} = \mu_1\, b_{n - k} = \mu_1, \end{align*} so $\mu_1 = 0$. Next specialise to $j = 2$: after using $\mu_1 = 0$, the same analysis yields $\mu_2 b_{n-k} = 0$, so $\mu_2 = 0$. Iterating through $j = 3, 4, \ldots, k$, we obtain $\mu_i = 0$ for all $1 \leq i \leq k$. Hence the rows of $H$ are linearly independent, and \begin{align*} \operatorname{rank}(H) = k. \end{align*} By the rank-nullity theorem applied to the map $v \mapsto Hv^\top$ from $\mathbb{F}_2^n$ to $\mathbb{F}_2^k$, \begin{align*} \dim_{\mathbb{F}_2} \ker(H) = n - \operatorname{rank}(H) = n - k. \end{align*} [/step] [step:Conclude $C = \ker(H)$] From Step 3, $C \subseteq \ker(H)$. From the theorem "Basis from Generator Polynomial", $\dim_{\mathbb{F}_2} C = n - k$. From Step 4, $\dim_{\mathbb{F}_2} \ker(H) = n - k$. A subspace of a vector space with the same dimension as the ambient space is the whole space, so \begin{align*} C = \ker(H) = \{ v \in \mathbb{F}_2^n : H v^\top = 0 \}. \end{align*} This is exactly the statement that $H$ is a parity check matrix of $C$, completing the proof. [/step]