% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.59}{23(1)}{2016}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\def\N{\mathbb{N}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\C{\mathbb{C}}
\def\Q{\mathbb{Q}}
\def\P{\mathbb{P}}
\def\I{\mathbb{I}}
\def\F{\mathbb{F}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf New duality operator for complex circulant matrices\\ and a conjecture of Ryser}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Luis H. Gallardo\\
\small Mathematics\\[-0.8ex]
\small University of Brest\\[-0.8ex] 
\small Brest, France\\
\small\tt Luis.Gallardo@univ-brest.fr\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{May 6, 2015}{Mar 10, 2016}{Mar 18, 2016}\\
\small Mathematics Subject Classifications: 11A07, 15A24, 15B34}

\begin{document}

\maketitle


\begin{abstract}
We associate to any given circulant complex matrix $C$ another one $E(C)$ such that 
$E(E(C)) = C^{*}$ the transpose conjugate of $C.$ All circulant Hadamard matrices of order $4$
satisfy a condition $C_4$ on their eigenvalues, namely, the absolute value of the sum of all eigenvalues
is bounded above by $4.$ We prove by a ``descent'' that uses our operator $E$ that
the only circulant Hadamard matrices of order $n \geq 4$, that satisfy a condition $C_n$ that 
generalizes the condition $C_4$  and that consist of a list of $n/4$ 
inequalities for the absolute value of some sums of four eigenvalues of $H,$ are the known ones.

 % keywords are optional
 \bigskip\noindent \textbf{Keywords:} Fourier matrix; Fourier transform; Circulant Hadamard matrices;
 Ryser's Conjecture
\end{abstract}

\section{Introduction}

A complex matrix $H$ of order $n$ is \emph{complex Hadamard} if $HH^{*} = nI_n$, where $I_n$ is the identity matrix of order $n$,
and if every entry  of $H$ 
is in the complex unit circle. Here, the $()^{*}$ means transpose and conjugate. 
When such $H$ has only real entries, so that $H$ is a $\{-1,1\}-$matrix, $H$ is called \emph{Hadamard}.  An  $n \times n$
matrix $H$ is
circulant, say $H=\text{circ}(h_1,\ldots,h_n)$, if the $i$-th row $H_i$ of $H$ is given by 
$H_i = [h_{1-i+1},\ldots, h_{n-i+1}]$, the subscripts being taken modulo $n,$ for example
$H_2 =[h_n,h_1,h_2, \ldots,h_{n-1}].$  For a circulant matrix $H := \text{circ}(h_1,\ldots,h_n),$
the polynomial
\begin{equation*}
\label{repres}
R_H(x) :=h_1+h_2x+ \cdots + h_nx^{n-1},
\end{equation*}
is called the \emph{representer} polynomial of $H.$
A long standing-conjecture of Ryser (see \cite[pp. 134]{ryser})
is:

\begin{conjecture}
\label{mainryser}
Let $n \geq 4.$  If $H$ is a circulant Hadamard matrix of order $n$, then $n=4.$
\end{conjecture}

Details about previous results on the conjecture and a short sample of recent related papers are in
\cite{turyn1}, \cite{cwallis}, \cite{cwallisB}, \cite{Leung}, \cite{BorMoss1}, \cite{BorMoss2}, \cite{Craigen},
\cite{brualdi}, \cite{lhg}, \cite{EGR} and the bibliography therein.  Some of the papers above contains also computer computations
related to the problem. A good source of numerical data about the problem is available in \cite{webmoss}.

For the history of the conjecture up to $2012$, see \cite{EGR}; see also \cite{cwallisB} that describes the current state
of knowledge up to $1993$. It is worth consulting more general classic accounts on Hadamard matrices
that include some results about the conjecture, in \cite{agaian} and  in \cite{wallisbig}. Of course, 
the conjecture being at the center of several very interesting mathematical subjects, some ``false'' proofs were also
published (see \cite{cwallis} for a description of older attempts, and  see \cite{unpubcjedwabA},
for a description of a recent's one).
We prove the conjecture under the following mild condition:
$H$ satisfies the condition $C_n$.

\begin{definition}
A complex circulant  matrix $C$ of order $n=4k$  and representer polynomial $R_C(x)$ satisfies the condition $C_n$ if and only if 
for all $i=1,\ldots,k$ one has
\begin{equation}
\label{condcn}
\vert \lambda_{i}+\lambda_{k+i} + \lambda_{2k+i}  +\lambda_{3k+i} \vert \leq 2.
\end{equation}
where the eigenvalues of $K := C/\sqrt{n}$ are defined by $\lambda_{j} := R_K(\exp(2 \pi i j/n)).$
\end{definition}

It is easy to check that all $8$ circulant Hadamard matrices of order $4$ satisfy the condition $C_4,$
namely that the absolute values of the sum of all its eigenvalues is at most $4.$
Moreover, if a circulant Hadamard matrix $H$ of order $n=4h^2$ satisfies the condition $C_n$ then by adding all these $n/4$
inequalities in (\ref{condcn}) we get the trivial inequality in which ``Tr'' means ``trace'',
$
2h = \vert \text{Tr}(H/\sqrt{n}) \vert  \leq  n/2 = 2h^2.
$
Having said that, we will now proceed to the details.
It is sufficient to prove the following
theorem that is our main result.

\begin{theorem}
\label{mainryser}
Let $h$ be an odd positive integer. If there exists a circulant Hadamard matrix $H$ of order $n=4h^2$
that satisfies the condition $C_n$
then there exists also a circulant Hadamard matrix $K$ of order $h^2.$ 
\end{theorem}

However, it is better to be a bit  more precise. 

\begin{corollary}
\label{ryserdone}
Let $n \geq 4.$  If $H$ is a circulant Hadamard matrix of order $n$ that satisfies the condition $C_n$, then $n=4.$
\end{corollary}

In section \ref{tools} are collected all the necessary tools. Theorem \ref{ddual} that describes a kind of 
``duality operator'' may have an interest in itself.
The most important of all these tools is Lemma \ref{lower4} in which
we manage the main reduction step for the proof of the theorem.
The proof of Theorem \ref{mainryser} appear in section \ref{proofmain}. The proof of Corollary \ref{ryserdone} appears
in section \ref{cormain}.

Thinking to the reader, we added section \ref{thoughs} just after the tools in section \ref{tools}. Indeed, we believe
 that even an
 ``informal'' account of the main new ideas and general
strategy of the proof, merits a special section. Thus, we hope that by just reading this section, 
and before entering the technical details,
the reader, may have (working on an analogy) a rough idea of what is going here.  

\section{Some tools}
\label{tools}
The following classical result of Turyn \cite{turyn} is useful.
\begin{lemma}
\label{turynbasic}
The order $n$ of a circulant Hadamard matrix $H$ such that $n>4$, must be of the
form $n = 4h^2,$ with $h$ an odd integer with at least two distinct prime divisors.
\end{lemma}
We recall the definition of the Fourier matrix  and of the Fourier transform (see \cite[pp. 31--35]{davis}):
\begin{definition}
\label{fourierm}
Let $n$ be a positive integer. Let $w = \exp(2 i \pi/n).$
\begin{itemize}
\item[(a)]
The Fourier matrix $F$ of order $n$ is defined (note the star in the left-hand member), by
$$
\sqrt{n}F^{*} = V([1,w,w^2,\ldots,w^{n-1}]) = (w^{(i-1)(j-1)}).
$$
\item[(b)]
For a matrix $A$ with $m$ rows and $n$ columns and $(i,j)$ entry equal to $a_{i,j}$, we denote, as usual, by $A^{T}$ the ``transpose'' of $A$
i.e., the matrix with $n$ rows and $m$ columns which $(i,j)$ entry is $a_{j,i}.$
\item[(c)] Let  $P(x) := c_1 + c_2x+ \cdots +c_nx^{n-1}$ be a complex polynomial of degree $<n.$ 
The Fourier transform
of the vector $c \in \C^n$ defined by $c := [c_1, \ldots, c_n]^{T}$,
is the vector $d := [d_1, \ldots, d_n]^{T} \in \C^n$
defined by
\begin{equation*}
\label{primero}
\sqrt{n}\cdot[\overline{c_1},\ldots,\overline{c_n}] \cdot F = [\overline{d_1},\ldots,\overline{d_n}] ,\;\;\;
\end{equation*}
where the $\overline{(\cdot)}$ denotes complex conjugation.
\end{itemize}
\end{definition}
 
We need two other results, both are simple consequences of the definitions for which we may check
\cite{davis}. A kind of ``double dual'' property for complex circulant matrices appears in the next theorem.

\begin{lemma}
\label{doubleeigen}
Let $A =\emph{ \text{circ}}(a_1, \ldots,a_n)$ with representer polynomial $R_A(x) \in \C[x].$
Let $w := \exp(2 i \pi /n).$
Set $B := \emph{\text{circ}}(\lambda_1, \ldots, \lambda_n)$ where $\lambda_j := R_A(w^{j-1})$, $j=1,\ldots,n$,
 are the eigenvalues of $A$ in some order.
Let $R_B(x) \in \C[x]$ be the representer polynomial of $B.$
Set $b_j := R_B(w^{i-1})$  for all $j=1,\ldots,n$ be the eigenvalues of $B$ in some order.  Then for all $j=1,\ldots,n$
$$
b_j = n \cdot a_{n-j+2}
$$
where the subscripts are considered modulo $n.$  Moreover, if all $a_i$ from $i=1, \ldots,n$ are real, then
$B=B^{*}.$
\end{lemma}

\begin{proof}
Set $r := \sqrt{n}.$
By definition of the Fourier transform (see Definition  \ref{fourierm}) we have
\begin{equation*}
\label{primero}
r[\overline{\lambda_1},\ldots,\overline{\lambda_n}] \cdot F = [\overline{b_1},\ldots,\overline{b_n}] ,\;\;\;
r[\overline{a_1},\ldots,\overline{a_n}] \cdot F = [\overline{\lambda_1},\ldots,\overline{\lambda_n}] 
\end{equation*}
where $F$ is the Fourier matrix (see again Definition  \ref{fourierm}).
This implies that
\begin{equation}
\label{segundo}
[\overline{b_1},\ldots,\overline{b_n}] = n \cdot [\overline{a_1},\ldots,\overline{a_n}] \cdot F^2 = 
n \cdot [\overline{a_1},\overline{a_n},\overline{a_{n-1}}, \ldots,\overline{a_2}],
\end{equation}
since the symmetric matrix $F^2 = \Gamma = (g_{i,j})$ has $g_{1,1}=1$, $g_{i,j}=1$ when $i+j =n+2$ and zeros 
everywhere else.
The result follows by conjugation of both sides of (\ref{segundo}).  Assume that all $a_i$'s are real. Then it follows that the 
$b_i$'s are also real. This proves that $B=B^{*}.$
\end{proof}

\begin{lemma}
\label{RiRj}
Let $H := \emph{\text{circ}}(h_1, \ldots,h_n)$ be a circulant matrix of order $n>1,$ with real entries $h_j$. Let $w := \exp(2 i \pi /n).$
Let $R_H(x)$ be its representer polynomial. Let $\rho := \emph{\text{circ}}(\lambda_1, \ldots, \lambda_n)$ 
where $\lambda_j := R_H(w^{j-1})$, for all $j=1,\ldots,n$.  For $i=1,\ldots,n,$ let $R_{i}$ be the $i$-th row of $\rho.$
Then for all $j=1,\ldots,n$
we have
$$
\frac{\langle R_1, R_j \rangle}{n} = m_1^2 + m_2^2 v^{j-1} + \cdots + m_n^2 v^{(j-1)(n-1)}
$$
where $v := \overline{w}$, the conjugate of $w$, $\langle \cdot,\cdot \rangle$ is the hermitian product 
$\langle x, y \rangle := x_1 \bar{y_1} + \cdots + x_n \bar{y_n},$
and $m_j :=  h_{n-j+2}$ where the subscripts are considered modulo $n.$ 
\end{lemma}

\begin{proof}
By Lemma \ref{doubleeigen}, $\rho = n \cdot F^{*} \text{diag}(h_1,h_n,h_{n-1}, \ldots,h_2) F$, where 
$F$ is the Fourier matrix. But, $\rho = \rho^{*}$ so that 
$
\beta := \rho \rho{*} = \rho^2 = n^2 \cdot F^{*} \text{diag}(h_1^2,h_n^2,h_{n-1}^2,\ldots,h_2^2)F.
$
We have also by direct multiplication $\beta = \text{circ}(\langle R_1, R_1\rangle , \ldots, \langle R_1,R_n \rangle).$
Let us define some vectors of length $n$. For $j \in \{1,2,\ldots,n\}$ 
let $e_j := [0, \ldots,1,0,\ldots,0]$ with the $1$ being at position $j.$
We compute then
\begin{equation}
\label{part1}
\langle R_1, R_j \rangle/ \;n = \frac{1}{n} \cdot (e_1\cdot  \beta \cdot e_j ) = e_1\cdot (\sqrt{n}F^{*}) \cdot \text{diag}(h_1^2,h_n^2,h_{n-1}^2,
\ldots,h_2^2)
\cdot (\sqrt{n} F) \cdot e_j.
\end{equation}
Observe that by definition of $F$  we have  $e_1 \cdot \sqrt{n}F^{*} = [1,1,\ldots,1]$ so that (\ref{part1}) becomes
$
\langle R_1,R_j \rangle / \;n  = [h_1^2,h_n^2,\ldots,h_2^2] \cdot F/\sqrt{n} \cdot e_j.
$
But,
$$
\sqrt{n} F \cdot e_j = [1, \overline{w}^{j-1},\overline{w}^{2(j-1)}, \ldots,\overline{w}^{(n-1)(j-1)}]^{T}.
$$
The result follows from this.
\end{proof}

We resume both lemmas in the theorem.

\begin{theorem}
\label{ddual}
Let $n$ be a positive integer. Let $C := \emph{\text{circ}}(c_1, \ldots,c_n)$ where $c_i \in \C$ for all $i=1,\ldots,n.$
Put 
$
E(C) := \frac{ \emph{\text{circ}}(\lambda_1, \ldots,\lambda_n)}{\sqrt{n}},
$
where the $\lambda_i$'s are the eigenvalues of $C$ in the order given by the Fourier transform
$
\sqrt{n}\,[\overline{c_1}, \ldots,\overline{c_n}] \cdot F = [\overline{\lambda_1}, \ldots,\overline{\lambda_n}].
$
Write
$
E(E(C)) := \frac{\emph{\text{circ}}(b_1, \ldots,b_n)}{\sqrt{n}},
$
where the $b_i$'s are the eigenvalues of $E(C)$ in the order given by the Fourier transform
$
\sqrt{n}\,[\overline{d_1}, \ldots,\overline{d_n}] \cdot F = [\overline{b_1}, \ldots,\overline{b_n}],
$
where $d_i := \frac{\lambda_i}{\sqrt{n}}$ for all $i \in \{1,\ldots,n\}$. In other words, 
$E(C) =  \emph{\text{circ}}(d_1,\ldots,d_n).$
Then
\begin{itemize}
\item[(a)]
$
E(E(C)) = C^{*}.
$
\item[(b)]
If, moreover $c_j \in \{-1,1\}$ for all $j=1,\ldots,n,$ then
$
C = C^{*}
$
and
$
E(C) \cdot E(C)^{*} = n I_n.
$
\end{itemize}
\end{theorem}

\begin{proof}
Part (a) follows from Lemma \ref{doubleeigen}. First result in Part (b) follows from  Lemma \ref{doubleeigen}.
The second result in part (b) follows from Lemma \ref{RiRj} by taking
$H=C,$ so that
$\rho := \sqrt{n}\cdot E(C)$, since $m_j^2 = c_{n-j+2}^2 =1.$ More precisely, with these choices Lemma \ref{RiRj} 
gives $\langle R_1, R_1 \rangle = n(1+ \cdots +1) =n^2$ and $\langle R_1, R_j \rangle = 1+ w^{j-1} + w^{(j-1)2}+ \cdots + w^{(j-1)(n-1)} = 0,$
that is, we get $E(C) \cdot E(C)^{*} = n I_n$ as claimed.
\end{proof}

The following simple lemma in Davis's book is useful also.

\begin{lemma}
\label{buildcirc}
Let $\Lambda := \emph{\text{diag}}(\lambda_1,\ldots,\lambda_n).$ Then
$
\Gamma := F^{*} \Lambda F
$
is a circulant matrix of order $n.$
\end{lemma}

\begin{proof}
See \cite[Theorem 3.2.3]{davis}.
\end{proof}

The following result is well known and it is easy to check.

\begin{lemma}
\label{eigensH}
All eigenvalues of any Hadamard matrix of order $n$ have the absolute value $\sqrt{n}.$
\end{lemma}

The following class of matrices, \emph{a priori}, an extension of the notion of Hadamard complex matrices,
is important for the proof.

\begin{definition}
\label{low}
Let $n$ be a positive integer. Let $C= (c_{ij})$ be a complex matrix of order $n.$ 
Then we say that $C$ is a \emph{lower}-Hadamard matrix if
$
C \cdot C^{*} = nI_n
$
and for each pair of indices $i,j \in \{1,\ldots,n\}$ one has
$
\vert c_{ij} \vert  \leq 1.
$
\end{definition}

It is practical to recall here the definition.

\begin{definition}
\label{norme}
Let $n$ be a positive integer. For any column vector $v \in \C^n$, say $v =[v_1, \ldots,v_n]^{T}$,
we define its $2$-norm $\vert \vert v \vert \vert$ by
$$
{\vert \vert v \vert \vert}^2 =v_1 \overline{v_1}+ \cdots + v_n \overline{v_n}.
$$ 
\end{definition}

The proposition below shows that we are \emph{not} extending the class of complex Hadamard matrices. It is
good news for us.

\begin{proposition}
\label{stable}
Let $n$ be a positive integer. Then, a matrix $C$ of order $n$, is a lower-Hadamard matrix if and only if $C$
 is a complex Hadamard matrix.
\end{proposition}

\begin{proof}
One direction is trivial.  Assume then that $C$ is a lower-Hadamard matrix. Taking determinants in both sides of 
$C \cdot C^{*} = nI_n$ we get $\vert \det(C) \vert = n^{n/2}.$ But, by Hadamard's inequality we have
\begin{equation}
\label{hadeq}
n^{n/2} = \vert \det(C) \vert \leq \prod_{i=1}^{n} \vert \vert \text{col}_i(C) \vert\vert,
\end{equation}
where $\text{col}_i(C)$ is the $i$-th column of $C.$
Therefore, by hypothesis, and by definition \ref{norme}
$$
{\vert \vert \text{col}_i(C) \vert \vert}^2 = \sum_{k=1}^{n} c_{ki}\overline{c_{ki}} = \sum_{k=1}^{n} {\vert c_{ki} \vert}^2 \leq \sum_{k=1}^{n} 1 =n.
$$
Thus,
\begin{equation}
\label{ineq1}
\vert \vert \text{col}_i(C) \vert \vert\leq \sqrt{n} = n^{1/2}.
\end{equation}

It follows then from \eqref{hadeq} that  we \emph{cannot} have strict inequality $<$ in \eqref{ineq1}
for any given column of $C.$ I.e., we cannot have for \emph{some}
$i \in \{1, \ldots,n\}$
\begin{equation}
\label{ineq2}
\vert \vert \text{col}_i(C) \vert\vert < n^{1/2}.
\end{equation}

In other words it is impossible to have simultaneously \eqref{hadeq} and \eqref{ineq2}, for if both were true
then we obtain from \eqref{hadeq} the contradiction
$
n^{n/2} < {(n^{1/2})}^n.
$
Therefore, we have now, for any given  $k \in \{1, \ldots,n\}$
\begin{equation}
\label{lesk}
S_k :={\vert c_{1k} \vert}^2 + \cdots + {\vert c_{nk} \vert}^2 = n.
\end{equation}
But by hypothesis, $\vert c_{ik} \vert \leq 1$, so, if for some $i$ we have $\vert c_{ik} \vert <1$ then we get
(from \eqref{lesk}) the contradiction
$
n = S_k < n.
$
Thus, we must have
$
\vert c_{ik} \vert  =1
$
for all $k$ and for all $i$ such that $\{i,k\} \subseteq \{1,\ldots,n\}.$
This finishes the proof.
\end{proof}

It will be clear in the proof of the main theorem, and in the proof of the crucial Lemma \ref{lower4},
why  Proposition \ref{stable} is good news for us.

We use the obvious decomposition below of a circulant matrix of  even order $n$ in four blocks of order $n/2,$
(see \cite{lhg} for a related result based on the same decomposition), in order to build a smaller
 size matrix $C$ attached to $H$.

\begin{lemma}
\label{weighing}
Let $n$ be  a positive even integer. Let $H =  \emph{\text{circ}}(h_1, \ldots,h_n)$ be a circulant matrix of order $n.$ Then
there exist matrices $A,B,K$ of order $\frac{n}{2}$ such that
\begin{itemize}
\item[(a)] 
\begin{equation*}
H=
\begin{bmatrix}
A & B\\
B & A\\
\end{bmatrix}
\end{equation*}
\item[(b)]
$K := A+B$ is circulant.
\end{itemize}
\end{lemma}

The lemma below is our main result. The theorem would follow quickly from it.

\begin{lemma}
\label{lower4}
Let $h$ be an odd positive integer. Assume that $H$ is a circulant Hadamard matrix of 
order $n,$ where $n=4h^2,$ that satisfies the condition $C_n.$ 
Then, there exists a circulant lower-Hadamard matrix  $C$ of order $n/4$
such that $C=C^{*}.$
\end{lemma}

\begin{proof}
Let $R = E(H)$ following Theorem \ref{ddual} applied to $H.$ By part (b) of the same Theorem \ref{ddual}, one has
$R=R^{*}$ and $RR^{*}=nI_n$.
Set $S = \frac{A+B}{2}$ where $A$ and $B$ are defined by Lemma \ref{weighing} applied to the matrix $R.$
Thus, $S$ is circulant. Write $S=\text{circ}(s_1,\ldots,s_n).$
Since $R$ is, trivially, lower-Hadamard, we claim that $S$ satisfies $S S^{*} =(n/4)I_{n/2}.$ 
Moreover, we claim that $S$ is hermitian.
In order to prove the claim observe that
$
\vert a_i  \vert \leq 1 \;\text{and}\; \vert b_i \vert \leq 1.
$
It follows that we have also
$
\label{lerr}
\vert s_i \vert = \left \vert \frac{a_i +b_i}{2} \right \vert \leq \frac{1+1}{2} = 1,
$
where $a_i$ is the $i$-th entry in row $1$ of $A$, and  $b_i$ is the $i$-th entry in row $1$ of $B$.  This proves the necessary
conditions on the entries of $S;$ and it is the core of the proof.
We now check the equation $S S^{*} = (n/4)I_{n/2}$. From $R R^{*} = nI_n,$ one gets by block multiplication
$AA^{*}+BB^{*} = n I_{n/2}$  and  $AB^{*}+BA^{*} =0.$  Thus,
\begin{equation}
\label{weic}
 AA^{*}+AB^{*}+BA^{*}+BB^{*} = AA^{*}+BB^{*} =n I_{n/2}.
\end{equation}
It follows from \eqref{weic}, and the definition of $S,$ that $S$  satisfies the equation.
It remains to prove that $S$ is hermitian. From the definition of $A$ and $B$ one has $A=A^{*}$ and $B=B^{*}$ since $R=R^{*}.$
It follows that $S^{*} = S.$
We have then established the claim. In order to complete the proof we apply now, by using our condition $C_n,$ an analogue construction to the matrix $S$, instead that applying it
to the matrix $R.$  In other words we do the following.  Observe that $n/2=2h^2$ is an even positive integer. Define then 
the matrices $K$ and $L$ both of order $n/4$ by applying
Lemma \ref{weighing} to the circulant matrix $S.$  I.e., one has
\begin{equation*}
S=
\begin{bmatrix}
K & L\\
L & K\\
\end{bmatrix}.
\end{equation*}
More precisely, the first rows $Row_K(1)$, $Row_L(1)$ of $K$ and $L$ are respectively:
$
\label{row1K}
Row_K(1) = [s_1,\ldots,s_{n/4}]
$
and
$
\label{row1L}
Row_L(1) =[s_{n/4+1},\ldots,s_{n/2}].
$
We define now our target matrix  $C$ by
\begin{equation}
\label{lecc}
C :=  K+L.
\end{equation}
By Lemma \ref{weighing} $C$ is a circulant matrix of order $n/4.$ Write $C= \text{circ}(c_1,\ldots,c_{n/4}).$

Put $R=E(H) = \text{circ}(d_1, \ldots,d_n).$ Since $H$ satisfies the condition $C_n$ one has
\begin{equation*}
\label{less}
\vert c_i \vert = \left \vert s_i +s_{n/4+i} \right \vert = \vert (d_i+d_{i+h^2}+d_{i+2h^2}+d_{i+3h^2})/2  \vert \leq \frac{2}{2} = 1
\end{equation*}
for all $i=1,\ldots,n/4.$

We claim that $C$ is a circulant lower-Hadamard matrix of order $n/4.$
The only thing that remains to be proved is the equality:
$
\label{lacc}
C C^{*} = (n/4) I_{n/4}.
$
As before we have the following.
From $S S^{*} = (n/4)I_{n/2},$ one gets by block multiplication
$KK^{*}+LL^{*} = (n/4) I_{n/4}$  and  $KL^{*}+LK^{*} =0.$  Thus, by (\ref{lecc})
\begin{equation*}
\label{secondstep}
 CC^{*}= KK^{*}+KL^{*}+LK^{*}+LL^{*} = KK^{*}+LL^{*} = (n/4) I_{n/4},
\end{equation*}
that proves the equality.
It remains to prove that $C$ is hermitian. From the definition of $K$ and $L$ one has $K=K^{*}$ and $L=L^{*}$ since $S=S^{*}.$
It follows that $C^{*} = C.$ We have then established that $C$ is a circulant lower-Hadamard matrix of order $n/4$, and that $C$ is hermitian.
This proves the lemma.
\end{proof}

Now, we describe the eigenvalues of our matrix $C$ defined above.

\begin{lemma}
\label{eigensC}
The eigenvalues of the matrix $C$ defined in Lemma \ref{lower4} 
are elements of the set
$Eig(C) := \{\sqrt{n}/2,-\sqrt{n}/2\}.$
\end{lemma}

\begin{proof}
Since $C$ is hermitian by Lemma \ref{lower4} the result follows from Lemma \ref{eigensH}.
\end{proof}

\section{Informal account of the new idea for the proof}
\label{thoughs}

The idea is to try to build a circulant Hadamard matrix, say $T_2,$ of smaller size than a given 
circulant Hadamard matrix $H$ of order $n$, that satisfies the condition $C_n.$
Of course, this appears at first view like an impossible task.  However, the fact that $H$ is formed of four blocks of size $n/2$ since
$H$ is circulant, suggest a first try.  Assume that  
\begin{equation*}
H=
\begin{bmatrix}
A & B\\
B & A\\
\end{bmatrix}
\end{equation*}
Then it is easy to see, using that $HH^{*}= I_n$ and block multiplication,
 that $T_1 := (A+B)/2$, of size $n/2$ is circulant, has its entries in $\{-1,0,1\}$ and satisfies $T_1 T_1^{*} = (n/4)I_{n/2}.$
Repeating the procedure we got (we cannot now divide by $2$), say, $T_2 := C+D$, of size $n/4$ is
 circulant with entries in $\{-2,-1,0,1,2\}$ and satisfies $T_2 T_2^{*} = (n/4) I_{n/4}. $  Besides the problem with the entries
not equal to $-1$ or to $1$ these circulant matrices, may exist !. For example, for $n=36$ (for which of course it is known
that there are no circulant Hadamard matrix), we got, by example $T_2 := \text{circ}(0,1,-1,0,1,-1,0,1,2)$ that satisfies
$T_2 T_2^{*}=9I_9.$  An interesting comment of the referee is that an orthogonal matrix with few entries often appear
in ``frames'' in some lattices such as Leech lattice.

We need then to ``fix'' the problem with the entries in such a manner that we do \emph{not} have trivial solutions as above.
This can be done by considering a slightly more general form of a circulant Hadamard matrix. Namely, considering instead
a matrix $H$ with complex entries that satisfies $HH^{*}=nI_n$ and has its entries in the complex unit disk.  First of all we prove
(see Proposition \ref{stable}) that these matrices are exactly the same as the matrices with the same constraint but having
 its entries exactly in the boundary
of the disk. This uses the classical Hadamard's inequality.
 Then with the help of the Fourier transform we obtain a kind of  ``duality operator'' $E$ (see Theorem \ref{ddual}). After that 
(see Lemma \ref{lower4})
we build an analogue of the construction above, beginning now with $E(H)$ instead that with $H$, that works in the more general
context,  and then (see proof on next section)
we are able to show
that we can really do the ``fix'', i.e., we are able to build a kind of ``descent''. This ``descent'' is possible by the condition $C_n$
on the eigenvalues of $H,$
(see (\ref{less})) above.

We are now ready to show our main result.

\section{ Proof of Theorem \ref{mainryser}}
\label{proofmain}
Let $n=4h^2.$ Let $H$ be a circulant Hadamard matrix of order $n.$ From Lemma \ref{lower4} there exists a circulant,
lower-Hadamard matrix $C$ of order $n/4$ such that $C$ is hermitian. Write $C=\text{circ}(c_1,\ldots,c_{h^2}).$ 
We define (see Lemma \ref{buildcirc}) a
circulant matrix $T$ by 
$
\label{leTe}
T = h \cdot F^{*} \text{diag}(c_1,\ldots,c_{h^2})F
$
where $F$ is the Fourier matrix defined in Definition \ref{fourierm}, and $\text{diag}(c_1,\ldots,c_{h^2})$ is a diagonal matrix of order
$h^2$ with
diagonal entries $c_i$ for $i=1 \ldots,h^2.$ Let
$
\label{entriesT}
T := \text{circ}(t_1,\ldots,t_{h^2}).
$
Observe that the eigenvalues of $T$ are $hc_1,\ldots,hc_{h^2}.$
More precisely, see Theorem \ref{ddual}, one has
$
\label{EdeT}
E(T) = C.
$
Define now the circulant matrix $D = \text{circ}(d_1,\ldots,d_{h^2})$ of order $n/4$ by
\begin{equation}
\label{doubleEdeT}
D := E(E(T)).
\end{equation}
By Lemma \ref{eigensC} we see that the eigenvalues of $C$ are in $\{h,-h\}.$
This together with the definition of $D$ (see Theorem \ref{ddual}) implies that one has for all $i=1,\ldots,h^2$
$
\label{Dentries}
d_i \in \{-1,1\}.
$
More precisely: from \eqref{EdeT} and the definition of $E(C)$ (see Theorem \ref{ddual}) we have
%\begin{equation*}
$
\label{ech}
D = E(E(T)) = E(C) = \frac{\text{circ}(\delta_1,\ldots,\delta_{h^2})}{h}
$
%\end{equation*}
where the $\delta_i$'s, for $i=1,\ldots,h^2$ satisfy
$
\delta_i \in \{h,-h\},
$
by  Lemma \ref{eigensC}.
Now, we come back to $T$.  Since $C$ is a circulant lower-Hadamard matrix of order $h^2$,
by Proposition \ref{stable} we have that, indeed, $C$ is a circulant complex Hadamard matrix. This means, in particular,
that all the entries of the first row of $C$, namely  all the $c_i$ from $i=1,\ldots,h^2$ satisfy
\begin{equation}
\label{cunits}
\vert c_i \vert =1
\end{equation}
(and \emph{not} just merely that $\vert c_i\vert \leq 1$).  Here we touch, really the point of the proof.

Since $C$ is a circulant complex Hadamard matrix of order $h^2$, we have also
$
C C^{*} = h^2 I_{h^2}.
$
We will show now that \eqref{cunits} has important consequences:

We claim that
$
\label{Tisok}
T T^{*} = h^2 I_{h^2}.
$
Proof of the claim using \eqref{cunits}: 
$$
T T^{*} =h^2 \cdot  F^{*}\text{diag}(c_1,\ldots,c_{h^2})F F^{*}\text{diag}(\overline{c_1},\ldots,\overline{c_{h^2}})F
$$
$$
= h^2 \cdot F^{*}\text{diag}({\vert c_1 \vert}^2,\ldots,{\vert c_{h^2} \vert}^2)F = h^2 \cdot F^{*}\text{diag}(1,\ldots,1)F
$$
$$
= h^2 \cdot F^{*} I_{h^2} F = h^2 \cdot  F^{*}F = h^2 \cdot I_{h^2}.
$$
It remains just the following claim about the entries in the first row of the circulant matrix $T$:
We claim that for all $i=1,\ldots,h^2$ one has
$
\label{Tispm1}
t_i \in \{-1,1\}.
$
Proof of the claim:
By Theorem \ref{ddual} part (a) one has
$
\label{duality}
E(E(T)) = T^{*}.
$ 
But, by \eqref{doubleEdeT}, this means
\begin{equation}
\label{ddt}
T^{*} = D.
\end{equation}
But, each entry of the matrix $D$ is in $\{1,-1\}$. So by \eqref{ddt}, each entry of the
matrix $T^{*}$ is in $\{-1,1\}.$ Therefore, each entry of the matrix $T$ is also in  $\{-1,1\}.$
This proves the claim. We have then
\begin{itemize}
\item[(a)]
The matrix $T$ is a circulant matrix of order $h^2$. All its entries belong to the set $\{1,-1\}$,
and
\item[(b)]
the circulant matrix $T$ of order $h^2$ satisfies
$
T T^{*} = h^2 I_{h^2}.
$
\end{itemize}

Therefore we obtain, by the definition of a Hadamard matrix, that $T$ is a
circulant Hadamard matrix of odd order $h^2.$
This proves the theorem.

\section{Proof of  Corollary \ref{ryserdone}}
\label{cormain}
Put $n=4h^2$ where $h$ is an odd positive integer.
By Theorem \ref{mainryser}  we deduce that there exists a circulant Hadamard matrix of odd order $h^2.$
But it is well known that the unique square matrices of odd order $k$ that are circulant and Hadamard, simultaneously,
are all of order $k=1$. More precisely these matrices are the following two square matrices with one, and only one, entry:
$I_1=(1)$ and $I_2=(-1)$.  Therefore, we must have $h=1.$ This proves the corollary.

\subsection*{Acknowledgements}
We thank Bahman Saffari for writing his inspiring nice papers on polynomials. In particular, we \emph{warmly} thanks him,
for choosing to display
the following (non-mathematical) statement: ``Whatever is worth doing is worth doing badly'' in the 
Introduction part of the most important of them. We are grateful to the referee for careful reading, for suggestions
that improved the presentation of the paper and for an observation that resulted in a much better Lemma \ref{eigensC}.



\begin{thebibliography}{99}

\bibitem{agaian} S. S. Agaian.
\newblock Hadamard matrices and their applications.
\newblock {\em Lecture Notes in Mathematics}. 1168. Springer-Verlag, Berlin, 1985.

\bibitem{BorMoss1} P. Borwein, M. J. Mossinghoff.
\newblock Wieferich pairs and Barker sequences.
\newblock {\em Des. Codes Cryptogr.}. 53(3):149--163, 2009.

\bibitem{BorMoss2} P. Borwein, M. J. Mossinghoff.
\newblock Wieferich pairs and Barker sequences, II.
\newblock {\em LMS J. Comput. Math.}. 17(1):24--32, 2014.

\bibitem{brualdi} R. A. Brualdi.
\newblock A note on multipliers of difference sets. 
\newblock {\em J. Res. Nat. Bur. Standards Sect. B}. 69:87--89, 1965.

\bibitem{Craigen}
R. Craigen, G. Faucher, R. Low, and T. Wares, \newblock Circulant partial Hadamard matrices.
\newblock {\em Lin. Alg. Appl.}. 439:3307-3317, 2013.

\bibitem{unpubcjedwabA}
R. Craigen, J. Jedwab. 
\newblock``Comment on revised version of ``The Hadamard circulant conjecture,''''. 
\newblock {\em arXiv:1111.3437v2 [math.CO]}. 

\bibitem{cwallisB} C. Lin, W. D. Wallis. 
\newblock Barker sequences and circulant Hadamard matrices.
\newblock {\em J. Combin. Inform. System Sci.}. 18(1--2):19--25, 1993.

\bibitem{cwallis} C. Lin, W. D. Wallis. 
\newblock On the circulant Hadamard matrix conjecture.
\newblock {\em Coding theory, design theory, group theory (Burlington, VT, 1990)}. 213--217,
Wiley-Intersci. Publ., Wiley, New York, 1993.

\bibitem{davis} P. J. Davis,
\newblock {\em Circulant matrices, 2nd ed.}.
\newblock  New York, NY: AMS Chelsea Publishing, xix, 250 p. 1994.

\bibitem{shalomK} S. Eliahou, M. Kervaire.
\newblock Corrigendum to:``Barker sequences and difference sets'', [Enseign. Math. (2) 38, no. 3-4, 
345--382, 1992].
\newblock {\em Enseign. Math.}. 40(1--2):109--111, 1994. 

\bibitem{EGR}
R. Euler, L. H. Gallardo, and O. Rahavandrainy, \newblock Sufficient conditions for a conjecture of
Ryser about Hadamard Circulant matrices. \newblock {\em Lin. Alg. Appl.}. 437:2877-2886, 2012.

\bibitem{lhg} L. Gallardo, \newblock On a special case of a conjecture of Ryser about Hadamard
circulant matrices. 
\newblock {\em Appl. Math. E-Notes}. 12:182-188, 2012.

\bibitem{webmoss}
M. J. Mossinghoff, \newblock ``Wieferich prime pairs, Barker sequences, and circulant Hadamard matrices''. 2013,
\newblock {\em http://www.cecm.sfu.ca/~mjm/WieferichBarker/}.

\bibitem{Leung}
K. H. Leung, B. Schmidt. \newblock New restrictions on possible orders of circulant Hadamard matrices.
\newblock {\em Designs, Codes and Cryptography}. 64:143-151, 2012.

\bibitem{ryser} H. J. Ryser.
 \newblock {\em Combinatorial mathematics}. \newblock The Carus Mathematical Monographs,
 No. 14 Published by The Mathematical Association of America; distributed by 
John Wiley and Sons, Inc.,
 New York, 1963.

\bibitem{turyn1} J. Storer, R. Turyn. 
\newblock On binary sequences. 
\newblock {\em Proc. Am. Math. Soc}.12:394--399, 1961.

\bibitem{turyn} R. Turyn, 
\newblock Character sums and difference sets. 
\newblock {\em Pacific J. Math}, 15:319--346, 1965.

\bibitem{wallisbig} W. D. Wallis, A. P. Street, and J. S. Wallis.
\newblock Combinatorics: Room squares, sum-free sets, Hadamard matrices.
\newblock {\em Lecture Notes in Mathematics}, 292. Springer-Verlag, Berlin-New York, iv+508 pp, 1972.

\end{thebibliography}

\end{document}