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

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)$$

• Your question has $n$ in two roles. As a dimension of the vector space and as a length of the sequence $V$. Using $L$ for the latter. So in your example $n=3$ and $L=7$. You get such sequences wrapping around at $L=2^n-1$ by viewing those vectors as elements of $\Bbb{F}_{2^n}$ and using powers of a primitive element. – Jyrki Lahtonen Apr 22 '16 at 4:58
• @JyrkiLahtonen Whoops! Like you said I had the length of $V$ wrong. I edited to correct that – Matt Thomas Apr 22 '16 at 15:13

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).
• Unfortunately I'm kind of unskilled with Finite Fields, so is this understanding of your answer correct? $\Bbb{F}_8$ would be the extension for my example and we'll choose $x^3 + x + 1$ as its primitive polynomial, so am I right that $x$ would be a generator of its multiplicative group? Then to get another basis besides $\{1, x, x^2\} = \{(0, 0, 1), (0, 1, 0), (1, 0, 0)\}$ I could just multiply those by $x$ (modulo that polynomial) to get $\{x, x^2, x + 1\} = \{(0, 1, 0), (1, 0, 0), (0, 1, 1)\}$, or by $x^2$ to get $\{x^2, x + 1, x^2 + x\} = \{(1, 0, 0), (0, 1, 1), (1, 1, 0)\}$? – Matt Thomas Apr 22 '16 at 20:12
• You got it, @Matt. Looks correct to me. – Jyrki Lahtonen Apr 22 '16 at 20:28
• My knowledge of algebraic field extensions is quite limited -- could you provide some keywords that would allow me to read up on the basic facts that tell us that $B$ is a basis? – joriki Apr 23 '16 at 17:11