Circulant $\lbrace -1,1 \rbrace $ matrices with eigenvalues seen in first row

Question

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

and

(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}. $$

Answer 1

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

Answer 2

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;
    end

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

    % 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
            continue;
        else
           v(j) = c(1);h
        end
    end

end

y = v;