[math-fun] Circulant determinants
A n x n "circulant" determinant A = |A_ij| is constructed from n-vector S = [S_j] by setting A_{i,j} = S_{(i+j) mod n}. Let S be a random n-vector with elements in {-1,+1}. What is the probability that A = 0 ? Example: when n = 32, A has a maximum about 23 decimal digits; yet about 30% of the time it turns out to be zero! Remark: A well-known classical theorem states that A = \product_i \sum_j S_j w^{i j} where w is a primitive n-th root of unity. Fred Lunnon
The probability should depend heavily on the factorization of n. As in Fred's post let w be a primitive n-th root of unity. Define F[j] := sum_j S[i]*w^{i j} Then the determinant is prod_j F[j]. The factor of F[0] behaves differently. If n is odd F[0] is never 0. If n is even then the number of +/-1 vectors making F[0] = 0 is C(n,n/2), where C(i,j) is the binomial coefficient. If j is not 0 then sum_i w^{i j} = 0, so it suffices to consider 0/1 vectors instead of +/- 1 vectors. If n is prime any n-1 of the w^{i j} are linearly independent over Q, and all the F[j] for j not 0 are conjugate, so they all either vanish together, or don't. So there are only 2 setting of S[i] that make them vanish -- the all 0's and the all 1's. When n is a power of 2 it's diametrically opposed. The only cases are given by the multiplicative order of w. For each case you can work out the number of assignments that make F[j] = 0 as a sum of products of binomial coefficients. The hard part (which I haven't done) is to figure out how to avoid double counting. Victor On Wed, Sep 24, 2008 at 6:54 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
A n x n "circulant" determinant A = |A_ij| is constructed from n-vector S = [S_j] by setting A_{i,j} = S_{(i+j) mod n}.
Let S be a random n-vector with elements in {-1,+1}.
What is the probability that A = 0 ?
Example: when n = 32, A has a maximum about 23 decimal digits; yet about 30% of the time it turns out to be zero!
Remark: A well-known classical theorem states that
A = \product_i \sum_j S_j w^{i j}
where w is a primitive n-th root of unity.
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 9/27/08, victor miller <victorsmiller@gmail.com> wrote:
... Define
F[j] := sum_j S[i]*w^{i j}
Then the determinant is prod_j F[j].
Should I think have read F[j] := sum_k S[k]*w^{k j} Good point about case j = 0. In fact, I did start off looking at {0,1} circulants, which displayed similar unexpected behaviour --- though to a lesser extent, for the reason mentioned. Edwin Clark has also communicated to me a proof for the prime case, and placed a list of counts for low n at OEIS A144926. WFL
participants (2)
-
Fred lunnon -
victor miller