| > For A a subset of { 0, 1 }, let N(A,n) be the number of n by n matrices
> [over] Z/2Z whose set of eigenvalues in Z/2Z is precisely A. Find a
> formula for N(A,n).
>
> [Z is in bold face, denoting the integers. -- edp]
Let W = N(�,n)
X = N({0},n)
Y = N({1),n)
Z = N({0,1},n)
First of all, W+X+Y+Z = 2^(n^2). I didn't think so at first, but I
wasn't reading the questions carefully. The question asks for the set of
eigenvalues in Z/2Z.
Next, W+Y = just the number of non-singular matrices.
That's (2^n - 1) * (2^n - 2) * (2^n - 4) * ... * (2^n - 2^n-1)
= 2^(n(n-1)/2) * prod(j=1..n)(2^j - 1)
Now the map, f:M -> I+M is a permutation of the set of matrices over
Z/2Z. Moreover, if M has eigenvalue 0, then f(M) has eigenvalue 1, and vice
versa. So:
W+X = W+Y
& hence
X = Y
There's only one degree of freedom left in the system. If we could
just construct W, for instance, then we would know all of X,Y,Z.
n=0 => W=0 (X=Y=0, Z=0)
n=1 => W=0 (X=Y=1, Z=0)
n=2 => W=2 (X=Y=4, Z=6)
n=3 => W=48 (X=Y=120, Z= 224)
But the general formula escapes me...
Andrew.
|