DERANGEMENTS AND EIGENVALUE-FREE ELEMENTS IN FINITE CLASSICAL GROUPS

Abstract

Permutations that have no fixed points have been known for a very long time as ‘derangements’. Under that heading Rouse-Ball [10, p. 46] puts the matter in the following charming way: ‘Suppose you have written a letter to each of n different friends, and addressed the n corresponding envelopes. In how many ways can you make the regrettable mistake of putting every letter into a wrong envelope?’ He traces this problem back to 1713 and since then it has occurred in one form or another in many elementary texts on probability theory (see for example [12, p. 57] and references cited by Rouse-Ball). Let p_n be the probability that all the letters are put into the wrong envelope. It is well known that p_n→e⁻¹ as n→∞, and that, moreover, convergence is very fast. In fact, p_n =[sum ]ⁿ₀(−1)^r/r!, so that [mid ]p_n−e⁻¹[mid ]<1/(n+1)!.

A derangement can be thought of as a fixed-point-free element of the symmetric group Sym(n). In this paper we turn our attention to eigenvalue-free elements of finite linear groups. Since an eigenvector of a linear transformation X in a vector space V corresponds to a fixed point of X in the projective space whose points are the 1-dimensional subspaces of V, eigenvalue-free invertible matrices correspond to derangements in projective groups.