%I A144926
%S A144926 0,0,4,2,8,2,40,2,128,62,504,2,1768,2,6864,2738,24192,2,107128,2,
%T A144926 331096,109334,1410864,2,5880544,206282,20801200,5417630,73508696,2,
%U A144926 345334744,2,1150681600,278770214,4667212440,133401818,19355912632,2,70690527600,
               15151534406
%N A144926 Number of n X n (-1,1)-circulant matrices with determinant 0.
%C A144926 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 A144926 Max Alekseyev's proof that a(2*p) = 2*binomial(2*p,p) if p is an odd 
               prime: 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, c(2p,
               x) = x^(p-1) - x^(p-2) + ... - x + 1.
%C A144926 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) They all follow from the following Lemma (that in turn directly 
               follows from the definition of f(x)):
%C A144926 Lemma. The values of f(1) and f(-1) are even but different modulo 4. 
               To prove i), it's 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.
%C A144926 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). iii) is proved similarly 
               to ii). 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. But it is easy to see that each of them 
               equal binomial(2p,p) that completes the proof. [From Vladeta Jovovic 
               (vladeta(AT)eunet.yu), Oct 02 2008]
%H A144926 W. F. Lunnon and Max Alekseyev, <a href="b144926.txt">Table of n, a(n) 
               for n=1..51</a>
%H A144926 W. F. Lunnon, <a href="a144926.txt">C program for A144926 and A086328</
               a>
%F A144926 a(2*n+1) = A086328(2*n+1), n>0. [From Vladeta Jovovic (vladeta(AT)eunet.yu), 
               Sep 29 2008]
%e A144926 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 A144926 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
%Y A144926 Sequence in context: A083489 A065464 A040015 this_sequence A153016 A088610 
               A026185
%Y A144926 Adjacent sequences: A144923 A144924 A144925 this_sequence A144927 A144928 
               A144929
%K A144926 nonn
%O A144926 0,3
%A A144926 W. Edwin Clark (eclark(AT)math.usf.edu), Sep 25 2008; corrected Sep 25 
               2008
%E A144926 a(22)-a(39) from W. F. Lunnon, Oct 02 2008, Oct 04 2008