How many elements of $\mathrm{SL}_n(\mathbb{F}_p)$ have all nonzero entries? Just the answer mod $p$ would be fine as well. This seems like it should be easy/in the literature but I couldn't find it.

  • 4
    A little remark is that the number of such matrices is an integer multiple of $(p-1)^{n-1}.$ The group $T$ of invertible diagonal matrices acts on such matrices by conjugation and only scalar matrices fix anything in the action. – Geoff Robinson Dec 25 '14 at 3:14
  • 1
    In the spirit of Geoff's comment, the count is $1/(p-1)$ times the count for ${\rm{GL}}_n$. We know the number matrices with all coordinates nonzero, so it is the same to study the space of matrices where the determinant vanishes, say avoiding the zero matrix. That reduces to the analogue (mod-$p$ count of points with all coordinates nonzero) for the hypersurface of degree $n^2$ in $\mathbf{P}^{n^2-1}$ defined by vanishing of det. Section 4 in Expose XXII in SGA7 is all about that kind of question for general projective hypersurfaces, so ask Nick Katz about this when you next see him. – user74230 Dec 25 '14 at 6:50
  • Indeed, I should have written more, but it suffices to count points mod $p$ (or even over $\mathbb{F}_{p^e}$ for large $e$ if that's easier) on the hypersurface defined by $\prod_{i,j=1}^n a_{i,j} \det(A)$ in $\mathbb{P}^{n^2-1}$. I know essentially nothing about this --- the little I know would just give me an asymptotic as $n\to \infty$, which says nothing about the answer mod $p$. Feel free to take $p$ very large, by the way --- I'm mainly wondering if e.g. there are infinitely many $p$ for which the count is nonzero mod $p$! – alpoge Dec 25 '14 at 11:18
  • 2
    Not relevant to your question, but Exercise 1.182 of Enumerative Combinatorics, vol. 1, 2nd ed., shows that if $f(n,q)$ is the number of matrices in $\mathrm{GL}(n,q)$ with no 0 entries, and $g(n,q)$ is the number of matrices in $\mathrm{GL}(n-1,q)$ with no entry equal to 1, then $f(n,q)=(q-1)^{2n-1}g(n,q)$. A reference for counting matrices in $\mathrm{GL}(n,q)$ with specified entries equal to 0 (though it doesn't seem useful for your question) is arXiv:1011.4539. – Richard Stanley Dec 25 '14 at 15:01
  • (Quick typo correction: the $n\to\infty$ in my comment should be $e\to\infty$.) – alpoge Dec 25 '14 at 20:08
up vote 33 down vote accepted

Mod $p$ it's $(-1)^{n+1} n!$.

Let's compute the number of points with determinant $1$ and all entries nonzero by inclusion-exclusion, modulo $p$. For each set of entries, we get a term for matrices in $SL _n$ with those entries $0$. This is an affine hypersurface of degree $n$ in some affine space. By Warning's theorem the number of points is a multiple of $p$ unless the number of variables is at most $n$. But the number of variables is the number of nonzero entries. A matrix with $\leq n$ nonzero entries that is invertible is a permutation matrix times a diagonal matrix. We can easily count the contribution if these. It is $(-1)^{n^2-n} (p-1)^{n-1} n!$. Mod $p$ we get the stated claim.

  • Nice; this should let you even get the count mod $p^e$ for at least the first few $e>1$. – Noam D. Elkies Dec 26 '14 at 2:25
  • 2
    Yes!! Nice argument! Just a quick typo: it should be Warning. But anyway that settles it for me. Thanks! – alpoge Dec 26 '14 at 7:34
  • 2
    Ah, that explains it: I didn't think Waring did this too. But as I understand it the case of a single hypersurface is due to Chevalley (and a complete intersection is Chevalley-Warning). Also, the residue mod $p^e$ won't be as straightforward as I imagined because you need $en+1$ variables, not $n+e$, to get a congruence mod $p^e$; but maybe $e=2$ is still tractable. – Noam D. Elkies Dec 26 '14 at 18:29

I will sharpen my earlier comment a little. The number of such matrices is divisible by $(p-1)^{2n-2}$ (though it may be zero). Let $T$ be the group of invertible diagonal matrices, and let $\mathcal{M}$ denote the set of invertible matrices of full rank ( though not necessarily determinant 1). Then $M \to TMU^{-1}$ defines an action of $T \times T$ on $\mathcal{M},$ and the only pairs $(T,U)$ which fix any element are those with $T = U$ both scalar. Hence $(T \times T)/{\rm diag} (S)$ acts semi-regularly on $\mathcal{M},$ where $S$ is the subgroup of $T$ consisting of scalars. Thus $|\mathcal{M}|$ is divisible by $(p-1)^{2n-1}$, and hence, as user74230 notes in comments, the number of matrices in $\mathcal{M}$ which have determinant $1$ is a multiple of $(p-1)^{2n-2}.$ Also, the number of such matrices is divisible by $\frac{n!}{2},$ since $A_{n}$ acts by right multiplication (in its representation by permutation matrices) on such matrices, and no non-identity element has any fixed point.

Actually, I realise that this implies that when $n \geq p,$ the number of such matrices is divisible by $p.$ For when $p =2$ the number is zero, and when $p$ is odd and $n \geq p,$ then $|A_{n}|$ is divisible by $p^{\frac{n - \sigma_{p}(n)}{p-1}}$, where $\sigma_{p}(n)$ is the sum of the digits in the base $p$ expansion of $n.$

Here's another argument obtaining the mod $p$ count. It's enough to do for $p$ odd. The desired count is $\sum_{A\in \mathrm{SL}_n(\mathbb{F}_p)} \prod_{i,j=1}^n A_{ij}^{p-1}\cdot \det(A)^{p-1}$. Changing "$\mathrm{SL}$" to "$\mathrm{GL}$" (even to all $n\times n$ matrices) changes the sum by a factor of $-1$. So it suffices to calculate $\sum_{A_{ij}\in \mathbb{F}_p} \prod_{i,j=1}^n A_{ij}^{p-1}\cdot \det(A)^{p-1}$.

Now, for $e_{ij}\geq 0$, $\sum_{A_{ij}\in \mathbb{F}_p} \prod_{i,j=1}^n A_{ij}^{e_{ij}} = 0$ unless all $e_{ij}$ are divisible by $p-1$, in which case it is $(-1)^{n^2} = (-1)^n$. Therefore the cross-terms in $\det(A)^{p-1}$ all die, and the only terms that can contribute are the $(p-1)$-st powers of terms in $\det(A)$. There are $n!$ of these, and they all carry a sign of $(\pm 1)^{p-1} = 1$. Therefore the count for $\mathrm{GL}_n$ is $(-1)^n n!$, so the count for $\mathrm{SL}_n$ is $(-1)^{n+1} n!$.

  • I suspect that this is basically the same argument that Will Sawin gave, because the Chevalley(-Warning) congruence is also proved by summing the $(p-1)$st power and expanding. – Noam D. Elkies Jan 1 '15 at 17:42
  • Yep! Indeed. It's also the reason I'd wanted the count mod $p$ in the first place, incidentally. – alpoge Jan 1 '15 at 17:48

EDIT: There's an error in this approach, it doesn't work. Computing some examples seems to show the answer is pretty complicated...

(All I have to add to what's been said is an ad-hoc argument for why this number is divisible by $p$. If you let $f(n, k)$ be the number of $n \times n$ matrices with nonzero entries having rank $k$, then you can easily write down the recurrence (letting $m=p-1$ for simplicity of notation) $$f(n, k)=m^{2k}f(n-1, k)+(2m^{n+k-1}-m^{2k-1}-m^{2k-2})f(n-1, k-1)+m^{2k-3}(m^{n-k+1}-1)^2f(n-1, k-2)$$ You can then show by induction that $f(n, n)$ and $f(n, n-1)$ are both divisible by $p$ for $n \ge 3$. It's true for $n=3$, because $f(3, 2)=m^5(m+1)^2(m-1)$ and $f(3, 3)=m^6(m+1)(m-1)^2$ are both divisible by $m+1$. Then since $m=p-1 \equiv -1\pmod{p}$, you can just use the above equation $\pmod{p}$ to write $$f(n, n-1) \equiv f(n-1, n-1)+2f(n-1, n-2)$$ $$f(n, n) \equiv -2f(n-1, n-1)-4f(n-1, n-2)$$ which are both zero by hypothesis. (I did also turn the above recurrence into a generating function identity, but the result seems very hard to solve. It's been a long time since I used generating functions, so I don't know if it's hard just because of that.))

  • Now I'm confused --- here's why I thought being nonzero was plausible. I think it suffices to count matrices with first row and column all 1s, say. But in the 3x3 case I think I get 212 such matrices over $\mathbb{F}_5$? (I just brute forced it but I probably just made a mistake in a reduction step.) Same sort of deal for 7, 11, 17, 19, 23 and then I stopped. (Not 13, though.) – alpoge Dec 25 '14 at 16:15
  • You can scale columns so the first row is all 1's, and then scale rows $2$ to $n$ so the first column is all 1's. Then you can subtract the first row from all of the other rows, so that you see $f(n, n)$ is $(p-1)^{2n-1}$ times the number of invertible $(n-1)\times (n-1)$ matrices that don't contain a $-1$. For $n=3$ and $p=5$, this gives that your result is divisible by $4^5$ ($4^4$ in the determinant $1$ case). $212$ isn't (in fact it's waaay too small!), so I think you made a computation error. My computation shows that $f(3, 3)=p(p-1)^6(p-2)^2$, so your answer should be $46080$... – Krishanu Sankar Dec 25 '14 at 17:36
  • But there are only 256 3x3 matrices with 1s in the first row and column and entries between 1 and 4! – alpoge Dec 25 '14 at 18:03
  • Whoops! I made a computational mistake, as expected (I counted those with nonzero determinant, rather than determinant not zero mod p!). It seems the congruence mod p stabilizes in the 2x2 case to 2, and in the 3x3 case to -6? Or maybe I mixed up a sign. Anyway now I get 201 matrices, though we'll see how long that lasts... – alpoge Dec 25 '14 at 18:13
  • (By the way, these small numbers are the (alleged) counts once you fix the first row and column, which is why they're small --- the 4^5 was factored out. Can you explain the recurrence?) – alpoge Dec 25 '14 at 19:02

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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