MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.