login
Number of terms in polynomial expression for determinant of generic circulant matrix of order n.
1

%I #19 Aug 31 2014 07:07:04

%S 1,2,4,10,26,68,246,810,2704,7492,32066,86500,400024,1366500,4614524,

%T 18784170,68635478

%N Number of terms in polynomial expression for determinant of generic circulant matrix of order n.

%C Define an n X n matrix A[i,j] by A[i,j]=x_(i+j), subscripts on x being interpreted mod n. This is a generic circulant matrix. If we expand det(A) we obtain a polynomial in the x_i. Define a(n) to be the number of terms in this polynomial after like terms have been combined. (Replacing det(A) with per(A), the permanent of A, we get sequence A003239).

%H Hugh Thomas, <a href="http://arXiv.org/abs/math.CO/0301048">The number of terms in the permanent ...</a>, arXiv:math/0301048 [math.CO], 2003.

%F a(n) <= A003239(n), with = if n is a prime power. For other values of n little is known.

%e Example : for n=2 the matrix is

%e x2,x1

%e x1,x2

%e and the determinant is (x_2)^2 - (x_1)^2 so a(2) = 2 and likewise for the permanent.

%t Table[Clear[x]; r=Array[x,n]; m=Table[RotateRight[r,i], {i,0,n-1}]; Length[Expand[Det[m]]], {n,10}] (* _T. D. Noe_, Oct 22 2008 *)

%Y Cf. A003239.

%K nonn,hard,more

%O 1,2

%A Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 13 2003

%E a(13) term added by _T. D. Noe_, Oct 22 2008

%E a(14) and a(15) from _Roman Pearce_, Aug 30 2014

%E a(16) and a(17) from _Robert Israel_, Aug 30 2014