Determinant Formula for derangement of $n$ numbers?

362 Views Asked by At

The field $F$ with characteristic two is given, and a $2n\times 2n$ matrix $A=(a_{ij})$ with entries in $F$ is defined as follows:

$$a_{ij}=0\text{ for }i=j\text{ and }a_{ij}=1\text{ otherwise.}$$

Prove that $\det(A)$ is equal to the number of derangements of $2n$ elements.

3

There are 3 best solutions below

0
On BEST ANSWER

It actually does not. For example, if $n=2$ then you get $-1$ instead of $1$. If you compute the permanent instead of the determinant then you do get the number of derangements. The permanent of $A$ is the sum over all "generalized diagonals" $a_{i\pi(i)}$ for all permutations $\pi$. In this case, the sum is $1$ if $\pi$ is a derangement, and $0$ otherwise.

0
On

The determinant of $A$ as you've described it (zero along the diagonal, and $1$ everywhere else) is simply $(-1)^{n-1}n$, which is not the number of derangements of $n$ elements.

One eigenvalue is $n$, with eigenvectors being the vectors with all entries equal (a one-dimensional subspace of $\Bbb R^n$). The other one is $-1$, with eigenvectors being the vectors where all entries sum to $0$ (which is an $(n-1)$-dimensional subspace os $\Bbb R^n$). The determinant is the product of all eigenvalues, and therefore the result above follows.

0
On

I think your question was misunderstood a little bit, but also largely answered by Yuval Filmus. Since you wrote that $F$ has characteristic 2, I think you wanted to work in $\mathbb{Z} / 2\mathbb{Z}$.

Hence, I think you could better rephrase your question as:

Given the matrix A(as you defined it), prove that $det(A) \pmod{2}$ is equal to the number of derangements of $2n$ elements. This is in fact true.

The determinant is defined as $$\operatorname{det}(A)=\sum_{\sigma\in S_n}(\operatorname{sgn}{\sigma})\prod_{i=1}^n a_{i,\sigma(i)}$$

where $\operatorname{sgn}{\sigma}$ is the signature of the permutation $\sigma$. The nice thing about evaluating $\pmod{2}$ is that since $1 = -1 \pmod{2}$, all signatures are just 1, and hence $$\operatorname{det}(A) \pmod{2}= \operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)} $$.

Where $\operatorname{perm}(A)$ is the permanent of $A$. It is the determinant except without the signatures.

Clearly, if $i = \sigma(i)$ for any $i$, then $a_{i,\sigma(i)} = 0$ and the permutation will be ignored by the determinant modulo 2. The only cases in which the permutation will not be ignored and $\prod_{i=1}^n a_{i,\sigma(i)}$ will evaluate to 1, are where $i \ne \sigma(i)$ for all $i$, or equivalently if $\sigma$ is a derangement. We are done.