Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose $X\subset \mathrm{GL}_n(p)$ is a set of invertible matrices such that for every $A,B\in X$ then also $A-B\in \mathrm{GL}_n(p)\cup \{0\}$. (If anyone knows a name for such sets I would be grateful).

I was trying to figure out what is the size of the largest such $X$. Since $\mathbb{F}_{p^n}$ can be embedded in $\mathrm{GL}_n(p)\cup \{0\}$ then obviously the size is at least $p^n-1$.

My interest in this question was motivated from a computer science question (ideal secret sharing schemes), and from there it appears that $p^n-1$ must also be the upper bound.

I was wondering if anyone knows a more direct way of showing that this holds (something more algebraic or direct combinatorial arguments).

share|improve this question
add comment

1 Answer

up vote 13 down vote accepted

The upper bound can be obtained as follows: Fix a nonzero vector $v$ from $\mathbb F_p^n$. Then the vectors $Bv$ for $B\in X$ are pairwise distinct and nonzero, for if $Bv=B'v$, then $B-B'$ is not invertible. Thus the map $X\to\mathbb F_p^n\setminus\{0\}$, $B\mapsto Bv$ is injective, hence $\lvert X\rvert\leq p^n-1$.

Your sets with $\lvert X\rvert=p^n-1$ do have a name, they are called spreadsets and they are closely related to finite translation planes. See here.

share|improve this answer
add comment

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.