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

Everybody knows that there are $D_n=n! \left( 1-\frac1{2!}+\frac1{3!}-\cdots+(-1)^{n}\frac1{n!} \right)$ derangements of $\{1,2,\dots,n\}$ and that there are $D_n(q)=(n)_q! \left( 1-\frac{1}{(1)_q!}+\frac1{(2)_q!}-\frac1{(3)_q!}+\cdots+(-1)^{n}\frac1{(n)_q!} \right)$ elements in $\mathrm{GL}(q,n)$ which do not have $1$ as an eigenvalue; here $q$ is a prime-power, $(k)_q!=(1)_q(2)_q\cdots(k)_q$ are the $q$-factorials, and $(k)_q=1+q+q^2+\cdots+q^{k-1}$ are the $q$-numbers.

Now, there are $D_n^+=\tfrac12\bigl(|D_n|-(-1)^n(n-1)\bigr)$ and $D_n^-=\tfrac12\bigl(|D_n|+(-1)^n(n-1))\bigr)$ even and odd derangements of $\{1,2,\dots,n\}$, as one can see, for example, by computing the determinant $\left| \begin{array}{cccccc} 0 & 1 & 1 & \cdots & 1 & 1 \\ 1 & 0 & 1 & \cdots & 1 & 1 \\ 1 & 1 & 0 & \cdots & 1 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & 1 & \cdots & 0 & 1 \\ 1 & 1 & 1 & \cdots & 1 & 0 \end{array} \right|$ and looking at the result.

How should one define $D_n^+(q)$ and $D_n^-(q)$?

share|cite|improve this question
up vote 5 down vote accepted

Both of Reid's suggestions sort-of work and lead to the same formula. However, it's easier to first change the question to a $q$-analogue of the difference $$D^{\pm}_n = D^+_n - D^-_n = (-1)^n(n-1).$$ (Also, the formula for $D_n(q)$ is missing a factor of $q^{n(n-1)/2}$.) You can find $D^{\pm}_n$ by the inclusion-exclusion formula just as you can find $D_n$. In fact, it's even easier since only the last two terms of inclusion-exclusion survive. This proof has a straightforward $q$-generalization, although the final formula isn't the same. But I don't know how likely the latter is in the $q$-linear algebra context. The determinant of a matrix seems like the reasonable $q$-analogue of the sign of a permutation, yet it is not a perfect analogue.

Let $\chi$ be a complex character of the multiplicative group of $\mathbb{F}_q$. Let $D^\chi(q)$ be the corresponding sum of $\chi(\det M)$, summed over deranged matrices $M$. Then the $q$-analogue is that $D^\chi(q) = (-1)^nq^{n(n-1)/2}$ for all non-constant $\chi$. The proof uses the Möbius function of the lattice of subspaces, just like for the ordinary enumeration of deranged matrices. This time only the last term of the Möbius inversion survives, the term for the identity matrix.

share|cite|improve this answer

This is just a guess with no basis, but maybe $D_n^+(q)$ should be those elements whose determinant is a quadratic residue (maybe let's assume p > 2 for safety)? Or you could split into $q-1$ groups, based on the determinant.

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.