Subsequences of length $n$ always making a basis for $\mathbb{F}^n_2$?

Question

Is it always possible to order every vector of $\mathbb{F}^n_2$ (except the zero vector) as a sequence $V = (v_1, \dots, v_{2^n - 1}) | v_i \in \mathbb{F}^n_2 \setminus \{0\} $ such that every subsequence of $V$ of length $n$ is a basis of $\mathbb{F}^n_2$? Furthermore, is it always possible to apply this rule (subsequences of length $n$ make a basis for $\mathbb{F}^n_2$) to concatenations of such a sequence (so that the rule "wraps around")?

If so, what's a good way to construct such a sequence for a given $n$?

Here's such an example sequence for $\mathbb{F}^3_2$ that can also "wrap around": $$v_1 = (0, 0, 1)$$ $$v_2 = (0, 1, 0)$$ $$v_3 = (1, 0, 0)$$ $$v_4 = (0, 1, 1)$$ $$v_5 = (1, 1, 0)$$ $$v_6 = (1, 1, 1)$$ $$v_7 = (1, 0, 1)$$

Answer 1

We can identify the extension field $\Bbb{F}_{2^n}$ with the vector space $\Bbb{F}_2^n$ by selecting a basis (over $\Bbb{F}_2$) for the former.

After that the following trick stands out. Let $\gamma$ be a generator of the multiplicative group $\Bbb{F}_{2^n}^*$. Because $\Bbb{F}_{2^n}=\Bbb{F}_2(\gamma)$ basic facts about algebraic field extensions tell us that $B=\{1,\gamma,\gamma^2,\ldots,\gamma^{n-1}\}$ is a basis and, therefore, a linearly independent set of vectors in $\Bbb{F}_2^n$. But, multiplication by a non-zero element of $\Bbb{F}_2^n$ is an invertible linear transformation. Consequently $\gamma^jB=\{\gamma^j,\gamma^{j+1},\ldots,\gamma^{j+n-1}\}$ is linearly independent for all integers $j$.

All this implies that the sequence $v_j=\gamma^{j-1}$ works as prescribed. Because $\gamma^{2^n-1}=1$ (and this is also the order of $\gamma$), the sequences also wraps around as prescribed.

A couple of remarks

• You can vary the order the vectors appear in by using another generator in place of $\gamma$. Any $\gamma^k$ with $\gcd(k,2^n-1)=1$ will do just as well.
• This is exploited in linear feedback shift registers. When a minimal polynomial of an element like $\gamma$ is used as a feedback polynomial, the contents of the $n$-bit register of bits will cycle through all the non-zero vectors (given any non-zero initial state).