[proofplan] A parity-check matrix of an $(n, k)$-linear code $C$ is, by definition, a generator matrix of the dual code $C^\perp$, which has dimension $n - k$. We prove the claim in two stages. First, we show that every row of the candidate matrix $H = (B^\top \mid I_{n-k})$ is orthogonal to every row of $G$, which means the rowspace of $H$ sits inside $C^\perp$. Second, we observe that $H$ has rank $n - k$ because its right-hand block is the identity, so its rowspace already has the full dimension of $C^\perp$, forcing equality. [/proofplan] [step:Record the matrix shapes and set up the orthogonality test] We work over the field $\mathbb{F}_2$, in which $1 + 1 = 0$ and every element equals its own additive inverse. The generator matrix $G = (I_k \mid B)$ has $k$ rows in $\mathbb{F}_2^n$; by definition of a generator matrix, $C$ is the row-space of $G$. A vector $u \in \mathbb{F}_2^n$ lies in $C^\perp$ if and only if $u \cdot c = 0$ for every $c \in C$, equivalently $G u^\top = 0 \in \mathbb{F}_2^k$. Therefore, to show that every row of $H = (B^\top \mid I_{n-k})$ lies in $C^\perp$, it suffices to establish the matrix identity \begin{align*} G H^\top = 0 \in \mathbb{F}_2^{k \times (n-k)}, \end{align*} because the $(i, j)$-entry of $G H^\top$ is exactly $g_i \cdot h_j$, where $g_i$ is the $i$-th row of $G$ and $h_j$ is the $j$-th row of $H$. [/step] [step:Compute $G H^\top$ directly in block form] The transpose of $H = (B^\top \mid I_{n-k})$ is the block column matrix \begin{align*} H^\top = \begin{pmatrix} (B^\top)^\top \\ I_{n-k}^\top \end{pmatrix} = \begin{pmatrix} B \\ I_{n-k} \end{pmatrix} \in \mathbb{F}_2^{n \times (n-k)}, \end{align*} where the top block $B$ has size $k \times (n-k)$ and the bottom block $I_{n-k}$ has size $(n-k) \times (n-k)$. The block-matrix product of $G = (I_k \mid B)$ with $H^\top$ is \begin{align*} G H^\top = (I_k \mid B) \begin{pmatrix} B \\ I_{n-k} \end{pmatrix} = I_k \cdot B + B \cdot I_{n-k} = B + B. \end{align*} Since we are working in $\mathbb{F}_2$, we have $B + B = 2B = 0$, so \begin{align*} G H^\top = 0 \in \mathbb{F}_2^{k \times (n-k)}. \end{align*} [guided] We aim to verify that each row of $H$ is orthogonal to each row of $G$. The cleanest way is to compute the matrix product $G H^\top$ in one go, because its $(i, j)$-entry is exactly the inner product of the $i$-th row of $G$ with the $j$-th row of $H$. Start by transposing $H$. Recall that transposing a block row produces a block column, and transposing each block inside gives \begin{align*} H^\top = \begin{pmatrix} B^\top \\ I_{n-k} \end{pmatrix}^{\!\top-\text{as-rows}} = \begin{pmatrix} B \\ I_{n-k} \end{pmatrix} \in \mathbb{F}_2^{n \times (n-k)}, \end{align*} using $(B^\top)^\top = B$ and $I_{n-k}^\top = I_{n-k}$. The block $B$ on top has $k$ rows — exactly the number of columns of $I_k$ — and the block $I_{n-k}$ on the bottom has $n - k$ rows — exactly the number of columns of $B$. So the block sizes line up for multiplication by $G = (I_k \mid B)$. Now multiply. The block rule reads: left factor split as $(A_1 \mid A_2)$, right factor split as $\begin{pmatrix} R_1 \\ R_2 \end{pmatrix}$, yields $A_1 R_1 + A_2 R_2$. Substituting: \begin{align*} G H^\top &= I_k \cdot B + B \cdot I_{n-k} = B + B. \end{align*} This is where the characteristic of the field matters. In $\mathbb{F}_2$ every element is its own additive inverse, so $B + B = 0$. Hence \begin{align*} G H^\top = 0. \end{align*} What would go wrong over a different field? Over $\mathbb{F}_p$ for $p \neq 2$, the expression $B + B = 2B$ is not zero, so the correct parity-check partner of $(I_k \mid B)$ would be $(-B^\top \mid I_{n-k})$. The binary setting hides this sign. [/guided] [/step] [step:Conclude that the rows of $H$ lie in $C^\perp$] The identity $G H^\top = 0$ means that for each row $h_j$ of $H$ and each row $g_i$ of $G$, \begin{align*} g_i \cdot h_j = 0. \end{align*} Since every codeword $c \in C$ is an $\mathbb{F}_2$-linear combination of the rows $g_1, \dots, g_k$ and the dot product is bilinear, this gives $c \cdot h_j = 0$ for all $c \in C$. Thus $h_j \in C^\perp$ for each $j \in \{1, \dots, n-k\}$. Consequently the rowspace of $H$ is a subspace of $C^\perp$: \begin{align*} \operatorname{rowspan}(H) \subseteq C^\perp. \end{align*} [/step] [step:Show $H$ has rank $n - k$ and conclude equality of rowspans] The matrix $H = (B^\top \mid I_{n-k})$ contains the block $I_{n-k}$ in its last $n - k$ columns. Restricting attention to those columns, the submatrix formed by the last $n - k$ columns of $H$ is exactly $I_{n-k}$, which has rank $n - k$. Rank cannot increase when columns are removed, and it cannot exceed the number of rows of $H$, which is also $n - k$. Therefore \begin{align*} \operatorname{rank}(H) = n - k. \end{align*} By the dimension formula for linear codes, since $\dim C = k$, we have $\dim C^\perp = n - k$. Combining this with the previous step: \begin{align*} \dim \operatorname{rowspan}(H) = \operatorname{rank}(H) = n - k = \dim C^\perp, \qquad \operatorname{rowspan}(H) \subseteq C^\perp. \end{align*} A subspace of dimension equal to the ambient space must equal the ambient space, so $\operatorname{rowspan}(H) = C^\perp$. [guided] Two linear-algebra facts do the work here. The first is that $H$ has full row rank because its right block is the identity $I_{n-k}$: for any nonzero linear combination $\sum_j \lambda_j h_j$ of the rows of $H$, looking only at coordinates $k+1, \dots, n$ gives $\sum_j \lambda_j e_j = (\lambda_1, \dots, \lambda_{n-k}) \neq 0$, where $e_j$ is the $j$-th standard basis vector. So the rows of $H$ are linearly independent, and $\operatorname{rank}(H) = n - k$. The second fact is the dimension formula for the dual code: $\dim C + \dim C^\perp = n$. Since $\dim C = k$ (because $G$ has $k$ linearly independent rows — indeed, the left block $I_k$ already proves this), we get $\dim C^\perp = n - k$. Putting these together: $\operatorname{rowspan}(H)$ is a subspace of $C^\perp$ (from the previous step) of dimension exactly $\dim C^\perp$. A subspace whose dimension matches the ambient space must coincide with it. Hence \begin{align*} \operatorname{rowspan}(H) = C^\perp, \end{align*} which is precisely the statement that $H$ is a generator matrix of $C^\perp$ — that is, a parity-check matrix of $C$. [/guided] [/step] [step:Assemble the conclusion] The previous steps show that $\operatorname{rowspan}(H) = C^\perp$, which is by definition the statement that $H$ is a parity-check matrix of $C$. This completes the proof of the formula $H = (B^\top \mid I_{n-k})$. [/step]