On $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices
%\boldmath A characterization of $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices is described, depending on the notions of {\em distributions}, {\em ingredients} and {\em recipes}. In particular, these notions lead to the establishment of some bounds on the number and distribution of 2-coboundaries over $\Z_t \times \Z _2^2$ to use and the way in which they have to be combined in order to obtain a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix. Exhaustive searches have been performed, so that the table in p. 132 in \cite{BH95} is corrected and completed. A deeper look at the results obtained leads to the definition of some transformations which preserve the $\Z _t \times \Z_2^2$-cocyclic Hadamard character of a matrix, and which give rise to orbits of $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices. This will be explained in a subsequent paper \cite{AGG11}, due to space limitations.
ref3.tex
%\documentstyle{article}
\documentclass{article}

\usepackage{graphicx}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}

%\usepackage[notref,notcite]{showkeys} %used by Warwick

\newcommand{\D}{\displaystyle}
%\newcommand{\mod}{\;mod\;}
%\newcommand{\Z}{{\mathsf{\textstyle Z\kern-0.4em Z}}}
\newcommand{\Z}{{\mathbb Z}}

\newcommand{\proof}{{\em Proof.}}
\newcommand{\finproof}{{\hfill $\Box$}}

\newtheorem{lemma}{\bf Lemma}{}{\rmfamily}
\newtheorem{corollary}{\bf Corollary}{}{\rmfamily}
\newtheorem{example}{Example}{\itshape}{\rmfamily}
\newtheorem{definition}{\bf Definition}{}{\rmfamily}
\newtheorem{proposition}{\bf Proposition}{}{\rmfamily}
\newtheorem{algorithm}{\bf Algorithm}{}{\rmfamily}
\newtheorem{remark}{\bf Remark}{}{\rmfamily}
\newtheorem{theorem}{\bf Theorem}{}{\rmfamily}






\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{On $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices}
%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%

\author{V\'{\i}ctor~\'{A}lvarez\thanks{All authors are partially supported by FEDER funds via the research projects FQM-016 and P07--FQM--02980 from JJAA and MTM2008-06578 from MICINN (Spain).},~%~\IEEEmembership{Member,~IEEE,
%        Jos\'{e}~Andr\'{e}s~Armario,~%\IEEEmembership{Fellow,~OSA,
%        Mar\'{\i}a~Dolores~Frau,~%\IEEEmembership{Fellow,~OSA,
        F\'{e}lix~Gudiel\thanks{V. \'{A}lvarez and F. Gudiel are with the Department
of Applied Mathematics 1, University of Seville, Seville,
Spain. E-mail: \{valvarez,gudiel\}@us.es.},~%\IEEEmembership{Fellow,~OSA,
        and~Maria~Bel\'{e}n~G\"{u}emes\thanks{M.B. G\"{u}emes is with the Department
of Algebra, University of Seville, Seville,
Spain. E-mail: bguemes@us.es.}%,~%\IEEEmembership{Fellow,~OSA,
%        Elena~Mart\'{\i}n,~%\IEEEmembership{Fellow,~OSA,
%        and~Amparo~Osuna%,~\IEEEmembership{Life~Fellow,~IEEE}% <-this % stops a space
% <-this % stops a space
% <-this % stops a space
%\thanks{Manuscript received November 7, 2011}
}%; revised January 11, 2007.


% note the % following the last \IEEEmembership and also \thanks -
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
%
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
%\markboth{IEEE Transactions on Information Theory}%
%{On $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
%
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.




% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2007 IEEE}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark.



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle

%\IEEEpeerreviewmaketitle

\begin{abstract}
%\boldmath
A characterization of $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices is described, depending on the notions of {\em distributions}, {\em ingredients} and {\em recipes}. In particular, these notions lead to the establishment of some bounds on the number and distribution of 2-coboundaries over $\Z_t \times \Z _2^2$ to use and the way in which they have to be combined in order to obtain a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix. Exhaustive searches have been performed, so that the table  in p. 132 in \cite{BH95} is corrected and completed. A deeper look at the results obtained leads to the definition of some transformations which preserve the $\Z _t \times \Z_2^2$-cocyclic Hadamard character of a matrix, and which give rise to orbits of $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices. This will be explained in a subsequent paper \cite{AGG11}, due to space limitations.
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the journal you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals frown on math
% in the abstract anyway.

% Note that keywords are not normally used for peerreview papers.
%\begin{IEEEkeywords}
%Hadamard matrix, cocyclic matrix.\end{IEEEkeywords}






% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
%\IEEEpeerreviewmaketitle



%\section{Introduction}
% The very first letter is a 2 line initial drop letter followed
% by the rest of the first word in caps.
%
% form to use if the first word consists of a single letter:
% \IEEEPARstart{A}{demo} file is ....
%
% form to use if you need the single drop letter followed by
% normal text (unknown if ever used by IEEE):
% \IEEEPARstart{A}{}demo file is ....
%
% Some journals put the first two words in caps:
% \IEEEPARstart{T}{his demo} file is ....
%
% Here we have the typical use of a "T" for an initial drop letter
% and "HIS" in caps to complete the first word.
%\IEEEPARstart{T}{his} demo file is intended to serve as a ``starter file''
%for IEEE journal papers produced under \LaTeX\ using
%IEEEtran.cls version 1.7 and later.
% You must have at least 2 lines in the paragraph with the drop letter
% (should never be an issue)
%I wish you the best of success.
%
%\hfill mds
%
%\hfill January 11, 2007
%
%\subsection{Subsection Heading Here}
%Subsection text here.
%
% needed in second column of first page if using \IEEEpubid
%\IEEEpubidadjcol
%
%\subsubsection{Subsubsection Heading Here}
%Subsubsection text here.
%
%
% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation Results}
%\label{fig_sim}
%\end{figure}

% Note that IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.


% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command, the
% \label for the overall figure must come after \caption.
% \hfil must be used as a separator to get equal spacing.
% The subfigure.sty package works much the same way, except \subfigure is
% used instead of \subfloat.
%
%\begin{figure*}[!t]
%\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
%\label{fig_second_case}}}
%\caption{Simulation results}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.


% An example of a floating table. Note that, for IEEE style tables, the
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


% Note that IEEE does not put floats in the very first column - or typically
% anywhere on the first page for that matter. Also, in-text middle ("here")
% positioning is not used. Most IEEE journals use top floats exclusively.
% Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
% floats. This can be corrected via the \fnbelowfloat command of the
% stfloats package.



\section{Introduction}

%\IEEEPARstart{H}{adamard}
 Hadamard matrices are $n\times n$ square matrices $H$ with entries in $\{1, -1\}$ such that every pair of rows (respectively, columns) are orthogonal, that is, $H  H^T=nI_n$.

Due to this nice combinatorial property, Hadamard matrices have many applications in a wide variety of fields, such as Signal Processing, Coding Theory and Cryptography (see \cite{Hor07} for details). Consequently, there is a real interest in knowing enough Hadamard matrices for practical use.

It is a straightforward exercise to prove that the order of a Hadamard matrix has to be 1, 2 or a multiple of 4 (as soon as three or more rows have to be simultaneously orthogonal one to each other). Unfortunately, the Hadamard Conjecture about the existence of these matrices for every order $4t$ remains unproved since the XIXth Century.

Nowadays, there are three orders less than 1000 for which no Hadamard matrix is known: $668=4 \cdot 167$, $716=4\cdot 179$, and $892=4 \cdot 223$. Furthermore,
there are 10 orders in the range $[1000,2000]$ for which no Hadamard matrix is known (see \cite{Kou} for details).

One of the most promising techniques for constructing Hadamard matrices is the cocyclic approach (see \cite{HdL93,HdL95,Hor07}). A cocyclic matrix $M_f$ over a group $G$ is a matrix $M_f=(f(g,h))$, for $f$ being a $2$-cocycle over $G$, that is, a function $f:G \times G \rightarrow \{1,-1\}$ such that for every $a,b,c \in G$, $f(a,b)\cdot f(ab,c)\cdot f(a,bc) \cdot f(b,c)=1$.

Actually, many well known families of Hadamard matrices, such as Sylvester's, Paley's, Williamson's and Ito's, have shown to be cocyclic over appropiated groups (see \cite{Hor07} for details). This has provided inspiration for the Cocyclic Hadamard Conjecture, which states that cocyclic Hadamard matrices exist for every order $4t$.

In this paper we are interested in characterizing cocyclic Hadamard matrices over $\Z_t \times \Z_2^2$, which include the family of symmetric Williamson Hadamard matrices.

Following the indications of \cite{AAFR08}, we will describe bounds on the number of 2-coboundaries over $\Z_t \times \Z_2^2$ to be combined, as well as their distribution (in terms of what we call {\em ingredients} and {\em recipes}), in order to construct a $\Z_t \times \Z_2^2$-cocyclic Hadamard matrix. A preliminary version of this work can be found in \cite{Gue11}.

This information will allow us to design an exhaustive search for $\Z_t \times \Z_2^2$-cocyclic Hadamard matrices for $3 \leq t \leq 13$, so that the table in p. 132 in \cite{BH95} is corrected and completed.

Taking a deeper insight on the results obtained, some relations seem to play an special role among $\Z_t \times \Z_2^2$-cocyclic Hadamard matrices. These observations have lead to ask some questions, which will be analyzed in a subsequent paper \cite{AGG11}, due to space limitations. In particular, in the second series of these papers we will define four different transformations on $\Z_t \times \Z_2^2$-cocyclic Hadamard matrices which are Hadamard-preserving, so that the set of $\Z_t \times \Z_2^2$-cocyclic Hadamard matrices splits in orbits. Furthermore, the knowledge of just one $\Z_t \times \Z_2^2$-matrix completely characterizes its corresponding orbit. With this information at hand, we have been able to extend the table in p. 132 in \cite{BH95} for values of $t$ in the range $3 \leq t \leq 23$.

%A deeper analysis of the results obtained have permitted to isolate some relations

We organize the paper as follows. Section II is dedicated to describe all about $\Z_t \times \Z_2^2$-cocyclic Hadamard matrices, as it is described in \cite{BH95} and \cite{AAFR08}. In Section III, we introduce the notions of {\em distribution}, {\em ingredients} and {\em recipes}, in terms of which we find some upper and lower bounds on the number of 2-coboundaries over $\Z_t \times \Z_2^2$ which have to be combined in order to get $\Z_t \times \Z_2^2$-cocyclic Hadamard matrices, as well as the way in which they have to be distributed. Section IV is devoted to calculations. Last section is dedicated to conclusions and further work.

\section{$\Z_t \times \Z_2^2$-cocyclic Hadamard matrices}

%In \cite{AAFR09} a basis for 2-cocycles over $\Z_t \times \Z_2^2$ is described.


Consider the group $G=\Z_t \times \Z_2^2=<x,u,v:\; x^t=u^2=v^2=1,uv=vu>$, $t>1$ odd, with ordering $$(x^i,1)<(x^i,u)<(x^i,v)<(x^i,uv), \; 0 \leq i < t, $$ $$(x^i,uv) < (x^{i+1},1), \; 0 \leq i <t-1.$$

A basis ${\cal B}=\{\partial _2,\ldots, \partial _{4t-2},\beta_1,\beta_2,\gamma\}$ for 2-cocycles over $G$ is described in
\cite{AAFR09}, and consists of $4t-3$ coboundaries $\partial _k$, two cocycles $\beta_i$ coming from inflation and one cocycle $\gamma$ coming from
transgression.

In these circumstances, every 2-cocycle over $G$ admits an unique representation as a product of the generators in ${\cal B}$,
$f=f_1^{\alpha_1}\cdots f_k^{\alpha_k}$, $\alpha _i \in \{0,1\}$. The tuple $(\alpha_1,\ldots,\alpha_k)_{\cal B}$ defines the coordinates
of $f$ with regards to ${\cal B}$. Accordingly, every cocyclic matrix $M_f=(f(g_i,g_j))$ for $f=(\alpha_1,\ldots,\alpha_k)_{\cal B}$
admits an unique decomposition as the Hadamard (pointwise) product $M_f=M_{f_1}^{\alpha_1} \cdots  M_{f_k}^{\alpha_k}$.

Let $BN_k$ denote the back negacyclic matrix of size $k\times k$, $$BN_k=\left( \begin{array}{crcr} 1&1&\cdots & 1\\
1&&_{\cdot}\cdot^{\cdot}&-1\\ \vdots&_{\cdot}\cdot^{\cdot}&_{\cdot}\cdot^{\cdot}&\vdots\\ 1&-1&\cdots&-1\end{array} \right)_{k\times k}.$$

The cocyclic matrices coming from
inflation may be described in terms of back negacyclic matrices, so that $M_{\beta _1}=1_{2t} \otimes BN_2$ and $M_{\beta_2}=1_t \otimes
BN_2\otimes 1_2$. Here we use $A\otimes B$ for denoting the usual Kronecker product of matrices, that is, the block
matrix whose blocks are $a_{ij}B$.

The transgression cocyclic matrix $M_{\gamma}$ is $M_{\gamma}= 1_t \otimes \left(\begin{array}{crcr}1&1&1&1\\1&1&1&1 \\1&-1&1&-1\\1&-1&1&-1
\end{array}\right)$.

It has been observed that cocyclic Hadamard matrices over $\Z _t \times \Z_2^2$ mostly use all the three representative cocycles
$\beta_1,\beta_2$ and $\gamma$ simultaneously (see \cite{BH95} for details). We will assume that every cocyclic matrix $M$ is obtained as
a product $M=M_{\partial_{i_1}} \ldots M_{\partial_{i_w}}\cdot R$ for $R=1_t \otimes
 \left(\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1 \\1&-1&-1&1\\1&1&-1&-1
\end{array}\right)$ and  $2 \leq i_1 < \ldots <i_w \leq 4t-2$, where $R=M_{\beta_1} \cdot M_{\beta_2} \cdot M_{\gamma}$.








As usual, $\partial _i$ refers to the coboundary associated to the $i^{th}$-element in $G$. The corresponding matrices $M_{\partial_i}$ are
 $4\times 4$-block back diagonal square matrices of size $4t$, starting from the $\lceil \frac{i}{4} \rceil ^{th}$-column:
$$\hspace*{.25cm} \stackrel{\lceil \frac{i}{4} \rceil}{} $$ $$M_{\partial_i}=\left(
\begin{array}{cccccc} &&A_{[i]_4}&&&\\ &_{\cdot}\cdot^{\cdot}&&&&\\ A_{[i]_4}&&&&&\\&&&&&A_{[i]_4}\\
&&&&_{\cdot}\cdot^{\cdot}&\\ &&&A_{[i]_4}&&
\end{array}\right)$$
with the $i^{th}$-row and the $i^{th}$-column negated. Here we adopt the notation $[m]_n$ instead of $m \mod n$ for brevity.


%Here the coset of $i$ modulo 4 is simply denoted by $[i]_4$ for brevity.
The $4\times 4$-blocks $A_{[i]_4}$ depend on the coset of $i$ modulo $4$, as follows: $$A_0=\left( \begin{array}{rrrr} &&&- \\ &&-&\\
&-&& \\-&&& \end{array}\right), A_1=\left( \begin{array}{rrrr} -&&& \\ &-&&\\ &&-& \\&&&- \end{array}\right),$$ $$  A_2=\left(
\begin{array}{rrrr} &-&& \\ -&&&\\ &&&- \\&&-& \end{array}\right),  A_3=\left( \begin{array}{rrrr} &&-& \\ &&&-\\ -&&& \\&-&&
\end{array}\right).$$

Negating the $i^{th}$-row gives a matrix with exactly two negative entries in each row, excepting the first one (consisting only of 1s). More concretely, the negative entries in the row $s\neq 1$ are located at the columns $i$ and $e$, where $g_e=g_s^{-1}g_i$. This matrix is termed a {\em generalized} coboundary matrix in \cite{AAFR08}.

In particular, there are three coboundary matrices which are not in ${\cal B}$: $M_{\partial _1}$, $M_{\partial _{4t-1}}$ and $M_{\partial _{4t}}$. It may be checked that:

%\begin{itemize}

%\item $
\begin{equation} \label{borde1} M_{\partial _1}= \D -\prod _{i=1}^{t-1} M_{\partial _{4i+1}}\prod _{i=0}^{t-1} M_{\partial _{4i+2}}. \end{equation}

%\item $
\begin{equation}\label{borde3} M_{\partial _{4t-1}}= \D \prod _{i=0}^{t-2} M_{\partial _{4i+3}}\prod _{i=0}^{t-1} M_{\partial _{4i+2}}.\end{equation}

%\item $
\begin{equation}\label{borde4} M_{\partial _{4t}}= \D \prod _{i=1}^{t-1} M_{\partial _{4i}}\prod _{i=0}^{t-1} M_{\partial _{4i+2}}.\end{equation}

%\end{itemize}

Consequently, every $\Z _t \times \Z_2^2$-cocyclic matrix $M_f$ using $R$ may be expressed as a pointwise product of matrices in $\{ M_{\partial _1},\ldots ,M_{\partial _{4t}}\}$ in 8 different ways,  just one of which does not use neither of $M_{\partial _1}$, $M_{\partial _{4t-1}}$ and $M_{\partial _{4t}}$ (and gives precisely the expression of $M_f$ as a linear combination of elements in ${\cal B}$). Actually, suppose that $M_f= \D R\cdot \prod _{k=1}^4 \prod _{i_j \in J_k} M_{\partial_{i_j}}$, where $J_k \subset \{1, \ldots, 4t\}$ is a subset of indexes which are congruent to $k$ modulo 4. Then $M_f$ may be expressed as the pointwise product of the coboundary matrices of indexes belonging to any of the following 8 subsets: $(J_1,J_2,J_3,J_4)$, $(\bar{J_1},\bar{J_2},J_3,J_4)$, $(J_1,\bar{J_2},\bar{J_3},J_4)$, $(J_1,\bar{J_2},J_3,\bar{J_4})$, $(\bar{J_1},J_2,\bar{J_3},J_4)$, $(\bar{J_1},J_2,J_3,\bar{J_4})$, $(J_1,J_2,\bar{J_3},\bar{J_4})$, $(\bar{J_1},\bar{J_2},\bar{J_3},\bar{J_4})$, where $\bar{J_k}=\{k+4i: 0 \leq i \leq t-1\} \backslash J_k$ denotes the complementary subset of $J_k$.


It is known that a cocyclic matrix is Hadamard if and only if the summation of each row but the first is zero (this is the cocyclic Hadamard test, see \cite{HdL95,BH95} for instance). Furthermore, following the proof of this fact, it is easy to prove that the summation of the row corresponding to  $g_i$ is zero if and only if the summation of the row corresponding to $g_i^{-1}$ is zero as well.

Consequently, the summation of the row $n$ of a $\Z _t \times \Z_2^2$-cocyclic matrix is zero if and only if the summation of the row $4t+4-4 \lceil \frac{n}{4}\rceil+ 1+[n-1 \mod 4]$ is zero as well, for $5 \leq n \leq 2t+2$.

Furthermore, as proved in \cite{AAFR08}, the summation of each of the second, third and fourth rows is always zero.

This way, a $\Z _t \times \Z_2^2$-cocyclic matrix is Hadamard if and only if the summation of each of the rows from 5 to $2t+2$ is 0.

In \cite{AAFR08}, an equivalent characterization of the cocyclic Hadamard test is described in terms of {\em paths} and {\em intersections}.

A set $\{M_{\partial_{i_j}}: \; 1 \leq j \leq w\}$ of generalized coboundary matrices defines a {\em $n$-walk} if these
matrices may be ordered in a sequence $(M_{l_1},\ldots,M_{l_w})$ so that consecutive matrices $M_{l_i}$ and $M_{l_{i+1}}$ share a negative entry at the
$n^{th}$-row, precisely at the position $(n,l_{i+1})$, $1 \leq i \leq w-1$. Such a walk is called a {\em path} if the initial (equivalently, the final) matrix shares a $-1$ entry with a generalized
coboundary matrix which is not in the walk itself, and a {\em cycle} otherwise.

With this notation at hand, the summation of the $n^{th}$-row of a matrix $M_{\partial_{i_1}}\ldots M_{\partial_{i_w}} \cdot R$ is zero if and only if $2c_n+r_n-2I_n=2t$, where $c_n$  is the number of maximal $n$-paths in $\{M_{\partial_{i_1}},\ldots,M_{\partial_{i_w}}\}$, $r_n$ is the number of
$-1$s in the $n^{th}$-row of $R$ and $I_n$ is the number of positions in which $R$ and $M_{\partial_{i_1}}\ldots M_{\partial_{i_w}}$ share a common $-1$
in their $n^{th}$-row (obviously, $0\leq I_n \leq r_n$).

\begin{corollary}\label{corolario1} In particular, for  $\Z _t \times \Z_2^2$-cocyclic matrices:

\begin{enumerate}

\item the summation of a row $n \equiv 1 \mod 4$ is zero if and only if \begin{equation}\label{filahadamard1} c_n=t, \end{equation}

\item the summation of a row $n \equiv 0,2,3 \mod 4$ is zero if and only if \begin{equation}\label{filahadamard2} c_n=I_n. \end{equation}

\end{enumerate}
\end{corollary}

%In particular, the summation of a row $n \equiv 1 \mod 4$ is zero if and only if $c_n=t$. On the other hand, the summation of a row $n \equiv 0,2,3 \mod 4$ is zero if and only if $c_n=I_n$.

In the following section we analyze the number $c_n$ of $n$-paths of a $\Z _t \times \Z_2^2$-cocyclic matrix. Focusing in rows $n \equiv 1 \mod 4$, we will obtain upper and lower bounds on the number of coboundaries to combine in order to get a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix. Furthermore, we will characterize the distribution of these coboundaries in terms of {\em ingredients} and {\em recipes}.

\section{Distributions, ingredients and recipes}

Firstly, we analyze the way in which $n$-paths are generated on $\Z _t \times \Z_2^2$-cocyclic matrices, depending on the value of $n$ modulo $4$.

\begin{lemma} \label{lema1} Characterization of $n$-paths of coboundaries on $\Z _t \times \Z_2^2$-cocyclic matrices:
\begin{enumerate}
\item If $n \equiv 1 \mod 4$,  $M_{\partial _{i-n+1}}$  forms an $n$-path with $M_{\partial _i}$.

\item If $n \equiv 2 \mod 4$,  $M_{\partial _{i-n+2-(-1)^i}}$  forms an $n$-path with $M_{\partial _i}$.

\item If $n \equiv 3 \mod 4$, $M_{\partial _{i-n+3-2(-1)^{\lceil \frac{i \mod 4}{2} \rceil}}}$ forms an $n$-path with $M_{\partial _i}$.

\item If $n \equiv 0 \mod 4$, $M_{\partial _{i-n+4+(-1)^i(1-4(1-\lfloor \frac{i  \mod 4}{2} \rfloor))}}$ forms an $n$-path with $M_{\partial _i}$.

\end{enumerate}
\end{lemma}

\proof

This may be checked by direct inspection.

\finproof

\begin{corollary} \label{corolariociclos}
In particular, the set of coboundaries $\{ \partial _1, \ldots ,\partial _{4t}\}$ splits into four $5$-cycles of length $t$, $$[\partial _{4t-3}, \partial  _{4t-7}, \ldots , \partial _5, \partial _1], \qquad [\partial _{4t-2}, \partial _{4t-6}, \ldots , \partial _6, \partial _2],$$ $$[\partial _{4t-1}, \partial _{4t-5}, \ldots , \partial _7, \partial _3], \qquad [\partial _{4t}, \partial _{4t-4}, \ldots , \partial _8, \partial _4],$$
\end{corollary}

Now we focus our attention on rows $n \equiv 1 \mod 4$.
From Lemma \ref{lema1}, it is apparent that $n$-paths consists of groups of coboundaries in the same coset modulo 4.

\begin{lemma} \label{lema2}
Given $ 1 \leq i \neq j \leq 4t$, $i \equiv j \mod 4$, there exists one and only one row $n$, $5 \leq n \leq 2t+2$, $n \equiv 1 \mod 4$, such that $M_{\partial _i}$ and $M_{\partial _j}$ form an $n$-path.
\end{lemma}

\begin{corollary}
Along the $\frac{t-1}{2}$ rows $n \equiv 1 \mod 4$, $5 \leq n \leq 2t+2$, any $k$ coboundaries $\partial _{i_1}, \ldots ,\partial _{i_k}$ in the same coset modulo 4 give rise to a total amount of $\frac{k(t-k)}{2}$ paths.
\end{corollary}

\proof

Along the $\frac{t-1}{2}$ rows $n \equiv 1 \mod 4$, $5 \leq n \leq 2t+2$, any $k$ coboundaries $\partial _{i_1}, \ldots ,\partial _{i_k}$ in the same coset modulo 4 might give rise to $k \frac{t-1}{2}$ paths. Actually, this is not the case, since we know from Lemma \ref{lema2} that every pair of such coboundaries forms a path at one and only one of these rows $n$. Thus the total amount of paths has to be reduced in the number of pairs in which the $k$ coboundaries may be grouped. This gives $k \frac{t-1}{2}- \frac{k(k-1)}{2}=k \frac{t-k}{2}$, as claimed.

\finproof

Table \ref{tabla1} shows the total amount $\frac{k(t-k)}{2}$ of paths produced by $k$ coboundaries in the same coset modulo 4, for odd values of $t$.

\begin{table}[!t]\renewcommand{\arraystretch}{1.3}\caption{Paths produced from $k$ coboundaries in rows $n \equiv 1 \mod 4$.}\label{tabla1}\centering
$\begin{array}{ccccc|ccccc|l} &&&&1&1&&&&&t=3\\ \hline &&&2&3&3&2&&&&t=5\\ \hline &&3&5&6&6&5&3&&&t=7\\ \hline &4&7&9&10&10&9&7&4&&t=9\\ \hline 5&9&12&14&15&15&14&12&9&5&t=11\\  \hline \vdots&&&&\vdots&\vdots&&&&\vdots&\\ \hline \hline  t-1&&&&\frac{t+1}{2}&\frac{t-1}{2}&&&&1&k\\ \hline \end{array}$
\end{table}

%\begin{table}[!t]\renewcommand{\arraystretch}{1.3}\caption{Number of paths produced from $k$ coboundaries in rows $n \equiv 1 \mod 4$.}\label{tabla1}\centering
%$\begin{array}{ccccccc|ccccccc|l} &&&&&&1&1&&&&&&&t=3\\ \hline &&&&&2&3&3&2&&&&&&t=5\\ \hline &&&&3&5&6&6&5&3&&&&&t=7\\ \hline &&&4&7&9&10&10&9&7&4&&&&t=9\\ \hline &&5&9&12&14&15&15&14&12&9&5&&&t=11\\  \hline &6&11&15&18&20&21&21&20&18&15&11&6&&t=13\\ \hline 7&13&18&22&25&27&28&28&27&25&22&18&13&7&t=15\\ \hline \vdots&&&&&&\vdots&\vdots&&&&&&\vdots&\\ \hline \hline  t-1&&&&&&\frac{t+1}{2}&\frac{t-1}{2}&&&&&&1&k\\ \hline \end{array}$
%\end{table}

%This table has many valuable combinatorial properties.

\begin{proposition}\label{proposicion1} Table \ref{tabla1} has many valuable combinatorial properties:

\begin{enumerate}

\item The table is symmetric.

\item The numbers in the central columns are triangular numbers, of the type $\frac{n(n+1)}{2}$.

\item Subtracting from a number in the central columns any of the numbers of the same row, gives as result a triangular number as well.

\item Reciprocally, subtracting from a number in the central columns any triangular number gives as result a number of the same row.

\end{enumerate}

\end{proposition}

\proof

\begin{enumerate}

\item The table is symmetric, since $k$ coboundaries give rise to $\frac{k(t-k)}{2}$ paths, exactly the same amount of paths produced by $t-k$ coboundaries, $\frac{(t-k)k}{2}$.

\item The numbers in the central columns are triangular numbers. Actually, $\frac{t-1}{2}$ coboundaries give rise to $\frac{\frac{t-1}{2}\cdot \frac{t+1}{2}}{2}=\frac{t^2-1}{8}$ paths.

\item Subtracting from a number in the central columns any of the numbers of the same row, gives as result a triangular number as well. Indeed, subtracting $\frac{k(t-k)}{2}$ paths from $\frac{t^2-1}{8}$ gives $\frac{t^2-1-4kt+4k^2}{8}=\frac{(t-2k)^2-1}{8}=\frac{\frac{t-2k-1}{2}\cdot \frac{t-2k+1}{2}}{2}.$

\item The argument above fits here as well.

\end{enumerate}

\finproof

Attending to the condition (\ref{filahadamard1}), in order to get a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix, a necessary (but not sufficient!) condition is to select $k_i$ coboundaries in the coset $i \mod 4$, such that there is a total amount of $t\frac{t-1}{2}$ paths along the $\frac{t-1}{2}$ rows $n \equiv 1 \mod 4$, $5 \leq n \leq 2t+2$. This motivates the following definition.

\begin{definition}\label{definicion1}
A {\em distribution} is an ordered tuple $(\frac{k_0(t-k_0)}{2},\frac{k_1(t-k_1)}{2},\frac{k_2(t-k_2)}{2},\frac{k_3(t-k_3)}{2})$, $0 \leq k_j% \leq k_2 \leq k_1
\leq k_i \leq \frac{t-1}{2}$ for $j \geq i$, such that \begin{equation}\label{ecuacionfila1} \sum _{i=0}^3 \frac{k_i(t-k_i)}{2}=\frac{t(t-1)}{2}.\end{equation}
\end{definition}

\begin{proposition} \label{proposicion2}
For any odd $t$, there always exists at least one distribution $(\frac{k_0(t-k_0)}{2},\frac{k_1(t-k_1)}{2},\frac{k_2(t-k_2)}{2},\frac{k_3(t-k_3)}{2})$.
\end{proposition}

\proof

%We want to prove that there exist a tuple $(k_0,k_1,k_2,k_3)$ such that condition (\ref{ecuacionfila1}) holds.

The maximum possible number of paths is $4 \frac{t^2-1}{8}=\frac{t^2-1}{2}$, obtained when $k_0=k_1=k_2=k_3= \frac{t-1}{2}$, so that the relation (\ref{ecuacionfila1}) fails to hold by a difference $m=\frac{t^2-1}{2}-\frac{t(t-1)}{2}$.

%Consider the difference $m=\frac{t^2-1}{2}-\frac{t(t-1)}{2}=\frac{t-1}{2}$, which is the number of paths to subtract.

In 1796 Gauss proved that any positive integer can be decomposed as the summation of three (not necessarily different) triangular numbers, some of which may be eventually zero. Consequently, there exist three triangular numbers $0 \leq t_1,t_2,t_3 \leq \frac{t^2-1}{8}$ such that $m=t_1+t_2+t_3$.

Thus $\frac{t^2-1}{2}=4 \frac{t^2-1}{8}-m=\frac{t^2-1}{8}+(\frac{t^2-1}{8}-t_1)+(\frac{t^2-1}{8}-t_2)+(\frac{t^2-1}{8}-t_3)$. Taking into account Proposition \ref{proposicion1}, there exist integers $0 \leq k_3 \leq k_2\leq k_1 \leq \frac{t-1}{2}$ such that  $(\frac{t^2-1}{8}-t_i)=\frac{k_i(t-k_i)}{2}$, and therefore $(\frac{t^2-1}{8},\frac{k_1(t-k_1)}{2},\frac{k_2(t-k_2)}{2},\frac{k_3(t-k_3)}{2})$ is a distribution, in the sense of Definition \ref{definicion1}.

\finproof

\begin{proposition} \label{proposicion3} Furthermore, there are as many different distributions as many different decompositions of $\frac{t-1}{2}$ as the summation of four triangular numbers.
\end{proposition}

\proof

This is a straightforward consequence of the argument explained in the proof of Proposition \ref{proposicion2}.

\finproof

Propositions \ref{proposicion2} and \ref{proposicion3} give a method for finding the set of distributions for a given $t$, in terms of decompositions of $\frac{t-1}{2}$ as the summation of four triangular numbers $0 \leq t_0 \leq t_1\leq t_2 \leq t_3 \leq \frac{t^2-1}{8}$.

\begin{proposition} \label{generadistribucion}
Let $k$ be a positive integer. Then:
\begin{enumerate}

\item $k$ is a triangular number if and only if $\frac{-1+\sqrt{1+8k}}{2}$ is an integer.

\item The greatest triangular number less or equal to $k$ is $t_n$, for $n=\lfloor \frac{-1+\sqrt{1+8k}}{2}\rfloor$.

\item If $k$ is decomposed as the summation of $m$ triangular numbers $t_{i_j}$, $1\leq j \leq m$, then $\D \max _j \{t_{i_j}\} \geq t_n $, for $n=\lceil \frac{-1+\sqrt{1+8\frac{k}{m}}}{2} \rceil$.

\end{enumerate}
\end{proposition}

\proof

It suffices to notice that $k$ is a triangular number if and only if there exists an integer $n$ such that $t_n=n \frac{n+1}{2}=k$. Equivalently, if and only if the equation $\frac{n^2}{2}+\frac{n}{2}-k$ has a positive integer solution (which, a fortiori, is $\frac{-1+\sqrt{1+8k}}{2}$).

\finproof

Proposition \ref{generadistribucion} leads straightforwardly to the following algorithm for constructing the full set of distributions for a given $t$.

\begin{algorithm}\label{algoritmo1} Constructing the set of distributions for $t$.\\

{\small
\noindent {\sc Input:} $t$\\
\\
$k=\{ \; \}$\\
for $i_1$ from $\lceil \frac{-1+\sqrt{t}}{2}\rceil $ to $\lfloor \frac{-1+\sqrt{4t-3}}{2} \rfloor$ do\\
\hspace*{.25cm}for $i_2$ from $\lceil \frac{-1+\sqrt{1+4\frac{t-1-i_1(i_1+1)}{3}}}{2}\rceil $ to\\
\hspace*{.25cm}$\min (i_1,\lfloor \frac{-1+\sqrt{1+4(t-1-i_1(i_1+1))}}{2} \rfloor )$ do\\
\hspace*{.5cm}for $i_3$ from $\lceil \frac{-1+\sqrt{1+2(t-1-i_1(i_1+1)-i_2(i_2+1))}}{2}\rceil $\\
 \hspace*{.5cm} to $\min (i_2,\lfloor \frac{-1+\sqrt{1+4(t-1-i_1(i_1+1)-i_2(i_2+1))}}{2} \rfloor )$\\
\hspace*{.5cm}  do\\
\hspace*{.75cm}  $x=\frac{-1+\sqrt{1+4(t-1-i_1(i_1+1)-i_2(i_2+1)-i_3(i_3+1))}}{2}$\\
\hspace*{.75cm} if $x$ is an integer, then $k= k \cup \{ (x,i_3,i_2,i_1) \}$ fi\\
\hspace*{.5cm} od\\
\hspace*{.25cm} od\\
od\\
$l=\{\;\}$\\
for $i$ from 1 to $length(k)$ do\\
\hspace*{.25cm} $l=l \cup \{ (\frac{t^2-1}{8}-k_{i,1},\frac{t^2-1}{8}-k_{i,2},\frac{t^2-1}{8}-k_{i,3},\frac{t^2-1}{8}-k_{i,4}) \}$\\
od\\
\\
{\sc Output:} $l$\\
}

\end{algorithm}

Table \ref{tabla2} shows the complete set of distributions obtained from Algorithm \ref{algoritmo1}, for $3\leq t \leq 25$.

\begin{table}[!t]\renewcommand{\arraystretch}{1.3}\caption{Distributions in terms of decompositions of $\frac{t-1}{2}=t_0+t_1+t_2+t_3$.}\label{tabla2}\centering
$\begin{array}{c|c|c|c} t&\frac{t(t-1)}{2}& distributions& t_0+t_1+t_2+t_3=\frac{t-1}{2}\\ \hline 3&3&(1,1,1,0)& 0+0+0+1=1\\ \hline
5&10&(3,3,2,2)&0+0+1+1=2\\ \hline 7&21& \begin{array}{c} (6,6,6,3)\\ (6,5,5,5)\end{array}& \begin{array}{c} 0+0+0+3=3\\ 0+1+1+1=3\end{array}\\ \hline
9&36& \begin{array}{c} (10,10,9,7)\\ (9,9,9,9)\end{array}& \begin{array}{c} 0+0+1+3=4\\ 1+1+1+1=4\end{array}\\ \hline
11&55&  (15,14,14,12)& 0+1+1+3=5\\ \hline
13&78& \begin{array}{c} (21,21,21,15)\\ (21,21,18,18)\\ (20,20,20,18)\end{array}& \begin{array}{c} 0+0+0+6=6\\ 0+0+3+3=6\\ 1+1+1+3=6\end{array}\\ \hline
15&105& \begin{array}{c} (28,28,27,22)\\ (28,27,25,25)\end{array}& \begin{array}{c} 0+0+1+6=7\\ 0+1+3+3=7\end{array}\\ \hline
17&136& \begin{array}{c} (36,35,35,30)\\ (35,35,33,33)\end{array}& \begin{array}{c} 0+1+1+6=8\\ 1+1+3+3=8\end{array}\\ \hline
19&171& \begin{array}{c} (45,45,42,39)\\ (45,42,42,42)\\ (44,44,44,39)\end{array}& \begin{array}{c} 0+0+3+6=9\\ 0+3+3+3=9\\ 1+1+1+6=9 \end{array}\\ \hline
21&210& \begin{array}{c} (55,55,55,45)\\ (55,54,52,49)\\ (54,52,52,52)\end{array}& \begin{array}{c} 0+0+0+10=10\\ 0+1+3+6=10\\ 1+3+3+3=10\end{array}\\ \hline
23&253& \begin{array}{c} (66,66,65,56)\\ (65,65,63,60)\end{array}& \begin{array}{c} 0+0+1+10=11\\ 1+1+3+6=11\end{array}\\ \hline
25&300& \begin{array}{c} (78,78,72,72)\\ (78,77,77,68)\\ (78,75,75,73)\\ (75,75,75,75)\end{array}& \begin{array}{c} 0+0+6+6=12\\ 0+1+1+10=12\\ 0+3+3+6=12\\ 3+3+3+3=12\end{array}\\
 \hline
\end{array}$
\end{table}

Notice that the knowledge of the full set of distributions implies the knowledge about the number of coboundaries which have to be used in order to get a
$\Z _t \times \Z_2^2$-cocyclic Hadamard matrix, since each summand $\frac{k_i(t-k_i)}{2}$ is in one to one correspondence to the values $k_i$ and $t-k_i$ (see Table \ref{tabla1}). In spite of this fact, we may bound the number of coboundaries to be combined a bit further.

\begin{proposition} \label{proposicion4}
Let $(\frac{k_0(t-k_0)}{2},\frac{k_1(t-k_1)}{2},\frac{k_2(t-k_2)}{2},\frac{k_3(t-k_3)}{2})$ be a distribution. Call $n=k_0+k_1+k_2+k_3$. Then

\begin{enumerate}

\item
\begin{equation}\label{cotacob1} \lceil \frac{t-\sqrt{4t-3}}{2}\rceil \leq k_3 \leq \lfloor \frac{t+\sqrt{4t-3}}{2}\rfloor . \end{equation}

\item
\begin{equation}\label{cotacob2} \lceil 2(t-\sqrt{t})\rceil \leq n \leq \lfloor 2(t+\sqrt{t})\rfloor . \end{equation}

\end{enumerate}
\end{proposition}

\proof

Let $(k_0,k_1,k_2,k_3)$ generate a distribution $(\frac{k_0(t-k_0)}{2},\frac{k_1(t-k_1)}{2},\frac{k_2(t-k_2)}{2},\frac{k_3(t-k_3)}{2})$.

On one hand, attending to condition (\ref{ecuacionfila1}), necessarily $$\frac{t(t-1)}{2}-3 \frac{t^2-1}{8} \leq \frac{k_3(t-k_3)}{2}.$$ Simplifying this expression, we get $$4k_3^2-4k_3t+t^2-4t+3 \leq 0 \Leftrightarrow$$ $$ \Leftrightarrow\lceil \frac{t-\sqrt{4t-3}}{2}\rceil \leq k_3 \leq \lfloor \frac{t+\sqrt{4t-3}}{2}\rfloor ,$$ which proves (\ref{cotacob1}).

On the other hand, simplifying (\ref{ecuacionfila1}), we get $$\D t \sum _{i=0}^3k_i-t^2+t=\sum _{i=0}^3k_i^2.$$ Call $\D n=\sum _{i=0}^3k_i$. Since \begin{equation}\label{repartohom} \D \sum _{i=0}^3k_i^2 \geq \sum _{i=0}^3(\frac{n}{4})^2, \end{equation} we get $$\D tn-t^2+t \geq \frac{n^2}{4} \Leftrightarrow $$ $$\Leftrightarrow \lceil 2(t-\sqrt{t})\rceil \leq n \leq \lfloor 2(t+\sqrt{t})\rfloor ,$$ as stated in (\ref{cotacob2}).

\finproof

\begin{remark} \label{nota1}
Condition $(\ref{cotacob2})$ may be tightened, depending on the coset of $n=k_0+k_1+k_2+k_3$ modulo 4, substituting the lower bound in (\ref{repartohom}) by the most homogeneously distributed partition of $n$ into four parts:

\begin{itemize}

\item If $n\equiv 0 \mod 4$, $\D \sum _{i=0}^3k_i^2 \geq 4(\frac{n}{4})^2$, so that
$$\lceil 2(t-\sqrt{t})\rceil \leq n \leq \lfloor 2(t+\sqrt{t})\rfloor .$$

\item If $n\equiv 1 \mod 4$, $\D \sum _{i=0}^3k_i^2 \geq 3(\frac{n-1}{4})^2+(\frac{n+3}{4})^2$, so that
$$ \lceil 2(t-\sqrt{t-\frac{3}{4}})\rceil \leq n \leq \lfloor 2(t+\sqrt{t-\frac{3}{4}})\rfloor .$$


\item If $n\equiv 2 \mod 4$, $\D \sum _{i=0}^3k_i^2 \geq 2(\frac{n-2}{4})^2+2(\frac{n+2}{4})^2$, so that
$$ \lceil 2(t-\sqrt{t-1})\rceil \leq n \leq \lfloor 2(t+\sqrt{t-1})\rfloor .$$

\item If $n\equiv 3 \mod 4$, $\D \sum _{i=0}^3k_i^2 \geq (\frac{n-3}{4})^2+3(\frac{n+1}{4})^2$, so that
$$ \lceil 2(t-\sqrt{t-\frac{3}{4}})\rceil \leq n \leq \lfloor 2(t+\sqrt{t-\frac{3}{4}})\rfloor .$$

\end{itemize}
\end{remark}

\begin{figure}[!t] \label{areas} \includegraphics[width=50mm]{areas.eps} \centering \caption{Visual trace of the relation $n_1^2+n_2^2\geq 2(\frac{n_1+n_2}{2})^2$.}\end{figure}

\begin{remark}

In spite of the fact that one may be immediately convinced about the validity of the condition (\ref{repartohom}), and its variants in Remark \ref{nota1}, actually these relations cannot be proved so easily. Although we are not going to prove these relations rigourously here, since this is out of the scope of the paper, we will however give a visual trace of this fact for the case of two summands.

Actually, given an integer $n$, it is apparent that for every decomposition of $n$ into two summands, say $n=n_1+n_2$, the area obtained by the summation of the squares of sides $n_1$ and $n_2$ is greater than or equal to twice the area of the square of side $\frac{n}{2}$, as Fig. 1 %\ref{areas}
illustrates.

The argument above would straightforwardly fit to prove the more general case. In fact, one could check that \begin{equation} \sum _{i=1}^k n_i^2-\frac{1}{k} \left( \sum _{i=1}^k n_i\right) ^2 = \frac{1}{k} \sum _{1 \leq j <i \leq k} (n_i-n_j)^2\geq 0. \end{equation}

\end{remark}

\begin{remark}

The bounds in Proposition \ref{proposicion4} are very tight, as it have been checked experimentally. The first gap occurs for $t=71$, and consists in just one coboundary.

\end{remark}

Once we know that a distribution is available for a given value of $t$, the next step is looking for appropriated subsets of $n_i$ coboundaries in the cosets $i \mod 4$ in ${\cal B}$ such that the amount of $n$-paths along rows $n \equiv 1 \mod 4$, $5 \leq n \leq 2t-1$ fits that distribution.

\begin{definition} An {\em ingredient} produced by a subset of $m$ coboundaries in ${\cal B}$ in the same coset modulo 4 is the column vector whose entries are the number of $n$-paths produced by these $m$ coboundaries along rows $n \equiv 1 \mod 4$, $5 \leq n \leq 2t-1$. A {\em recipe} is a collection of 4 ingredients (one for each different coset $i$ modulo 4), arranged as a matrix of 4 columns, such that the sum of each of the rows is $t$.   \end{definition}

Consequently, if a subset of $\{n_1,n_2,n_3,n_4\}$ coboundaries in ${\cal B}$ defines a recipe, this subset of coboundaries satisfies the condition (\ref{filahadamard1}), and therefore the summation of each of the rows $n \equiv 1 \mod 4$, $5 \leq n \leq 2t-1$ is zero.

\begin{proposition}
The notion of recipe does not depend on the order of its ingredients.
\end{proposition}

\proof

Attending to Lemma \ref{lema1}, $\partial _i$ forms an $n$-path with $\partial _{i-n+1}$, independently on the coset $i \mod 4$, for $n \equiv 1 \mod 4$, $5 \leq n \leq 2t-1$. In particular, $n$-paths are constructed from those coboundaries in ${\cal B}$ in the same coset $\mod 4$, which differ in $\frac{n-1}{4}$ positions in the cycles of Corollary \ref{corolariociclos}.

This way, if a subset of coboundaries of the coset $i \mod 4$ produces an ingredient, the same ingredient is produced by the translation of this subset to any other coset $j \mod 4$.

Eventually, this translation could produce a coboundary $\partial _i$ which is not in ${\cal B}$. This is not a source of difficulties, since from the relations $(\ref{borde1})$, $(\ref{borde3})$ and $(\ref{borde4})$, such prohibited subsets of coboundaries may be substituted by their complements in the cycles of Corollary \ref{corolariociclos}. Since the substitution of any amount of paths by their complementary in a cycle does not change the total amount of paths, this operation preserves the ingredient.

\finproof

Finding a recipe is the first step in the process of constructing a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix, since any subset of coboundaries in ${\cal B}$ defining a recipe satisfies condition (\ref{filahadamard1}). The following proposition gives a condition about when the relation (\ref{filahadamard2}) is also satisfied (and hence a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix has been found).

\begin{proposition}
A subset of coboundaries in ${\cal B}$ satisfies (\ref{filahadamard2}) (i.e. the summation of the $n^{th}$-row is zero, for $n\equiv 0,2,3 \mod 4$, $6 \leq n \leq 2t+2$),  if and only if the number of $n$-paths of length even is itself even, half of them starting and ending with cobundaries in cosets $i_1,i_2 \mod 4$, the other half starting and ending in coboundaries in cosets $i_3,i_4 \mod 4$, $i_j \neq i_k$ for $j \neq k$.
\end{proposition}

\proof

As we commented in Section II, we are using $R=1_t \otimes
 \left(\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1 \\1&-1&-1&1\\1&1&-1&-1
\end{array}\right)$ as the matrix coming from representative cocycles.

Consequently, intersections in rows $n \equiv 2 \mod 4$ can occur in positions $(n,i)$, for $i \equiv 2,0 \mod 4$. Similarly, intersections in rows $n \equiv 3 \mod 4$ can occur in positions $(n,i)$, for $i \equiv 2,3 \mod 4$. Finally, intersections in rows $n \equiv 0 \mod 4$ can occur in positions $(n,i)$, for $i \equiv 3,0 \mod 4$.

Taking into account Lemma \ref{lema1}, it follows that $n$-paths consists in properly alternating coboundaries in:

\begin{itemize}

\item Either cosets $(1,2) \mod 4$, either cosets $(3,0) \mod 4$, for $n \equiv 2 \mod 4$.

\item Either cosets $(2,0) \mod 4$, either cosets $(1,3) \mod 4$, for $n \equiv 3 \mod 4$.

\item Either cosets $(2,3) \mod 4$, either cosets $(1,0) \mod 4$, for $n \equiv 0 \mod 4$.

\end{itemize}

Hence any $n$-path of odd length produces exactly one intersection (i.e. shares exactly one negative entry) with $R$ at the $n^{th}$-row. On the other hand, $n$-paths of even length produces either 2 or 0 intersections, depending on the cosets modulo 4 of $n$ and the initial coboundary of the $n$-path. More precisely:

\begin{itemize}

\item If $n\equiv 2 \mod 4$, then an $n$-path of even length will produce two intersections at the $n^{th}$-row if and only if the coset $i$ of the initial coboundary is $i \equiv 2,0 \mod 4$.

\item If $n\equiv 3 \mod 4$, then an $n$-path of even length will produce two intersections at the $n^{th}$-row if and only if the coset $i$ of the initial  coboundary is $i \equiv 2,3 \mod 4$.


\item If $n\equiv 0 \mod 4$, then an $n$-path of even length will produce two intersections at the $n^{th}$-row if and only if the coset $i$ of the initial  coboundary is $i \equiv 3,0 \mod 4$.


\end{itemize}

Summing up, odd $n$-paths produces 1 intersection, and even $n$-paths produces either 2 or 0 intersections. Hence, the only circumstance in which the amounts of intersections and $n$-paths both coincide is precisely when half the even $n$-paths give rise to 2 intersections, whereas the remaining half of even $n$-paths do not produce any intersections at all, as stated.

\finproof

Now it is straightforward to design an algorithm searching exhaustively for $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices for odd $t$.

\begin{algorithm} \label{algoritmo2} Exhaustive search for $\Z _t \times \Z_2^2$-Hadamard matrices.\\
\\
{\small
{\sc Input:} $t$.\\
\\
Calculate the valid distributions for $t$.\\
Calculate all the ingredients associated to every distribution.\\
Construct the set of recipes corresponding to each distribution.\\
Determine those subsets of coboundaries defining a recipe.\\
Check whether these subsets satisfy the balanced distribution of even $n$-paths for $n  \equiv 2,3,0 \mod 4$, $6 \leq n \leq 2t+2$.\\
\\
{\sc Output:} the full set of $\Z _t \times \Z_2^2$-Hadamard matrices.
}

\end{algorithm}


%\end{remark}


\section{Calculations and examples}

%We now apply Algorithm \ref{algoritmo2} for odd $t$, $3 \leq t \leq 13$.

%\subsection{Case $t=3$}



Table \ref{tabla3} shows an exhaustive calculation of $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices (last column) for odd $t$, $3 \leq t \leq 13$, in terms of distributions (second column), ingredients (third column) and recipes (fourth column) by means of Algorithm \ref{algoritmo2}. The fifth column shows how many of the recipes are ``productive", in the sense that they actually give rise to $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices.

\begin{table}[!t]\renewcommand{\arraystretch}{1.3}\caption{$\Z _t \times \Z_2^2$-cocyclic Hadamard matrices from Algorithm  \ref{algoritmo2}.}\label{tabla3}\centering
$\begin{array}{c|c|c|c|c|c} t& distribution&\# ingred.& \# rec.& \# H.r.&\# H.\\ \hline 3&(1,1,1,0)& (1,1,1,1)&4&4&24\\
 \hline 5&(3,3,2,2)& (2,2,1,1)&12&12&120\\
 \hline 7&(6,6,6,3)& (4,4,4,1)&28&24&336\\
 &(6,5,5,5)& (4,3,3,3)&60&36&504\\
 \hline 9& (10,10,9,7) &(10,10,7,4)&756& 108&1944\\
  \hline 9&(9,9,9,9)& (7,7,7,7)&60&24&432\\
 \hline 11&(15,14,14,12)& (26,20,20,10)&5580&120&2640\\
 \hline 13& (21,21,21,15)& (74,74,74,14)& 19320 & 144&3744\\
&(21,21,18,18)& (74,74,34,34)&29208&72&1872\\
&(20,20,20,18)& (57,57,57,34)&21612&108&2808\\
 \hline
\end{array}$
\end{table}



%\begin{table}[!t]\renewcommand{\arraystretch}{1.3}\caption{$\Z _t \times \Z_2^2$-cocyclic Hadamard matrices from Algorithm  \ref{algoritmo2}.}\label{tabla3}\centering
%$\begin{array}{c|c|c|c|c|c} t& distribution&\# ingred.& \# rec.& \# H.r.&\# H.\\ \hline 3&(1,1,1,0)& (1,1,1,0)&4&4&24\\
% \hline 5&(3,3,2,2)& (2,2,1,1)&12&12&120\\
% \hline 7&(6,6,6,3)& (4,4,4,1)&28&24&336\\
% \hline &(6,5,5,5)& (4,3,3,3)&60&36&504\\
% \hline 9& \begin{array}{c}(10,10,9,7)\\(9,9,9,9) \end{array} & \begin{array}{c}(10,10,7,4)\\ (7,7,7,7) \end{array}&\begin{array}{c}756\\60 \end{array}& \begin{array}{c}108\\ 24 \end{array}& \begin{array}{c}1944\\ 432\end{array}\\
%  \hline 9&(9,9,9,9)& (7,7,7,7)&60&24&432\\
% \hline 11&(15,14,14,12)& (26,20,20,10)&5580&120&2640\\
% \hline 13& \begin{array}{c}(21,21,21,15)\\ (21,21,18,18) \\ (20,20,20,18) \end{array}& \begin{array}{c}(74,74,74,14)\\ (74,74,34,34)\\ (57,57,57,34) \end{array}& \begin{array}{c}19320\\ 29208\\21612\end{array}  & \begin{array}{c}144\\72\\108 \end{array}&\begin{array}{c}3744\\ 1872\\2808 \end{array}\
% \hline 13&(21,21,18,18)& (74,74,34,34)&29208&72&1872\\
%  \hline 13&(20,20,20,18)& (57,57,57,34)&21612&108&2808\\
% \hline
%\end{array}$
%\end{table}


%C\'{a}lculos completos mediante ingredientes y recetas hasta t=13.

\section{Conclusions}

We wonder about the consistence of the observations listed below. Are there any reasons for these behaviors? Can these properties be demonstrated?

%After an observation process, some questions come into our minds:

%Preguntas tras observaciones:

\begin{enumerate}

\item As far as we have been able to check, if a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix exists associated to a recipe, it seems that there also exist $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices associated to any recipe obtained by permuting columns from it. Nevertheless, this is not always true for row permutations. % Can be this fact demonstrated in general?

\item Furthermore, as far as we have been able to check, given a $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix meeting a distribution, it seems that there also exists another $\Z _t \times \Z_2^2$-cocyclic Hadamard matrix meeting the same distribution, but using the complementary number of coboundaries ($t-k_i$ instead of $k_i$) for generating some of the entries $\frac{k_i(t-k_i)}{2}$ of the distribution.% Is there a reason for that?

%It seems that the set of $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices may be organized in terms of distributions,

%Se observan ciertos bailes en las configuraciones de matrices de Hadamard. ?`Es siempre as\'{\i}? ?`Motivo?

\item $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices seem to come from special recipes, those involving {\em singular} ingredients. Here, for a ``singular'' ingredient we mean one for which the set of subsets of coboundaries providing this ingredient has minimum size. This would imply that these subsets of coboundaries must be somehow symmetrically distributed.

%Las matrices de Hadamard aparecen siempre con aquellas recetas que generan el menor n\'{u}mero posible de matrices. ?`Es siempre as\'{\i}? ?`Motivo?

\item The set of symmetric Williamson type Hadamard matrices seems to be in proportion $\frac{1}{t}$ with respect to the full set of  $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices.

%En los ejemplos calculados, hay una relaci\'{o}n de proporcionalidad de $\frac{1}{t}$ entre matrices sim\'{e}tricas de Williamson y matrices

%$\Z _t \times \Z_2^2$-cocyclic Hadamard matrix

\end{enumerate}

We will devote another paper to analyze these facts. In particular,  in the second series of this paper \cite{AGG11} we will define a visual scheme (called diagram) for working with $\Z_t \times \Z_2^2$-cocyclic matrices. With these diagrams at hand, the condition of symmetry will be apparent. The remaining conditions cited above imply the existence of some Hadamard-preserving transformations. In particular, assuming this condition of symmetry, the set of $\Z_t \times \Z_2^2$-cocyclic matrices may be organized in orbits, $\frac{1}{t}$ of which will be proved to be symmetric Williamson type Hadamard matrices. We have been able to calculate the full set of orbits for $3 \leq t \leq 23$, and one orbit for $t=25$. Furthermore, since the knowledge of just one $\Z_t \times \Z_2^2$-cocyclic matrix completely characterizes its corresponding orbit, our method may be used to calculate orbits from the symmetric Williamson type Hadamard matrices listed in \cite{Kou} (this is an exhaustive list for odd $t \leq 39$, partial for $41 \leq t \leq 63$).

%In \cite{BH95}.


%\section*{Acknowledgment}


%The authors would like to thank...


% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
%\ifCLASSOPTIONcaptionsoff
%  \newpage
%\fi



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
%\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
\begin{thebibliography}{1}

%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.


\bibitem{AAFR08} V. \'{A}lvarez, J.A. Armario, M.D. Frau and P. Real, "A system of equations for describing cocyclic Hadamard matrices", {\em J. Comb. Des.}, vol. 16, pp. 276--290, 2008.
\bibitem{AAFR09} V. \'{A}lvarez, J.A. Armario, M.D. Frau and P. Real, "The homological reduction method for computing cocyclic Hadamard matrices", {\em J. Symb. Comput.}, vol. 44, pp. 558-570, 2009.


\bibitem{AGG11} V. \'{A}lvarez, F. Gudiel and M.B. G\"{u}emes, "Some new operations on $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices". Preprint. Submitted to journal.

\bibitem{BH95} A. Baliga and K.J. Horadam, "Cocyclic Hadamard matrices over $\Z _t \times \Z _2^2$, {\em Australas. J. Combin.}, vol. 11, pp. 123--134, 1995.

\bibitem{Gue11}
M. B. G\"uemes, ``Cocyclic Hadamard matrices over $\Z _t \times
\Z_2^2$. Description, classification and search. PhD thesis (English translation), University of Seville, 2011.

\bibitem{Hor07} K.J. Horadam, {\em Hadamard matrices and their applications}. Princeton: Princeton University Press,  2007.

\bibitem{HdL93} K.J. Horadam and W. de Launey, "Cocyclic development of designs", {\em J. Algebraic Combin.}, vol. 2, no. 3, pp. 267--290, 1993. Erratum, {\em J. Algebraic Combin.}, vol. 3, pp. 129, 1994.

\bibitem{HdL95} K.J. Horadam and W. de Launey, "Generation of cocyclic Hadamard matrices", in: {\em Proc. Computational Algebra and Number Theory}, Sydney, 1992, in {\em Math. Appl.}, vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 279--290.


\bibitem{Kou} C. Koukouvinos, web page, http://www.math.ntua.gr/~ckoukouv/


















\end{thebibliography}

% biography section
%
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
%\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

%\vfill



%\vfill{ }

% if you will not have a photo at all:
%\begin{IEEEbiographynophoto}{John Doe}
%Biography text here.
%\end{IEEEbiographynophoto}

% insert where needed to balance the two columns on the last page with
% biographies
%\newpage

%\begin{IEEEbiographynophoto}{Jane Doe}
%Biography text here.
%\end{IEEEbiographynophoto}

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\end{document}

1112.4296.extracted_bib
\begin{thebibliography}{1}

%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.


\bibitem{AAFR08} V. \'{A}lvarez, J.A. Armario, M.D. Frau and P. Real, "A system of equations for describing cocyclic Hadamard matrices", {\em J. Comb. Des.}, vol. 16, pp. 276--290, 2008.
\bibitem{AAFR09} V. \'{A}lvarez, J.A. Armario, M.D. Frau and P. Real, "The homological reduction method for computing cocyclic Hadamard matrices", {\em J. Symb. Comput.}, vol. 44, pp. 558-570, 2009.


\bibitem{AGG11} V. \'{A}lvarez, F. Gudiel and M.B. G\"{u}emes, "Some new operations on $\Z _t \times \Z_2^2$-cocyclic Hadamard matrices". Preprint. Submitted to journal.

\bibitem{BH95} A. Baliga and K.J. Horadam, "Cocyclic Hadamard matrices over $\Z _t \times \Z _2^2$, {\em Australas. J. Combin.}, vol. 11, pp. 123--134, 1995.

\bibitem{Gue11}
M. B. G\"uemes, ``Cocyclic Hadamard matrices over $\Z _t \times
\Z_2^2$. Description, classification and search. PhD thesis (English translation), University of Seville, 2011.

\bibitem{Hor07} K.J. Horadam, {\em Hadamard matrices and their applications}. Princeton: Princeton University Press,  2007.

\bibitem{HdL93} K.J. Horadam and W. de Launey, "Cocyclic development of designs", {\em J. Algebraic Combin.}, vol. 2, no. 3, pp. 267--290, 1993. Erratum, {\em J. Algebraic Combin.}, vol. 3, pp. 129, 1994.

\bibitem{HdL95} K.J. Horadam and W. de Launey, "Generation of cocyclic Hadamard matrices", in: {\em Proc. Computational Algebra and Number Theory}, Sydney, 1992, in {\em Math. Appl.}, vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 279--290.


\bibitem{Kou} C. Koukouvinos, web page, http://www.math.ntua.gr/~ckoukouv/


















\end{thebibliography}