Show that the $n+1$ elementary codewords (of length $2^{n}$ ) are linearly independent (Reed-Muller Codes)

Question

The problem below is based on the Coding Theory, specifically on Reed-Muller codes (RM codes). These are linear codes whose codewords have size $2^{n}$ for some $n \in \mathbb{Z}^{+}$. Here the alphabet is $\{0,1\},$ so the field is $\mathbb{Z}_{2}$ and all arithmetic is done modulo $2$.

The $2^{n}$ -bit RM code is defined as the code space spanned by the $n+1$ elementary codewords. These elementary codewords have a specific pattern explained below with examples. For $n=2,3$ and $4$ these are (written as column vectors):

$n=2 \quad\left[\begin{array}{lll} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array}\right],$ $n=3\left[\begin{array}{llll} 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{array}\right],$ $n=4\left[\begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{array}\right].$

I want to show that the $n+1$ elementary codewords (of length $2^{n}$ ) are linearly independent.

We see that for $n=2$ these vectors $(1,1,1,1), (0,0,1,1)$ and $(0,1,0,1)$ are linearly independent, and we can check easily for $n=3,4$ etc. but how can I show $n+1$ elementary codewords (of length $2^{n}$ ) are linearly independent, can you help, can you add an answer?

Note: I don't know any knowledge about Coding Theory, I'm focused these matrices.

My attempt.

Let $$A=\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 m} \\ a_{21} & a_{22} & \cdots & a_{2 m} \\ \vdots & \vdots & & \vdots \\ a_{n 1} & a_{n 2} & \cdots & a_{n m} \end{array}\right]_{n \times m}$$ be matrix representation of the $n+1$ elementary codewords (of length $2^{n}$ ). Let $v_1,v_2,...,v_n$ be column vectors of $A.$

Let $\alpha_1,...,\alpha_n$ be scalars. Assume $\alpha_1 v_1+...+\alpha_n v_n=0.$ I need to show $\alpha_1=...\alpha_n=0.$

Now, look $1th$ row: since only $a_{11}=1$ and others are zero then we get $\alpha_1=0.$

Look $2th$ row: only $a_{21}=1$ and $a_{2m-1}=1$, others are zero. Hence, $\alpha_{n-1}=0$ Can I continue in this way?

Answer 1

Hint: show that the row space of each matrix spans $\mathbb{Z}_2^{n+1}$, and therefore the row rank is $n+1$. This implies the same for the column rank.

Answer 2

A commonly used convention in coding theory is that codewords are row vectors and the generator matrix of a $[n,k]$ code is a $k\times n$ matrix whose rows are linearly independent vectors. The code is a $k$-dimensional subspace of the $n$-dimensional space and the $k$ rows of the generator matrix are a basis for this subspace. You are taking codewords as column vectors, but no matter; just tilt your head sideways and you will be able to follow along.

The code you are looking at is called a first-order Reed-Muller code and it is a $[2^n,n+1]$ code. Its codewords can be represented as the truth tables of the $2^{n+1}$ linear functions (actually, affine functions) of $n$ binary variables $x_1, x_2, \ldots, x_n$. That is, the codewords correspond to the $2^{n+1}$ Boolean functions $$f(a_0, a_1, a_2, \ldots, a_n) = a_0 \oplus a_1x_1 \oplus a_2x_2 \oplus \cdots \oplus a_nx_n, ~~a_i \in \{0, 1\}, 0 \leq i \leq n.$$ Notice that your matrices are just the truth tables for the functions $f(1, 0,\ldots, 0) = 1$, $f(0,1, 0,\ldots, 0) = x_1$, $f(0, 0,1, 0,\ldots, 0)=x_2, \cdots$, $f(0,0, \ldots, 0, 1) = x_n$, and these functions are linearly independent: $$a_0 \oplus a_1x_1 \oplus a_2x_2 \oplus \cdots \oplus a_nx_n \neq 0 ~\text{if at least one } a_i ~\text{is nonzero}.$$