login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144926 Number of n X n (-1,1)-circulant matrices with determinant 0. 2
0, 0, 4, 2, 8, 2, 40, 2, 128, 62, 504, 2, 1768, 2, 6864, 2738, 24192, 2, 107128, 2, 331096, 109334, 1410864, 2, 5880544, 206282, 20801200, 5417630, 73508696, 2, 345334744, 2, 1150681600, 278770214, 4667212440, 133401818, 19355912632, 2, 70690527600, 15151534406 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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, and c(2p,x) = x^(p-1) - x^(p-2) + ... - x + 1.

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)):

Lemma. The values of f(1) and f(-1) are even but different modulo 4.

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).

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

LINKS

W. F. Lunnon and Max Alekseyev, Table of n, a(n) for n = 0..51

W. F. Lunnon, C program for A144926 and A086328

FORMULA

a(2*n+1) = A086328(2*n+1), n>0. - Vladeta Jovovic, Sep 29 2008

EXAMPLE

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.

MAPLE

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

CROSSREFS

Sequence in context: A065464 A201400 A040015 * A153016 A231549 A088610

Adjacent sequences:  A144923 A144924 A144925 * A144927 A144928 A144929

KEYWORD

nonn

AUTHOR

W. Edwin Clark, Sep 25 2008; corrected Sep 25 2008

EXTENSIONS

a(22)-a(39) from Fred Lunnon, Oct 02 2008, Oct 04 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 20:55 EDT 2019. Contains 328103 sequences. (Running on oeis4.)