7
$\begingroup$

$\DeclareMathOperator\GL{GL}$A few months ago, the following discussion took place on AoPS, concerning matrices that have nonzero determinant under any permutation of their entries: https://artofproblemsolving.com/community/c7h3116517.

This inspired me to ask the following question:

For a prime $p$ and a positive integer $n$, let $\mathcal{P}_n(\mathbb{F}_p)$ be the set of matrices $M\in \GL_n(\mathbb{F}_p)$ such that any matrix $M’$ formed by a permutation of the entries in $M$ has nonzero determinant. For which $(n,p)$ is $\mathcal{P}_n(\mathbb{F}_p)$ nonempty? Can we determine the size of $\mathcal{P}_n(\mathbb{F}_p)$ for these pairs?

We may be able to roughly estimate what the size of the set should look like by just comparing the size of $\GL_n(\mathbb{F}_p)$ to the number of distinct permutations of entries that such a matrix has, on average. I would love to see if you all have any ideas for this problem.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ We have $n^2$ elements to divide among $p$ residues, so there must be a multiset of at least $n^2 - p$ elements which can be partitioned into two equal multisets. If $n^2 - p \ge 2n$ then this means there must be a permutation with two equal rows, hence singular; so necessarily $n(n-2) < p$. $\endgroup$
    – Peter Taylor
    Commented Nov 28, 2023 at 8:41
  • 1
    $\begingroup$ It is also clear that, if $n$ is fixed, then solutions exist for $p$ sufficiently large: The linked thread constructs examples of $n \times n$ integer matrices with that property; reduce them modulo any sufficiently large prime. $\endgroup$
    – David E Speyer
    Commented Nov 28, 2023 at 16:14

2 Answers 2

Reset to default
5
$\begingroup$

$\det \begin{pmatrix} 1 \end{pmatrix} = 1$ works for any $p$.

$\det \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = -1$ similarly.

For $n=3$ we require $p \ge 5$. By exhaustion there's no solution for $p=5$ or $p=7$. There aren't many for $p=11$, but e.g. the multiset $\{\{1, 2^5, 3, 4, 8\}\}$ works for all primes not in $\{2,3,5,7,13,17\}$. For $p > 11$ the multiset $\{\{0, 1, 2^5, 3, 5\}\}$ is good: it has determinants $\{\pm 1, \pm 2, \pm 4, \pm 6, \pm 7, \pm 8, \pm 9, \pm 10, \pm 12, \pm 14, \pm 16, \pm 18, \pm 20, \pm 22, \pm 24 \}$.

For $n=4$ direct calculation is already struggling due to combinatorial explosion.

Improve this answer
$\endgroup$
5
$\begingroup$

Let's try an easy case: $n=2$. If the matrix has entries $a,b,c,d$ we need $ab - cd$, $ac-bd$ and $ad-bc$ to all be nonzero. In particular if $b,c,d$ are all nonzero there are at most $3$ forbidden values for $a$. Thus the number of such $M$ is at least $(p-1)^3(p-3)$.

[EDIT] In fact, the number of such $M$ is $p^4 - 3 p^3 + 9 p^2 - 17 p + 10$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. I’m not sure if there’s a nice closed form for the actual number of $M$ for $n=2$, for $p=2,3,5,7,\ldots$ there are $4,41,447,1963,\ldots$ such $M$. OEIS doesn’t have anything. $\endgroup$
    – TheBestMagician
    Commented Nov 28, 2023 at 17:25
  • $\begingroup$ Note: you're adressing the refined question "determine the size". (For $n=2$ the existence question is clear: $(1,1,1,0)$ works regardless of the field.) $\endgroup$
    – YCor
    Commented Nov 29, 2023 at 17:11
  • $\begingroup$ I think your counts for $p=3, 5$ and $7$ are wrong. I get $4, 40, 400, 1704$ for $p = 2,3,5,7$. For example with $p=3$ the possible $M$ are $[0, 1, 1, 1], [0, 1, 1, 2], [0, 1, 2, 2], [0, 2, 2, 2], [1, 1, 1, 2], [1, 2, 2, 2]$ and their permutations. How do you get $41$? $\endgroup$
    – Robert Israel
    Commented Dec 1, 2023 at 15:51
  • $\begingroup$ Still not in OEIS though. Would you like to contribute it? If not, I can do it. $\endgroup$
    – Robert Israel
    Commented Dec 1, 2023 at 16:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .