MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For the circulant matrix $C$ of order $n=4$ with first row $[-1,1,1,1]$ say $$ C = Circ(-1,1,1,1) $$ we have the equality of vectors $$ [R(1),R(\omega),R(\omega^2),R(\omega^3)] = c [-1,1,1,1], $$ where $$ \omega=exp(2\pi i/4)=i, $$ $$ c =-2 $$ and $R(t)$ is the the representer polynomial of $C$ namely, $$ R(t)=-1+t+t^2+t^3. $$

Question: Are there other such matrices $C$ when $n =4k >4$ ?

More precisely: Let $k >1$ be an integer, and let $n=4k.$ We want a matrix $C$ such that

(a) $$ C = Circ(h_1, \ldots,h_n), $$ be a non-singular circulant matrix of order $n$ with $h_i \in \lbrace -1,1 \rbrace$ for all $i=1, \ldots,n.$


(b) For some nonzero integer $c \neq 0$ one has the equality of vectors $$ [R(1),R(\omega), \ldots, R(\omega^{n-1}] = c [h_1, \ldots,h_n]. $$ where $$ \omega=exp(2\pi i/n), $$ and $R(t)$ is the the representer polynomial of $C$ namely, $$ R(t)= h_1+h_2t + \cdots + h_{n}t^{n-1}. $$

share|cite|improve this question

This is a partial answer. What you are looking for is an eigenvector $h$ of the matrix $M$ whose entries are $\omega^{(j-1)(k-1)}$. The eigenvalue is $c$. Because $M^*M=nI_n$, we must have $|c|=\sqrt n$. because of the first equation $R(1)=ch_1$ and the fact that $h_j=\pm1$, we see that $c$ must be real. Hence $c=\pm\sqrt n$. Now the question reduces to whether $Mh=\pm nh$ has a solution with $h_j=\pm1$. One way to continue the analysis is to calculate the powers $M^2,\ldots$. They look to be much simpler than $M$ itself, due to cancellations, and we have $M^kh=c^kh$. For instance $M^2h=nh$ and $M^4h=n^2h$. Whence necessary conditions.

More precisely, $N=M^2$ has entries $n_{jk}=0$, except for $j+k=2$ (mod $n$). Its eigenvalues are $\pm n$, with respective multiplicities $2k+1$ and $2k-1$. Only $c^2=n$ matters for you. Then you have $h_j=h_{n+2-j}$ for every $j=2,\ldots,2k$.

share|cite|improve this answer
@Denis: Thanks for nice idea. Your matrix $M$ is $\sqrt{n}$ times the conjugate transpose of the Fourier matrix $F$ that has order $4$. Carlitz obtained his characteristic polynomial. His eigenvalues are $1,-1,i,-i$ but I have not found how to track his eigenvectors. – Luis H Gallardo Jan 10 '11 at 10:00
@Denis: Previous comment solve the problem ? – Luis H Gallardo Jan 10 '11 at 10:07
@Denis: Moreover, Carlitz's paper , sadly, says nothing about the eigenvectors. – Luis H Gallardo Jan 21 '11 at 14:56

A quick bit of MATLABing gives 4 total solutions for $k = 1$, namely $h = (-,-,+,-)$, $(-,+,+,+)$, $(+,-,-,-)$, and $(+,+,-,+)$: the corresponding values of $c$ are $2,-2,-2,2$.

My code returns no solutions for $k = 2,3,4,5$. For larger values this is prohibitive to run. To play with it (especially in case I made any stupid mistakes, as is entirely possible given the time at which I'm writing this), here it is:

function y = moq51069(K);

% for MO question 51069

n = 4*K;
w = exp(2*pi*i/n);

v = sparse(1,2^n);   % verification array

for j = 1:2^n
    temp = dec2bin(j-1,n);
    h = zeros(1,n);
    for k = 1:n
        h(k) = 2*str2num(temp(k))-1;

    Rv = zeros(1,n);
    for m = 1:n
        t = w^(m-1);
        tt = t.^(0:(n-1))';
        Rv(m) = h*tt;

    % test for constant integrality
    c = Rv./h;
    mc = max(max(abs(c - mean(c))));
    if mc < 10^-6
        h2 = [h(1),fliplr(h(2:end))]';
        C = toeplitz(h2,h);
        if det(C) == 0
            'det = 0 for j = ',j
           v(j) = c(1);h


y = v;
share|cite|improve this answer
BTW, it's not clear to me how much $C$ really has to do with anything. It's not actually used in the code except to check the determinant (and for this purpose we could use a special formula for determinants of circulant matrices). – Steve Huntsman Jan 10 '11 at 6:45
k=6 gives no solutions also. – Steve Huntsman Jan 10 '11 at 15:50
@Steve: Thanks for computations. An interesting case is $n=36$ but for the moment I do not see how try to do this case. – Luis H Gallardo Jan 21 '11 at 15:57
Using Denis' answer to modify this code should make $n \le 12$ accessible to exhaustive search. – Steve Huntsman Jan 21 '11 at 20:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.