16
$\begingroup$

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)$?

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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