3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Apr 22 '16 at 4:58
  • $\begingroup$ @JyrkiLahtonen Whoops! Like you said I had the length of $V$ wrong. I edited to correct that $\endgroup$ – Matt Thomas Apr 22 '16 at 15:13
4
$\begingroup$

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).
$\endgroup$
3
  • $\begingroup$ 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)\}$? $\endgroup$ – Matt Thomas Apr 22 '16 at 20:12
  • $\begingroup$ You got it, @Matt. Looks correct to me. $\endgroup$ – Jyrki Lahtonen Apr 22 '16 at 20:28
  • $\begingroup$ 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? $\endgroup$ – joriki Apr 23 '16 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.