Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

Let $\mathbb F_q$ be the finite field with $q$ elements, $q=2^n$. This is a vector space over $\mathbb F_2$. My question is rather general: given two linearly independent sets of vectors of the same size, say $A=\{x_1,…,x_k\}$ and $B=\{y_1,…,y_k\}$, is it possible to say anything useful about the set $C=\{x_iy_j:1\leq i,j \leq k\}$ in terms of independence, i.e., the size of a maximal linearly independent subset?

The question is probably too vague to admit a full answer, so feel free to make any assumptions that might restrict the problem considerably. For example, what if we take $B$ to be the image of $A$ under a certain (injective) map (automorphism, permutation polynomial etc) ?

P.S. I should clarify that I'm not really asking of anyone to spend time on this. What I'm interested in is whether this problem has appeared somewhere in the existing literature in one form or another.

share|improve this question

1 Answer

up vote 3 down vote

Let $k < n/2$ and let $\alpha$ be a generator of $\mathbb F_q^\times$. Then, any $n$ consecutive powers of $\alpha$ are a basis for $\mathbb F_q$ regarded as a vector space over $\mathbb F_p$. Take $A = \{1, \alpha, \ldots, \alpha^{k-1}\}$ and $B = \{x^{-1} \colon x\in A\}$ which clearly are linearly independent. Then, $C = \{a_ib_j\}$ is a multiset containing $\{\alpha^\ell \colon -k < \ell < k\}$, a set of $2k < n$ distinct elements that are linearly independent. Note that $p$ need not be restricted to have value $2$.

But perhaps you are asking what is the minimum size of the maximal independent subset of $C$ for two arbitrarily chosen linearly independent sets $A$ and $B$ of size $k$?

Added in response to "For instance, suppose $k \leq \sqrt{n}$. Is it possible to choose $A$ and $B$ in such a way so that dim(span($C))=k^2$?"

Yes, at least in one instance. Let $q=16$, $n = 4$, and take $A = \{1,\alpha\}$ and $B = \{1,\alpha^2\}$ of cardinality $k = \sqrt{4} = {2}$. Then $C = \{1,\alpha, \alpha^2,\alpha^3\}$ is the canonical polynomial basis for $\mathbb F_{16}$ as a $4$-dimensional vector space over $\mathbb F_2$.

share|improve this answer
I'm interested in both a lower and an upper bound for $dim(spanC)$. For instance, suppose $k<\sqrt{n}$. Is it possible to choose $A$ and $B$ in such a way so that $dim(spanC)=k^2$? – Stefanos Jan 11 at 20:36
To be more precise, I am interested in determining the exact range of values of $dim(spanC)$ and possibly to be able to count the number of subspaces for which each value occurs. – Stefanos Jan 11 at 20:42
1  
@Stefanos: If $k\mid n$, then the minimum of $\dim (\langle C\rangle)$ is surely equal to $k$. Obviously can't be less, and $k$ occurs, if $A$ and $B$ both span the subfield $\mathbb{F}_{2^k}$. I don't know, if the minimum is still $k$, when $k\nmid n$? Need to think about this more. Fun question! – Jyrki Lahtonen Jan 11 at 22:49
1  
And if $k\mid n$, then the maximum is $\min\{n,k^2\}$, because we can select $A$ to be a basis of the subfield $\mathbb{F}_{2^k}$, and $B$ to be a subset of the basis of the extension $\mathbb{F}_{2^n}/\mathbb{F}_{2^k}$, when $n\ge k^2$, and to contain such a basis when $n<k^2$. I have a feeling that getting to $k^2$ is easier than staying at the other extreme. – Jyrki Lahtonen Jan 11 at 22:56
What if $B$ depends on $A$? For example, suppose $B=\sigma(A)$, where $\sigma$ is a generator of the group of automorphisms of the field. – Stefanos Jan 11 at 23:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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