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

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

-

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

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

-
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