|
%I #15 Feb 05 2018 16:45:03
%S 0,0,4,2,8,2,40,2,128,62,504,2,1768,2,6864,2738,24192,2,107128,2,
%T 331096,109334,1410864,2,5880544,206282,20801200,5417630,73508696,2,
%U 345334744,2,1150681600,278770214,4667212440,133401818,19355912632,2,70690527600,15151534406
%N Number of n X n (-1,1)-circulant matrices with determinant 0.
%C The sequence comes from a problem suggested by Fred Lunnon on the math-fun mailing list on Sep 24 2008. a(n) is also the number of polynomials of degree at most n-1 with all coefficients equal to 1 or -1 which are not invertible modulo x^n - 1. I have a proof that a(n) = 2 if n is an odd prime. - _W. Edwin Clark_
%C _Max Alekseyev_'s proof that a(2*p) = 2*binomial(2*p,p) if p is an odd prime:
%C First notice that A144926(2p) equals the number of such (1,-1)-polynomials f(x) of degree 2p-1 that are divisible by at least one of the cyclotomic polynomials of orders 1, 2, p, or 2p (that are divisors of 2p). These cyclotomic polynomials are: c(1,x) = x - 1, c(2,x) = x + 1, c(p,x) = x^(p-1) + x^(p-2) + ... + x + 1, and c(2p,x) = x^(p-1) - x^(p-2) + ... - x + 1.
%C Our goal is to prove that (i) f(x) may be divisible only by (x-1) or (x+1) but not both; (ii) if c(p,x) divides f(x) then so does either (x-1) or (x+1) ; (iii) if c(2p,x) divides f(x) then so does either (x-1) or (x+1). Conditions (i), (ii), (iii) all follow from the following Lemma (that in turn directly follows from the definition of f(x)):
%C Lemma. The values of f(1) and f(-1) are even but different modulo 4.
%C To prove (i), it is enough to notice that if f(x) were divisible by (x - 1) and (x + 1), then f(1) = f(-1) = 0, a contradiction to the Lemma. To prove (ii), suppose that f(x) = c(p,x) * q(x) for some integer polynomial q. Then f(1) = p * q(1), together with the Lemma and primality of p implying that f(1) = -2p, 0, or 2p. But it is easy to see that if f(1)=0, then (x-1) divides f(x); while if f(1) = -2p or 2p, then (x+1) divides f(x). Condition (iii) is proved similarly to (ii).
%C From (i), (ii), (iii), it follows that to compute A144926(2p) it is enough to compute the number of such f(x) that are divisible by (x-1) and the number of such f(x) that are divisible by (x+1) and add up these numbers. Clearly, each of these numbers equals binomial(2p,p) that completes the proof. - _Vladeta Jovovic_, Oct 02 2008
%H W. F. Lunnon and Max Alekseyev, <a href="/A144926/b144926.txt">Table of n, a(n) for n = 0..51</a>
%H W. F. Lunnon, <a href="/A144926/a144926.txt">C program for A144926 and A086328</a>
%F a(2*n+1) = A086328(2*n+1), n>0. - _Vladeta Jovovic_, Sep 29 2008
%e If n is an odd prime the only two such matrices are the matrix J with all entries 1 and the matrix -J with all entries -1.
%p a := proc(n) local T, b, U, M; if isprime(n) and n <> 2 then return 2 end if; T := combinat:-cartprod([seq({-1, 1}, j = 1 .. n)]); b[n] := 0; while not T[finished] do U := T[nextvalue](); M := Matrix(n, shape = Circulant[U]); if LinearAlgebra:-Determinant(M) = 0 then b[n] := b[n]+1 end if end do; return b[n] end proc
%K nonn
%O 0,3
%A _W. Edwin Clark_, Sep 25 2008; corrected Sep 25 2008
%E a(22)-a(39) from _Fred Lunnon_, Oct 02 2008, Oct 04 2008
|
