% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% 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
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}

% 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
%\newcommand{\proof}{\vspace{0pt}{\noindent\bfseries Proof.\ }}

%\newcommand{\QED}{{\unskip\nobreak\hfil\penalty50\hskip1em\hbox{}\nobreak
%   \hfil \ensuremath{\Box}\parfillskip=0pt \par}}

% 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}

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

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

\title{\bf A Step Towards Yuzvinsky's Conjecture}

% 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{Dagwood Remifa\thanks{Supported by NASA grant ABC123.}\\
\author{Isidoro Gitler\thanks{Supported by ABACUS-CINVESTAV, Conacyt grant EDOMEX-2011-C01-165873, SNI-Conacyt.} \qquad Enrique Reyes\footnotemark[1]\\
\small Departamento de Matemáticas\\[-0.8ex]
\small Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional\\[-0.8ex] 
\small Ciudad de México 07000 México\\
\small\tt igitler@math.cinvestav.edu.mx \quad ereyes@math.cinvestav.mx\\
\and
Francisco Javier Zaragoza Martínez\thanks{Supported by UAM Azcapotzalco, research grant SI004-13, SNI-Conacyt.}\\
\small Departamento de Sistemas\\[-0.8ex]
\small Universidad Autónoma Metropolitana Azcapotzalco\\[-0.8ex]
\small Ciudad de México 02200 México\\
\small\tt franz@correo.azc.uam.mx
}

% \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{Jul 22, 2016}{xx xx, 20xx}\\
\small Mathematics Subject Classifications: 05B20, 11B75}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
An intercalate matrix $M$ of type $[r,s,n]$ is an $r\times s$ matrix with entries in $\{1,2,\dotsc,n\}$ such that all entries in each row are distinct, all entries in each column are distinct, and all $2\times 2$ submatrices of $M$ have either $2$ or $4$ distinct entries. Yuzvinsky's Conjecture on intercalate matrices claims that the smallest $n$ for which there is an intercalate matrix of type $[r,s,n]$ is the Hopf-Stiefel function $r\circ s$. In this paper we prove Yuzvinsky's Conjecture is asymptotically true for $\frac{5}{6}$ of integer pairs $(r,s)$. We prove the conjecture for $r\le 8$, and we study it in the range $r,s\le 32$.

\vspace{0.5ex}
  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Yuzvinsky's Conjecture; Intercalate matrices; Hopf-Stiefel function.
\end{abstract}



\section{Introduction}


Let $M$ be an $r\times s$ matrix with entries in a set of \emph{colors} $\{1,2,\dotsc,n\}$. Let $M_{i,j}$ be the $(i,j)$-entry of $M$. The matrix $M$ is said to be \emph{intercalate} of type $[r,s,n]$ if it satisfies the following two conditions:
\begin{description}
\item[Latinicity] \mbox{The colors along each row and each column are distinct.}\label{cond_1}    
\item[Intercalacy] \mbox{If $M_{i, j} = M_{i^\prime, j^\prime}$, then $M_{i, j^\prime} = M_{i^\prime, j}$.}\label{cond_2}
\end{description}

\vspace{1ex}

These conditions imply that every $2\times 2$ submatrix of $M$ involves an even number of distinct colors. Those involving exactly two colors are called \emph{intercalations}; in this case each color forms a \emph{half-intercalation}. Observe that the set of intercalate matrices is closed under transposition, taking submatrices, and permutation of rows, columns, or colors. Intercalate matrices appeared in the context of the classical problem of sums of squares formulae~\cite{yuzvinsky1981}. For more details see~\cite{yiu1987} and for a thorough exposition see~\cite{shapiro2000}. 

\vspace{2ex}

In the 1940's, Hopf~\cite{hopf1941} and Stiefel~\cite{stiefel1941} introduced the function
\[
r\circ s = \min\Bigl\{ n\in\mathbb{N}\mid\mbox{$\binom{n}{k}\equiv 0\bmod 2$ for all $k$ in the range $n-r < k < s$}\Bigr\}
\]
in their work on real division algebras by topological methods. This function, currently known as the Hopf-Stiefel function, plays an important role in several other subjects such as algebraic topology~\cite{lam1985, lam2016, yiu1987}, quadratic forms~\cite{pfister1987, plagne2003}, sums of squares formulae~\cite{romero1995, sanchez1996, yiu1987, yiu1990, yuzvinsky1981}, and additive number theory \cite{eliahou1998, eliahou2005, karolyi2006, plagne2003}. The Hopf-Stiefel function can also be computed recursively by the following formula due to Pfister~\cite{pfister1965}:


\begin{equation*}
r \circ s =
\begin{cases}
	s\circ r & \mbox{if $r>s$}                \\
	s & \mbox{if $r = 1$}                     \\
	2^k & \mbox{if $2^{k-1} < r\le s\le 2^k$} \\
	2^k + r \circ (s-2^k) & \mbox{if $r \le 2^k < s$}.
\end{cases}
\end{equation*}


For an extensive description of reformulations of $r\circ s$ we refer the reader to~\cite{eliahou2005}. 

\vspace{2ex}

Stated in Yiu's standard terminology~\cite{yiu1987}, Yuzvinsky showed in 1981~\cite{yuzvinsky1981} that for every $r$ and $s$ there is an intercalate matrix of type $[r,s,r\circ s]$. For a simple proof see Shapiro~\cite[p. 274]{shapiro2000}. Additionally, Yuzvinsky posed the following conjecture:


\begin{conjecture}[Yuzvinsky's Conjecture]
    Let $f(r,s)$ be the smallest value of $n$ for which there exists an intercalate matrix of type $[r,s,n]$. Then $f(r,s)=r\circ s$.
\end{conjecture}

\vspace{2ex}
 
Since every $r\times s$ matrix whose entries are all distinct is intercalate, it follows that $f(r,s)\le rs$, therefore $f(r,s)$ is well defined. Furthermore, Yuzvinsky's result implies $f(r,s)\le r\circ s$. Since intercalate matrices are closed under transposition, it follows that $f(r,s) = f(s,r)$. Furthermore, intercalate matrices are closed under taking submatrices, hence the function $f$ has the following property: 

 
\begin{description}
    \item[Monotonicity] If $r\le R$ and $s\le S$, then $f(r,s)\le f(R,S)$.
\end{description}

\vspace{1ex}

Yiu~\cite{yiu1990} verified Yuzvinsky's Conjecture whenever $r,s\le 16$ and Lam~\cite{lam2016} proved it for square intercalate matrices, together with some other special cases. In the same paper Lam gave a result implying the conjecture is asymptotically true for $\frac{2}{3}$ of integer pairs $(r,s)$. In this paper we improve Lam's asymptotic bound to $\frac{5}{6}$ of integer pairs $(r,s)$. We prove the conjecture for $r\le 8$, and we study it in the range $r,s\le 32$.



\section{Dyadic intercalate matrices}

There is a well-known general distinction between two main classes of intercalate matrices: dyadic and non-dyadic. Dyadic intercalate matrices are an important class whose construction comes from group theory. Let $D =\mathbb{Z}/2\mathbb{Z}\oplus\cdots\oplus\mathbb{Z}/2\mathbb{Z}$ be an Abelian $2$-group with cardinality $2^k$. The addition table of $D$ gives an intercalate matrix of type $[2^k, 2^k, 2^k]$, whose color set is $D$. A dyadic matrix is a submatrix of the addition table of group $D$. Following Yiu~\cite{yiu1987, yiu1990}, we can construct a canonical family of dyadic intercalate matrices. Starting with $D_1 = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ define inductively:
\[
D_{t+1} =  
\begin{pmatrix}
	D_t       & 2^t + D_t \\
	2^t + D_t & D_t 
\end{pmatrix} \mbox{ for $t=1,2,\dotsc$}
\]


Here, we consider $D_t$ as a matrix of integers, and obtain $2^t + D_t$ by adding $2^t$ to each entry of $D_t$. The intercalate matrix $D_t$ is of type $[2^t, 2^t, 2^t]$ and every submatrix of $D_t$ is an intercalate matrix. Given $r,s\le 2^t$, let $D_{r, s}$ be the principal $r\times s$ submatrix in the upper left hand corner of $D_t$. Observe that $D_{r, s}$ does not depend on $t$. Note that $D_i=D_{2^i,2^i}$, and an intercalate matrix is dyadic if it is a submatrix of some $D_t$. Yuzvinsky proved in~\cite{yuzvinsky1981} that the submatrices of $D_t$ with type $[ r,s,n ]$ satisfy $n\ge r \circ s$, hence Yuzvinsky's Conjecture is true for dyadic matrices. A conceptually elegant proof of this result was obtained by Eliahou and Kervaire~\cite{eliahou1998}, using the polynomial method extensively developed by Alon and Tarsi~\cite{alon1992}. For different methods to decide when an intercalate matrix is dyadic see~\cite{calvillo1997A}, for further properties see~\cite{calvillo1997B, zaragoza1998}. 

\vspace{2ex}

In contrast to the dyadic case, there are no theoretical methods to obtain non-dyadic intercalate matrices, although there exist simple examples such as
\[
\begin{pmatrix}
	1 & 2 & 3 & 4 \\
	2 & 1 & 4 & 3 \\ 
	5 & 6 & 7 & 8 \\ 
	6 & 5 & 9 & 10 
\end{pmatrix}
\quad\mbox{and}\quad 
\begin{pmatrix}
	1  & 2  & 3  & 4  & 5  \\
	6  & 3  & 2  & 7  & 8  \\ 
	9  & 10 & 11 & 8  & 7  \\ 
	10 & 9  & 12 & 13 & 14 \\ 
	15 & 16 & 13 & 12 & 17 
\end{pmatrix}.
\]

 
Yuzvinsky's Conjecture remains open for non-dyadic intercalate matrices.



\section{Constructions relative to color frequencies}

There are several known methods to obtain new intercalate matrices from a given intercalate matrix. These have been described mostly in the context of sums of squares formulae~\cite{lam1985, romero1995, sanchez1996, shapiro2000, yiu1987, yiu1990}. In this section we introduce some constructions based on the frequency of the colors appearing in an intercalate  matrix to obtain new intercalate matrices. The procedure given in Theorem~\ref{hidden} was originally introduced by Lam and Yiu~\cite{lam1987, lam1989} while studying sums of squares formulae from a topological perspective, and later by Yiu~\cite{yiu1987} in combinatorial terms. 

\vspace{2ex}

Let $M$ be an intercalate matrix of type $[r,s,n]$ and let $a$ be a color of frequency $t$ in $M$. By permuting rows and columns, we can assume color $a$ appears in the first $t$ rows and columns along the main diagonal of $M$, to obtain 
\begin{equation*}\label{matrix_M}
M = 
\begin{pmatrix}
	A & B\, \\ 
	C & D 
\end{pmatrix}
\end{equation*}
with $A$ a $t\times t$ submatrix. In this case $M$ is said to be in \emph{block form} with respect to color $a$. 


\begin{theorem}[\cite{lam1987, lam1989, yiu1987}]\label{hidden}
Let $M$ be an intercalate matrix of type $[r,s,n]$ in block form with respect to color $a$ of frequency $t$. Then the matrix  
\[ 
M^\prime = \begin{pmatrix}
				A & B & C^T \,
			\end{pmatrix}
\] 
is intercalate of type $[t,s+r-t,n^\prime]$ with $n^\prime\le n$. In particular $n\ge f(t,s+r-t)$.
\end{theorem}


The matrix $M^\prime$ of Theorem~\ref{hidden} is called the intercalate matrix {\em hidden behind} color $a$~\cite{yiu1990}. Analogous to Theorem~\ref{hidden}, in the following result we construct a new intercalate matrix $M^{\prime\prime}$ when $t=r-1$. 


\begin{theorem}\label{grow}
Let $M$ be an intercalate matrix of type $[r,s,n]$ in block form with respect to color $a$ of frequency $t = r-1$. Then the matrix
\[ 
M^{\prime\prime} = 
\begin{pmatrix}
	A & B & C^T \,\\ 
	C & D & a 
\end{pmatrix}
\] 
is intercalate of type $[r,s+1,n]$. In particular $n\ge f(r,s+1)$.
\end{theorem}

\proof
Since $a$ does not appear in $C$ nor $D$, it follows that $M^{\prime\prime}$ satisfies the latinicity condition. Now, we prove that each $2\times 2$ submatrix $N$ of $M^{\prime\prime}$ also satisfies the intercalacy condition. By Theorem~\ref{hidden} we can assume $N=\begin{pmatrix}M_{i,j}^{\prime\prime}&M_{i,s+1}^{\prime\prime}\\M_{r,j}^{\prime\prime}&a\end{pmatrix}$. It follows that $M_{i,j}^{\prime\prime}=a$ if and only if $i=j$ if and only if $M_{i,s+1}^{\prime\prime}=M_{r,j}^{\prime\prime}$. Finally, $M^{\prime\prime}$ is intercalate of type $[r,s+1,n]$ since $M^{\prime\prime}$ is an $r \times (s+1)$ intercalate matrix with the same number of colors as $M$.
\qed          

\vspace{2ex}

It is not possible to generalize Theorem~\ref{grow} for all $t\le r-1$. For example, consider the intercalate matrix
\[
M = 
\left(\begin{array}{cc|cc}
	1 & 2 & 7 & 8 \\
	2 & 1 & 9 & 10 \\
	\hline
	3 & 4 & 6 & 5 \\
	5 & 6 & 4 & 3 \\
\end{array}\right)
\]
for which there are no colors $y$ and $z$ such that the matrix
\[
\left(\begin{array}{cc|cc|cc}
	1 & 2 & 7 & 8 & 3 & 5 \\
	2 & 1 & 9 & 10 & 4 & 6 \\
	\hline
	3 & 4 & 6 & 5 & 1 & z \\
	5 & 6 & 4 & 3 & y & 1 \\
\end{array}\right)
\]
is intercalate. This is because the intercalation $\begin{pmatrix} 8 & 5 \\ 5 & z \end{pmatrix}$ implies $z=8$, the intercalation $\begin{pmatrix} 9 & 4 \\ 4 & y \end{pmatrix}$ implies $y=9$, but the intercalation  
$\begin{pmatrix} 1 & z \\ y & 1 \end{pmatrix}$ implies $y=z$.

\vspace{2ex}

The following result deals with intercalate matrices $M$ with only two distinct color frequencies and allows us to construct two new intercalate matrices, one of them contained in $M$.


\begin{theorem}\label{not1}
If $M$ is an intercalate matrix of type $[r,s,n]$ with $r$ colors of frequency $t < r$ and all the others with frequency $r$, then there exist an intercalate matrix of type $[t,n,n]$ and an intercalate submatrix of type $[r-t,s-t,s-t]$.
\end{theorem}

\proof
We have $rs=rt+(n-r)r$, hence $n-r=s-t$. Since there are $n-r=s-t$ colors of frequency $r$ and each one of them occurs in every row, it follows that each row has exactly $t$ colors of frequency $t$. We can assume $M$ is in block form with respect to color $a$ of frequency $t$. Let $c$ be a color in the submatrix $C$. If $c$ has frequency $r$, then it appears in every row of the submatrix $\bigl(A\;B\bigr)$. A contradiction, since by Theorem~\ref{hidden} the matrix $M^\prime$ is intercalate. Hence, $c$ has frequency $t$. Thus, $C$ contains only $t$ colors of frequency $t$ and $D$ contains only colors of frequency $r$. Therefore, $M^\prime$ is of type $[t,r+s-t,n] = [t,n,n]$ and $D$ is of type $[r-t,s-t,s-t]$.
\qed          

\vspace{2ex}

For example, the intercalate matrix 
\[
M = 
\left(\begin{array}{cc|cccc}
	1 & 2 & 5 & 6 & 7 & 8 \\
	2 & 1 & 6 & 5 & 8 & 7 \\
	\hline
	3 & 4 & 7 & 8 & 5 & 6 \\
	4 & 3 & 8 & 7 & 6 & 5 \\
\end{array}\right)
\]
is in block form with respect to color $1$ and by Theorem~\ref{not1} the matrices 
\[
M^\prime = 
\left(\begin{array}{cc|cccc|cc}
	1 & 2 & 5 & 6 & 7 & 8 & 3 & 4 \\
	2 & 1 & 6 & 5 & 8 & 7 & 4 & 3\\		
\end{array}\right)
\quad\mbox{and}\quad
D = 
\left(\begin{array}{cccc}
	7 & 8 & 5 & 6 \\
	8 & 7 & 6 & 5 \\		
\end{array}\right)
\]
are intercalate.




\section{Asymptotic results}


In this section we prove Yuzvinsky's Conjecture is asymptotically true for $\frac{5}{6}$ of integer pairs $(r,s)$. 


\begin{lemma}\label{mulpow}
If $r = 2^k$ and $s = t2^k$, then $f(r,s)=r\circ s$.
\end{lemma}

\proof
By the monotonicity of $f$, we have $f(r,s)\ge f(1,s)=t 2^k$. We also have $f(r,s)\le r\circ s=t 2^k$. Hence equality holds.
\qed

\vspace{2ex}

The next result due to Yiu~\cite{yiu1990} restricts the size of certain intercalate matrices.

\begin{theorem}\label{power}
If $M$ is an intercalate matrix of type $[r,n,n]$ with $n = 2^p (2\ell+1)$, then $r\le 2^p$.
\end{theorem}

\vspace{1ex}
For our purposes we include proofs of some results by Lam found in~\cite{lam2016}.

\begin{lemma}\label{lemma_I}
If $r+s=2^k+1$, then $r\circ s=2^k$.
\end{lemma}

\proof
We may assume $r\le s$. By induction on $k$. If $k=0$, then $r=s=1$ and $r\circ s=2^0$. It follows that $s>2^{k-1}\ge r$. Thus, Pfister's formula implies $r\circ s=2^{k-1}+r\circ (s-2^{k-1})$. Furthermore, $r+(s-2^{k-1})=2^{k-1}+1$ and, by the induction hypothesis, $r\circ (s-2^{k-1})=2^{k-1}$. Therefore, $r\circ s=2^k$.
\qed


\begin{theorem}[\cite{lam2016}]\label{lam}
If $r+s=2^k+1$, then $f(r,s) = r\circ s$.
\end{theorem}

\proof
By Lemma~\ref{lemma_I}, we have $r\circ s = 2^k$. We assume without loss of generality that $r < s$. By induction on $r$. If $r=1$, then $f(1,s) = 1\circ s$. Now assume $r \ge 2$. Let $M$ be an intercalate matrix of type $[r,s,n]$. Suppose each color of $M$ has frequency $r$, hence $n = \frac{rs}{r} = s$ and $M$ is of type $[r,s,s]$. Theorem~\ref{power} implies $s\ge r\circ s = 2^k$. Consequently, $r = 2^k+1-s \le 1$. A contradiction, hence $M$ has a color of frequency $t<r$. Thus, by Theorem~\ref{hidden}, there is an intercalate matrix $M^\prime$ of type $[t,r+s-t,n^\prime]$ with $n^\prime\le n$. Furthermore, $t+(r+s-t) = r+s = 2^k+1$ and, by the induction hypothesis, $n^\prime\ge t\circ (r+s-t) = 2^k$. Therefore, $n\ge 2^k = r\circ s$.
\qed          


\begin{corollary}[\cite{lam2016}]\label{mainlam}
If $r,s \le 2^k$ and $r+s\ge 2^k+1$, then $f(r,s) = r\circ s = 2^k$.
\end{corollary}

\proof
By Lemma~\ref{mulpow} and Pfister's formula we have $f(2^k,2^k) = 2^k\circ 2^k = 2^k$. Furthermore, there are $r^\prime\le r$ and $s^\prime\le s$ such that $r^\prime+s^\prime = 2^k+1$, consequently  the monotonicity of $f$ together with Theorem~\ref{lam} imply $2^k = f(r^\prime,s^\prime)\le f(r,s)\le f(2^k,2^k) = 2^k$. Also, $2^k = r^\prime\circ s^\prime\le r\circ s\le 2^k\circ 2^k = 2^k$. Therefore, $f(r,s) = 2^k = r\circ s$.
\qed          

\vspace{1ex}

Let $\ell_k$ be the number of integer pairs $(r,s)$ guaranteed to satisfy Yuzvinsky's Conjecture by Corollary~\ref{mainlam}, namely such that $1\le r,s\le 2^i$ and $r+s\ge 2^i+1$ for some $1\le i\le k$. For example, each dot in Figure~\ref{fig:lam} corresponds to a known value of $f(r,s)$ for $1\le r,s\le 64$. 

\begin{corollary}
    The ratio between $\ell_k$ and the size of the interval $[1,2^k]\times [1,2^k]$ converges asymptotically to $\frac{2}{3}$. That is, $\lim_{k\rightarrow\infty}\frac{\ell_k}{2^k\times 2^k}=\frac{2}{3}$.
\end{corollary}
    
\proof
It is easy to see that Corollary~\ref{mainlam} implies Yuzvinsky's Conjecture is true for $\ell_k = \frac{1}{2}\sum_{i=0}^{k} 2^k(2^k+1) = \frac{2}{3}(4^k-1)+2^k$ integer pairs $(r,s)$ with $1\le r,s\le 2^k$. The ratio between $\ell_k$ and the size of the interval is $\frac{\ell_k}{2^k\times 2^k} = \frac{2}{3}\Bigl(1-\frac{1}{4^k}\Bigl)+\frac{1}{2^k}$ and hence $\lim_{k\rightarrow\infty} \frac{\ell_k}{2^k\times 2^k} = \frac{2}{3}$.
\qed

\vspace{1ex}

As a consequence of Theorem~\ref{lam} and Corollary~\ref{mainlam}, Lam obtained that Yuzvinsky's Conjecture is true for square matrices. 


\begin{figure}[t]
\centering
\includegraphics[width=8cm]{figura-lam}
\caption{Integer pairs for which Corollary~\ref{mainlam} implies Yuzvinsky's Conjecture.}
\label{fig:lam}
\end{figure}


\begin{corollary}[\cite{lam2016}]
If $r = s$, then $f(r,s) = r\circ s$.
\end{corollary}

\vspace{1ex}
We call the pair $(r,s)$ \emph{Lam favorable} if $r+s = 2^{k_h} + \dotsb + 2^{k_1} + 1$ for some integers $k_h > \dotsb > k_1 > 0$ and $r\le\min(s,2^{k_1})$.


\begin{lemma}\label{favorable}
If $(r,s)$ is Lam favorable, then $r\circ s = r+s-1$.
\end{lemma}

\proof
By induction on $h$. If $h=1$ then, by Lemma~\ref{lemma_I}, $r\circ s = 2^k = r+s-1$. Now assume $h > 1$. In this case, $r+(s-2^{k_h}) = 2^{k_{h-1}}+\dotsb+2^{k_1}+1$. Thus, by the induction hypothesis, $r\circ (s-2^{k_h}) = r+s-2^{k_h}-1$. Hence, Pfister's formula implies $r\circ s = 2^{k_h} + r\circ (s-2^{k_h}) = r+s-1$.
\qed          


\begin{theorem}\label{general}
If $(r,s)$ is Lam favorable, then $f(r,s) = r\circ s$.
\end{theorem}

\proof
By induction on $r$. If $r=1$, then $f(1,s) = 1\circ s$. Now assume $r\ge 2$.  Let $M$ be an intercalate matrix of type $[r,s,n]$. Suppose all colors of $M$ have frequency $r$, hence $n = \frac{rs}{r} = s$ and $M$ is of type $[r,s,s]$. Theorem~\ref{power} implies $s\ge r\circ s$. Furthermore, by Lemma~\ref{favorable}, $r\circ s = r+s-1$, which implies $r\le 1$, a contradiction. Hence, there is a color of frequency $t<r$. Consequently, by Theorem~\ref{hidden} there is an intercalate matrix $M^\prime$ of type $[t,r+s-t,n^\prime]$ with $n^\prime\le n$. Since $t+(r+s-t) = r+s$ and $t<r$, it follows that $(t,r+s-t)$ is Lam favorable.  Thus, by the induction hypothesis $n^\prime\ge t\circ (r+s-t)$. By Lemma~\ref{favorable}, $t\circ (r+s-t) = r+s-1$. Therefore, $n\ge n^\prime\ge r+s-1$.
\qed          


\begin{figure}[t]
\centering
\includegraphics[width=8cm]{figura-grz}
\caption{Integer pairs for which Corollary~\ref{triangle} implies Yuzvinsky's Conjecture.}
\label{fig:grz}
\end{figure}


\begin{corollary}\label{triangle}
Let $k_h >\dotsb > k_1 > 0$ and $m = 2^{k_h} + \cdots + 2^{k_1}$. If $r\le 2^{k_1}$, $s\le m$, and $r+s\ge m+1$, then $f(r,s) = r\circ s = m$.
\end{corollary}

\proof
Lemma~\ref{mulpow} implies $f(2^{k_1},m)=2^{k_1}\circ m$. By Pfister's formula we obtain $2^{k_1}\circ m=2^{k_h}+2^{k_1}\circ (2^{k_{h-1}}+\dotsb+2^{k_1})=2^{k_h}+2^{k_{h-1}}+2^{k_1}\circ (2^{k_{h-2}}+\dotsb+2^{k_1})=\dotsb=2^{k_h}+\dotsb+2^{k_2}+2^{k_1}\circ 2^{k_1}=2^{k_k}+\dotsb+2^{k_2}+2^{k_1}=m$. Furthermore, there are $s^\prime\le s$ and $r^\prime\le r$ such that $s^\prime+r^\prime=m+1$. Consequently, $(s^\prime,r^\prime)$ is Lam favorable, then Lemma~\ref{favorable} together with Theorem~\ref{general} imply $f(r^\prime,s^\prime)=r^\prime\circ s^\prime=m$. Hence, $m=f(r^\prime,s^\prime)\le f(r,s)\le f(2^{k_1},m)=m$ and $m=r^\prime\circ s^\prime\le r\circ s\le 2^{k_1}\circ m=m$. Therefore, $f(r,s)=m=r\circ s$. 
\qed          


Similarly to $\ell_k$, we define $\ell_k^\prime$ as the number of integer pairs $(r,s)$ guaranteed to satisfy Yuzvinsky's Conjecture by Corollary~\ref{triangle} such that $1\le r,s\le 2^k$. For example, each dot in Figure~\ref{fig:grz} corresponds to a known value of $f(r,s)$ for $1\le r,s\le 64$. 


\begin{theorem}
    The ratio between $\ell_k^\prime$ and the size of the interval $[1,2^k]\times [1,2^k]$ converges asymptotically to $\frac{5}{6}$. That is, $\lim_{k\rightarrow\infty}\frac{\ell_k'}{2^k\times 2^k}=\frac{5}{6}$.
\end{theorem}

\proof 
It is easy to see that Corollary~\ref{triangle} implies Yuzvinsky's Conjecture is true for $\ell_k^\prime = 4^k-\sum_{i=1}^{k-2} (2^{k-i-1}-1)2^i(2^i-1) = \frac{1}{6}(5\cdot 4^k+4)+(k-1)2^{k-1}$ integer pairs $(r,s)$ with $1\le r,s\le 2^k$. The ratio between $\ell_k^\prime$ and the size of the interval is $\frac{\ell_k^\prime}{2^k\times 2^k} = \frac{1}{6}\left(5+\frac{1}{4^{k-1}}\right)+\frac{k-1}{2^{k+1}}$ and hence $\lim_{k\rightarrow\infty}\frac{\ell_k^\prime}{2^k\times 2^k} = \frac{5}{6}$.
\qed

\vspace{1ex}
We obtain a generalization of Lemma~\ref{mulpow}:


\begin{corollary}\label{mainpow}
If $b = 2^k$, then $f(a,b) = a\circ b$ for all $a\ge 1$.
\end{corollary}

\proof
If $a\le b$, then the claim follows from Corollary~\ref{triangle} with $r=a$ and $s=m=b$. Now, if $a>b$, then let $n$ be the unique integer with $(n-1)b<a\le nb$. Let $s_1=(n-1)b+1$ and $s_2=nb$. By the monotonicity of $f$, we have $f(s_1,b)\le f(a,b)\le f(s_2,b)$. Using Corollary~\ref{triangle} with $m = nb$, $r = b$ and $s\in\{s_1, s_2\}$, we obtain $f(s,b)=s\circ b=m$. Therefore, $f(a,b)=m=a\circ b$ since $s_1\circ b\le a\circ b\le s_2\circ b$.
\qed          

\vspace{1ex}
We close this section with a short proof of the following result of Lam (private communication):


\begin{theorem}\label{lamtwo}
Let $a,b\ge 1$. If $r+s = 2^a + 2^b + 1$, then $f(r,s) = r\circ s$.
\end{theorem}

\proof
By Corollary~\ref{mainlam}, we can assume $a > b > 0$. We can also assume $r < s$. If $r\le 2^b$, then $(r,s)$ is Lam favorable and we are done by Theorem~\ref{general}. Now, if $2^b < r < s\le 2^a$ then, by Corollary~\ref{triangle} taking $m = 2^a$, it follows that $f(r,s)=r\circ s$.
\qed          





\section{The conjecture for matrices with eight rows or less}

Yuzvinsky's Conjecture is known to be true for intercalate matrices with four or less rows~\cite{yiu1990}. In addition, Corollary~\ref{mainpow} implies Yuzvinsky's Conjecture is true for intercalate matrices whose number of rows is a power of two. Hence, a natural step would be to give a proof of Yuzvinsky's Conjecture for intercalate matrices with eight or less rows. This is our next main result.

\begin{theorem}\label{eightless}
If $r\le 8$, then $f(r,s) = r\circ s$ for all $s\ge 1$.
\end{theorem}

To prove Theorem~\ref{eightless}, we only need to give proofs for matrices with five, six, and seven rows (Theorems~\ref{Five},~\ref{Six}, and~\ref{Seven}). The main idea in these proofs is as follows: First, since we know the upper bound $f(r,s)\le r\circ s$, we can determine which matching lower bounds we have to prove. Second, we assume a color of a given frequency $t$ exists and we use Theorems~\ref{hidden} and~\ref{grow} to prove that the lower bound holds. Third, we prove that the remaining cases are impossible.

\vspace{2ex}

Let us illustrate this method with a proof of $f(3,s) = 3\circ s$. For $1\le i\le 4$, let $M_i$ be an intercalate matrix of type $[3,4k+i,n_i]$, and let $a$ be a color of frequency $1\le t\le 3$. We assume $M_i$ is in block form with respect to color $a$. By the monotonicity of $f$ we have:
\begin{enumerate}
\item $4k+4 = 3\circ (4k+4)\ge f(3,4k+4)\ge f(3,4k+3)\ge f(3,4k+2)$,  and
\item $4k+3 = 3\circ (4k+1)\ge f(3,4k+1)$.
\end{enumerate}

Therefore, it is enough to prove that $n_2\ge 4k+4$ and $n_1\ge 4k+3$.
\begin{enumerate}
\item If $t = 1$ then, by Theorem~\ref{hidden}, we have $n_2\ge f(1,4k+4) = 4k+4$. If $t = 2$ then, by Theorem~\ref{hidden}, we have $n_2\ge f(2,4k+3) = 4k+4$. Now, we can assume $M_2$ only has colors of frequency $3$, hence $n_2 = \frac{3(4k+2)}{3} = 4k+2$. Thus, $M_2$ is of type $[3,4k+2,4k+2]$, contradicting Theorem~\ref{power}.

\item If $t = 1$ then, by Theorem~\ref{hidden}, we have $n_1\ge f(1,4k+3) = 4k+3$. If $t = 2$ then, by Theorem~\ref{grow}, we have $n_1\ge f(3,4k+2) = 4k+4$. Now, we can assume $M_1$ only has colors of frequency $3$, hence $n_1 = \frac{3(4k+1)}{3} = 4k+1$. Thus, $M_1$ is of type $[3,4k+1,4k+1]$, contradicting Theorem~\ref{power}.
\end{enumerate}

\vspace{2ex}

\begin{lemma}\label{eight}
The following table gives $r\circ (8k+i)$ for $1\le r\le 8$:
\[ 
\begin{array}{|c||l|l|l|l|l|l|l|l|}
\hline
r & 8k+1 & 8k+2 & 8k+3 & 8k+4 & 8k+5 & 8k+6 & 8k+7 & 8k+8 \\ \hline \hline
1 & 8k+1 & 8k+2 & 8k+3 & 8k+4 & 8k+5 & 8k+6 & 8k+7 & 8k+8 \\ \hline
2 & 8k+2 & 8k+2 & 8k+4 & 8k+4 & 8k+6 & 8k+6 & 8k+8 & 8k+8 \\ \hline
3 & 8k+3 & 8k+4 & 8k+4 & 8k+4 & 8k+7 & 8k+8 & 8k+8 & 8k+8 \\ \hline
4 & 8k+4 & 8k+4 & 8k+4 & 8k+4 & 8k+8 & 8k+8 & 8k+8 & 8k+8 \\ \hline
5 & 8k+5 & 8k+6 & 8k+7 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 \\ \hline
6 & 8k+6 & 8k+6 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 \\ \hline
7 & 8k+7 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 \\ \hline
8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 & 8k+8 \\ \hline
\end{array} 
\]
\end{lemma}

\proof
Using Pfister's formula.
\qed


\begin{lemma}\label{diophantine}
Let $M$ be an intercalate matrix of type $[r,s,n]$. For each $1\le i\le r$, let $t_i$ be the number of colors of $M$ with frequency $i$. Then the following hold:
\begin{enumerate}
\item $t_1 + 2t_2 + 3t_3 + \dotsb + rt_r = rs$.
\item $t_2 \binom{2}{2} + t_3 \binom{3}{2} + \dotsb + t_r \binom{r}{2}\equiv 0\pmod{2}$.\label{4_3ii}
\item $t_2 + t_3 + t_6 + t_7 + \dotsb \equiv 0\pmod{2}$.
\end{enumerate}
\end{lemma}

\proof
The first identity counts the number of entries of $M$ in two different ways. The left-hand side of the second identity counts the number of half-intercalations of $M$. Since each intercalation consists of two half-intercalations, this number is even. The third identity follows from the second, noting that $\binom{i}{2}$ is odd if and only if $i\equiv 2,3\pmod{4}$.
\qed          


\begin{lemma}\label{not2}
There are no $r\times s$ intercalate matrices $M$ with $3\le r\le s$ such that:
\begin{enumerate}
\item There are at most $2(r-2)$ colors of frequency less than $r$.
\item There is a color of frequency $2$ that intercalates with a color of frequency $r$.
\end{enumerate}
\end{lemma}

\proof
By contradiction, assume there is such a matrix $M$. By Point \textit{2}, we can assume color $c$ has frequency $r$, color $b$ has frequency $2$, and they intercalate. By permuting rows and columns, and filling its first two columns, $M$ looks like:
\[ 
\left(\begin{array}{cccccccc}
	c      & b      & 3   & 4      & \cdots & r   & r+1 & \cdots \\
	b      & c      & a_3 & a_4    & \cdots & a_r &\cdot& \cdots \\
	3      & a_3    & c   &        &        &     & d   & \cdots \\
	\vdots & \vdots &     & \ddots &        &     &     & \cdots \\
	r      & a_r    &     &        &        & c   &     & \cdots
\end{array}\right).
\]


We claim that all $2(r-2)$ colors $\{3,\dotsc,r,a_3,\dotsc,a_r\}$ are pairwise different. Indeed, if $j=a_i$ with $i,j\in\{3,\dotsc,r\}$, then $j\ne i$ and $M_{i,2}=M_{1,j}$. Hence, $b=M_{1,2}=M_{i,j}$, a contradiction, since color $b$ has frequency $2$. Now, by Point \textit{1}, at least one of those colors (say $a_3$) must have frequency $r$ and must appear in all rows of $M$. By permuting columns, we can assume $a_3=r+1$. Consequently, $M_{1,r+1}=r+1=a_3=M_{3,2}$ which implies $d=M_{3,r+1}=M_{1,2}=b$, a contradiction.
\qed          


\begin{theorem}\label{Five}
$f(5,8k+i) = 5\circ (8k+i)$ for all $k\ge 0$ and $1\le i\le 8$.
\end{theorem}

\proof
Let $M_i$ be an intercalate matrix of type $[5,8k+i,n_i]$ and let $a$ be a color of frequency $1\le t\le 5$. We assume $M_i$ is in block form with respect to color $a$. By the monotonicity of $f$ and Lemma~\ref{eight} we have:
\begin{enumerate}
\item $8k+8 = 5\circ (8k+8)\ge f(5,8k+8)\ge\dotsb\ge f(5,8k+4)$,
\item $8k+7 = 5\circ (8k+3)\ge f(5,8k+3)$,
\item $8k+6 = 5\circ (8k+2)\ge f(5,8k+2)$, and
\item $8k+5 = 5\circ (8k+1)\ge f(5,8k+1)$.
\end{enumerate}

Therefore, it is enough to prove that $n_4\ge 8k+8$, $n_3\ge 8k+7$, $n_2\ge 8k+6$, and $n_1\ge 8k+5$.

\begin{enumerate}
\item If $1\le t\le 4$ then, by Theorem~\ref{hidden}, we have $n_4\ge f(t,8k+9-t) = 8k+8$. Now, we can assume $M_4$ only has colors of frequency $5$, hence $n_4 = \frac{5(8k+4)}{5} = 8k+4$. Consequently, $M_4$ is of type $[5,8k+4,8k+4]$, contradicting Theorem~\ref{power}.

\item If $t = 1$ then, by Theorem~\ref{hidden}, we have $n_3\ge f(1,8k+7) = 8k+7$. If $t = 3$ then, by Theorem~\ref{hidden}, we have $n_3\ge f(3,8k+5) = 8k+7$. If $t = 4$ then, by Theorem~\ref{grow},  we have $n_3\ge f(5,8k+4) = 8k+8$. Now, we can assume $M_3$ has $t_2$ colors of frequency $2$ and $t_5$ colors of frequency $5$, hence $2t_2 + 5t_5 = 5(8k+3)$. For a contradiction, we can assume $n_3\le 8k+6$, therefore: 
\[
8k+6\ge n_3 = t_2 + t_5\ge f(5,8k+3)\ge f(4,8k+3) = 8k+4. 
\]
The unique solution to this Diophantine system is $t_2 = 5$ and $t_5 = 8k+1$. Since $t_2$ is odd, this contradicts Lemma~\ref{diophantine}.

\item If $t = 1$ then, by Theorem~\ref{hidden}, we have $n_2 \ge f(1,8k+6) = 8k+6$. If $t = 2$ then, by Theorem~\ref{hidden}, we have $n_2 \ge f(2,8k+5) = 8k+6$. If $t = 4$ then, by Theorem~\ref{grow}, we have $n_2 \ge f(5,8k+3) = 8k+7$. Now, we can assume $M_2$ has $t_3$ colors of frequency $3$ and $t_5$ colors of frequency $5$, hence $3t_3 + 5t_5 = 5(8k+2)$. For a contradiction, we can assume $n_2 \le 8k+5$, therefore:
\[
8k+5\ge n_2 = t_3 + t_5\ge f(5,8k+2)\ge f(4,8k+2) = 8k+4. 
\]
The unique solution to this Diophantine system is $t_3 = 5$ and $t_5 = 8k-1$. By Theorem~\ref{not1}, there exists an intercalate matrix of type $[5-3,(8k+2)-3,(8k+2)-3] = [2,8k-1,8k-1]$, contradicting Theorem~\ref{power}.

\item If $t = 1$ then, by Theorem~\ref{hidden}, we have $n_1 \ge f(1,8k+5) = 8k+5$. If $t = 4$ then, by Theorem~\ref{grow}, we have $n_1 \ge f(5,8k+2) = 8k+6$. Now, we can assume $M_1$ has $t_2$ colors of frequency $2$, $t_3$ colors of frequency $3$, and $t_5$ colors of frequency $5$, hence $2t_2 + 3t_3 + 5t_5 = 5(8k+1)$. For a contradiction, we can assume $n_1 \le 8k+4$, therefore: 
\[
8k+4\ge n_1 = t_2 + t_3 + t_5\ge f(5,8k+1)\ge f(4,8k+1) = 8k+4. 
\]
There are exactly three solutions to this Diophantine system:
\begin{enumerate}
\item The solution $t_2 = 5$, $t_3 = 0$, and $t_5 = 8k-1$. Since $t_2+t_3$ is odd,  this contradicts Lemma~\ref{diophantine}.
\item The solution $t_2 = 3$, $t_3 = 3$, and $t_5 = 8k-2$. Since $t_2$ is odd, a color of frequency $2$, say $c$, must intercalate with color $a$ of frequency $t\in\{3,5\}$. By Lemma~\ref{not2}, we can assume $t=3$. Recall that $M_i$ is in block form with respect to color $a$. Hence, $A$ has no colors of frequency $5$. If $C$ contains a color of frequency $5$, then $a$ appears in $D$, a contradiction. Therefore, $A$ and $C$ form an intercalate matrix of type $[5,3,6]$, a contradiction.
\item The solution $t_2 = 1$, $t_3 = 6$, and $t_5 = 8k-3$. Since $t_2+t_3$ is odd,  this contradicts Lemma~\ref{diophantine}. \qed
\end{enumerate}
\end{enumerate}


\begin{theorem}\label{Six}
$f(6,8k+i) = 6\circ (8k+i)$ for all $k\ge 0$ and $1\le i\le 8$.
\end{theorem}

\proof
Let $M_i$ be an intercalate matrix of type $[6,8k+i,n_i]$ and let $a$ be a color of frequency $1\le t\le 6$. We assume $M_i$ is in block form with respect to color $a$. By the monotonicity of $f$ and Lemma~\ref{eight} we have:
\begin{enumerate}
\item $8k+8 = 6\circ (8k+8)\ge f(6,8k+8)\geq\cdots\ge f(6,8k+3)$, and
\item $8k+6 = 6\circ (8k+2)\ge f(6,8k+2)\ge f(6,8k+1)$.
\end{enumerate}

Therefore, it is enough to prove that $n_3\ge 8k+8$ and $n_1\ge 8k+6$.


\begin{enumerate}
\item If $1\le t\le 5$ then, by Theorem~\ref{hidden}, we have $n_3 \ge f(t,8k+9-t) = 8k+8$. Now, we can assume $M_3$ only has colors of frequency $6$, hence $n_3 = \frac{6(8k+3)}{6} = 8k+3$. Thus, $M_3$ is of type $[6,8k+3,8k+3]$, contradicting Theorem~\ref{power}.

\item If $1\le t\le 2$ then, by Theorem~\ref{hidden}, we have $n_1 \ge f(t,8k+7-t) = 8k+6$. If $t = 4$ then, by Theorem~\ref{grow} (applied to the first five rows of $M_1$) we have $n_1\ge f(5,8k+2) = 8k+6$. If $t = 5$ then, by Theorem~\ref{grow}, we have $n_1\ge f(6,8k+2) = 8k+6$. Now, we can assume $M_1$ has $t_3$ colors of frequency $3$ and $t_6$ colors of frequency $6$, hence $3t_3 + 6t_6 = 6(8k+1)$. For a contradiction, we can assume $n_1\le 8k+5$, therefore: 
\[
8k+5\ge n_1 = t_3 + t_6\ge f(6,8k+1)\ge f(5,8k+1) = 8k+5. 
\]


The unique solution to this Diophantine system is $t_3 = 8$ and $t_6 = 8k-3$. Since $t_3+t_6$ is odd, this contradicts Lemma~\ref{diophantine}.\qed
\end{enumerate}


\begin{lemma}\label{not_matrix3x4}
There is no intercalate matrix of type $[3,4,5]$.
\end{lemma}

\proof
By contradiction, suppose $M$ is an intercalate matrix of type $[3,4,5]$. Assume first that there is a color of frequency $3$, say color $1$. Hence, we may assume that $M$ has the form:
\[
\left(\begin{array}{cccc}
	1 & 2 & 3 & 4     \\
	2 & 1 & x & \cdot \\
	3 & x & 1 & \cdot \\
\end{array}\right).
\]


By latinicity of columns $2$ and $3$, we have $x\notin\{1,2,3\}$. If $x=4$, then by intercalacy $M_{2,4} = 3$ and $M_{3,4} = 2$, a contradiction since $M$ would have only $4$ colors. It follows that $x = 5$. By latinicity of row $2$ and column $4$, we have  $M_{2,4} = 3$. A contradiction, by the intercalacy condition on the upper-right $2\times 2$ submatrix. Thus, each color has frequency at most $2$. We can assume color $1$ has frequency $2$ and $M$ has the form
\[
\left(\begin{array}{cccc}
	1 & 2 & \cdot & \cdot \\
	2 & 1 & a     & \cdot \\
	c & b & 3     & \cdot \\
\end{array}\right).
\]


By latinicity and intercalacy in the last two rows, it follows that $1,2,3,a,b,c$ are pairwise different, a contradiction.
\qed


\begin{theorem}\label{Seven}
$f(7,8k+i) = 7\circ (8k+i)$ for all $k\ge 0$ and $1\le i\le 8$.
\end{theorem}

\proof
Let $M_i$ be an intercalate matrix of type $[7,8k+i,n_i]$ and let $a$ be a color of frequency $1\le t\le 7$. We assume $M_i$ is in block form with respect to color $a$. By the monotonicity of $f$ and Lemma~\ref{eight} we have:
\begin{enumerate}
\item $8k+8 = 7\circ (8k+8)\ge f(7,8k+8)\geq\cdots\ge f(7,8k+2)$, and
\item $8k+7 = 7\circ (8k+1)\ge f(7,8k+1)$.
\end{enumerate}

Therefore, it is enough to prove that $n_2\ge 8k+8$ and $n_1\ge 8k+7$.

\begin{enumerate}
	\item If $1\le t\le 6$ then, by Theorem~\ref{hidden}, we have $n_2\ge f(t,8k+9-t) = 8k+8$. Now, we can assume $M_2$ only has colors of frequency $7$, hence $n_2 = \frac{7(8k+2)}{7} = 8k+2$. Thus, $M_2$ is of type $[7,8k+2,8k+2]$, contradicting Theorem~\ref{power}.

	\item If $t\in\{1,3,5\}$ then, by Theorem~\ref{hidden}, we have $n_1\ge f(t,8k+8-t)=8k+7$. If $t = 6$ then, by Theorem~\ref{grow}, we have $n_1\ge f(7,8k+2) = 8k+8$. Now, we can assume $M_1$ has $t_2$ colors of frequency $2$, $t_4$ colors of frequency $4$, and $t_7$ colors of frequency $7$, hence $2t_2 + 4t_4 + 7t_7 = 7(8k+1)$. For a contradiction, we can assume $n_1\le 8k+6$, therefore:
\[
8k+6\ge n_1 = t_2 + t_4 + t_7\ge f(7,8k+1)\ge f(6,8k+1) = 8k+6. 
\]
There are exactly three solutions to this Diophantine system:
	\begin{enumerate}
		\item The solution $t_2 = 7$, $t_4 = 0$, and $t_7 = 8k-1$. Since $t_2$ is odd, there exist a color of frequency $2$ that intercalates with a color of frequency $7$. A contradiction by Lemma~\ref{not2}.
		\item The solution $t_2 = 4$, $t_4 = 5$, and $t_7 = 8k-3$. Since $t_2+t_7$ is odd, this contradicts Lemma~\ref{diophantine}.
	\item The solution $t_2 = 1$, $t_4 = 10$ and $t_7 = 8k-5$. By contradiction, suppose $M$ is an intercalate matrix of type $[7,8k+1,8k+6]$.  Let $b$ be the color of frequency $2$, and let $c$ be the color that intercalates with $b$. Observe that $c$ must have frequency either $4$ or $7$.

\vspace{1ex}	

We assume first $c$ has frequency $7$. By the proof of Lemma~\ref{not2}, we obtain a contradiction if at least one element of $W=\{3,\dotsc,7,a_3,\dotsc,a_7\}$ has frequency $7$ or if at least two of them are equal. This implies these $10$ colors have frequency $4$. Hence, $M$ has the form:	
\[
M = 
\left(\begin{array}{cccccc}
	c      & b     & 3     &\cdots & 7     &\cdots\\
	b      & c     & a_3   &\cdots & a_7   &\cdots\\
	3      & a_3   & c     &\cdots &\cdot  &\cdots\\
	\vdots &\vdots &\vdots &\ddots &\vdots &      \\
	7      & a_7   &\cdot  &\cdots & c     &\cdots\\
\end{array}\right).
\]


If the other two appearances of these $10$ colors are on the first $7$ columns of $M$, then the rest of $M$ would be an intercalate matrix of type $[7,8k-6,8k-6]$, contradicting Theorem~\ref{power}. Consequently, at least one color in $W$ does not appear in the first $7$ columns. So, we can assume color $3$ appears in column $8$. Since the frequency of color $3$ is $4$, we can assume $3$ appears in column $9$. Furthermore, by the intercalacy condition, we have $a_{ij}=a_{ji}$ for $3\le i\le 7$, $3\le j\le 7$. Hence, by the intercalations induced by colors $3$ and $c$, it follows that $M$ has the form:

\vspace{-1ex}
\[
\left(\begin{array}{cc|ccccc|ccc}
 c & b   & 3   & 4   & 5   & 6   & 7   & 8   & 9   & \cdots\\  
 b & c   & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & a_9 & \cdots\\
 \hline
 3 & a_3 & c   & 8   & 9   &\cdot&\cdot& 4   & 5   &\cdots\\
 4 & a_4 & 8   & c   &\cdot&\cdot&\cdot& 3   &\cdot&\cdots\\
 5 & a_5 & 9   &\cdot& c   &\cdot&\cdot&\cdot& 3   &\cdots\\
 6 & a_6 &\cdot&\cdot&\cdot& c   &\cdot&\cdot&\cdot&\cdots\\
 7 & a_7 &\cdot&\cdot&\cdot&\cdot& c   &\cdot&\cdot&\cdots\\  
\end{array}\right).
\]


Now, suppose $M_{4,9}=M_{5,8}=d$, then by latinicity of columns $8$, $9$ and latinicity of rows $4$, $5$, we have $d\notin\{3,4,5,8,9,a_4,a_5,a_8,a_9\}$. If $d=a_3$, then $a_4=5$. But the  colors in $W$ are pairwise different, hence $d\ne a_3$. If $d=6$, then by the intercalations induced by colors $6$ and $c$, $M$ would look like:
\[
\left(\begin{array}{cccccccccc}
c & b   & 3   & 4   & 5   & 6   & 7   & 8   & 9   &\cdots\\
b & c   & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & a_9 &\cdots\\
3 & a_3 & c   & 8   & 9   &\cdot&\cdot& 4   & 5   &\cdots\\
4 & a_4 & 8   & c   &\cdot& 9   &\cdot& 3   & 6   &\cdots\\
5 & a_5 & 9   &\cdot& c   & 8   &\cdot& 6   & 3   &\cdots\\
6 & a_6 &\cdot& 9   & 8   & c   &\cdot& 5   & 4   &\cdots\\
7 & a_7 &\cdot&\cdot&\cdot&\cdot& c   &\cdot&\cdot&\cdots\\
\end{array}\right).
\]


Consequently, by the intercalations induced by colors $9$ and $c$, we have $M_{3,6}=M_{4,5}=M_{5,4}=M_{6,3}=u$. Since color $7$ has frequency $4$, it follows that $u\ne 7$ and we can assume $M_{i,10}=7$ for some $i\in\{2,3,4,5,6\}$. Thus, $M_{7,10}\in\{b,3,4,5,6\}$. But these colors have frequency $2$ or $4$. Hence $d\ne 6$. Now, if $d=a_6$, then by the intercalations induced by colors $a_6$ and $c$, $M$ would have the following form:
\vspace{-1ex}
\[
\left(\begin{array}{cccccccccc}
c & b   & 3   & 4   & 5   & 6   & 7   & 8   & 9   &\cdots\\
b & c   & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & a_9 &\cdots\\
3 & a_3 & c   & 8   & 9   &\cdot&\cdot& 4   & 5   &\cdots\\
4 & a_4 & 8   & c   &\cdot& a_9 &\cdot& 3   & a_6 &\cdots\\
5 & a_5 & 9   &\cdot& c   & a_8 &\cdot& a_6 & 3   &\cdots\\
6 & a_6 &\cdot& a_9 & a_8 & c   &\cdot& a_5 & a_4 &\cdots\\
7 & a_7 &\cdot&\cdot&\cdot&\cdot& c   &\cdot&\cdot&\cdots\\
\end{array}\right).
\]


We assume $M_{4,5}=e$, then by intercalacy $M_{5,4}=e$. By latinicity of columns $4$ and $5$, we have $e\notin\{4,5,8,9,a_4,a_5,a_8,a_9\}$. Furthermore, by latinicity of row $4$, we have $e\notin\{3,a_6\}$. If $e=6$ or $e=a_3$, then by intercalacy $a_9=5$ or $a_5=8$. A contradiction by latinicity of columns $9$ and $8$, respectively. Consequently $e\notin\{6,a_3\}$. Now, if $e\in\{7,a_7\}$, then $M_{7,4}=M_{4,7}\in\{5,a_5\}$. A contradiction, since $a_5$ and $5$ have frequency $4$. Hence, $e\notin W\cup\{8,9,a_8,a_9\}$. In particular $e$ has frequency $7$, so we can assume $M_{1,10}=e$. Thus, by the intercalacy condition on color $e$ we have $M_{4,10}=5$ implying $M_{3,10}=a_6$. A contradiction, since $a_6$ has frequency $4$. Consequently, we can assume $d\notin\{6,a_6\}$. Similarly $d\notin\{7,a_7\}$. Therefore, $d\notin W$, implying $d$ has frequency $7$. So, we can assume $M_{1,10}=d$, and $M$ has the form:
\vspace{-1ex}
\[ 
\left(\begin{array}{ccccccccccc}
c & b   & 3   & 4   & 5   & 6   & 7   & 8   & 9   &d    &\cdots\\
b & c   & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & a_9 &\cdot&\cdots\\
3 & a_3 & c   & 8   & 9   &\cdot&\cdot& 4   & 5   & f   &\cdots\\
4 & a_4 & 8   & c   & f   &\cdot&\cdot& 3   & d   & 9   &\cdots\\
5 & a_5 & 9   & f   & c   &\cdot&\cdot& d   & 3   & 8   &\cdots\\
6 & a_6 &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdots\\
7 & a_7 &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdots\\
\end{array}\right),
\]
where $f$ is the color that intercalates with $c$ in columns $4$ and $5$. Consequently, $f\notin W$ since these colors have frequency $4$. Furthermore, by latinicity of row $4$, we have $f\notin\{8,9,d\}$. If $f=a_8$, then $a_5=3$. A contradiction, since the elements of $W$ are pairwise different. Hence $f\ne a_8$. Similarly we have $f\ne a_9$. Therefore, $f$ has frequency $7$ and we can suppose $M$ looks like:

\vspace{-1ex}
\[
\left(\begin{array}{cccccccccccc}
c & b   & 3   & 4   & 5   & 6   & 7   & 8   & 9   & d   & f   &\cdots\\
b & c   & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & a_9 &\cdot&\cdot&\cdots\\
3 & a_3 & c   & 8   & 9   &\cdot&\cdot& 4   & 5   & f   & d   &\cdots\\
4 & a_4 & 8   & c   & f   &\cdot&\cdot& 3   & d   & 9   & 5   &\cdots\\
5 & a_5 & 9   & f   & c   &\cdot&\cdot& d   & 3   & 8   & 4   &\cdots\\
6 & a_6 &\cdot&\cdot&\cdot& c   &\cdot&\cdot&\cdot&\cdot&\cdot&\cdots\\
7 & a_7 &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdots\\
\end{array}\right).
\]


If $M_{i,j}=7$ for some $i\in\{3,4,5\}$, then by intercalacy $M_{7,j}=M_{i,1}=i$. A contradiction, since $i$ has frequency $4$. If $M_{2,i}=7$, then by intercalacy $M_{7,i}=b$, a contradiction. So, $7$ can only appear in rows $1$, $6$ and $7$. This is a contradiction, since $7$ has frequency $4$. Hence, our assumption that $c$ had frequency $7$ cannot hold.

Therefore, $c$ must have frequency $4$. Hence, we can assume

\vspace{-1ex}
\[
M = 
\left(\begin{array}{cccc|ccc}
	c & b & z & w &  &   &   \\
	b & c & y & v &  &   &   \\
	z & y & c & x &  & Q &   \\
	w & v & x & c &  &   &   \\
	\hline
  	&   &   &   &  &   &   \\
  	&   & \hspace{-0.6cm}P &   &  & R &  \\
\end{array}\right).
\]


If $v=z$, then $x=b$ by intercalacy with $M_{3,1}=z$. A contradiction, so $v\ne z$. This implies $w\ne y$. Therefore, by latinicity $c,b,z,w,v,y,x$ are pairwise different colors. If there is a color $u$ in $P$ whose frequency is $7$, then we can suppose $M_{5,i}=u$ for some $i\in\{1,2,3,4\}$. Also, we can assume $M_{i,5}=u$, hence $M_{5,5}=c$. A contradiction, hence each color of $P$ has frequency $4$ in $M$. If $M_{i,j}$ has frequency $7$ with $i\in\{1,2\}$ and $j\in\{3,4\}$, then we can assume $M_{i^\prime,5}=M_{i,j}$ with $\{i,i^\prime\}=\{1,2\}$. Consequently, $M_{j,5}=b$, since $M_{j,i}=M_{i,j}=M_{i^\prime, 5}$ and $M_{i,i^\prime}=b$. This is a contradiction. Therefore, $z,y,w,v$ have frequency $4$. Now,  suppose $x$ has frequency $7$, then $x$ is not a color of $P$. By the intercalations induced by color $x$, $M$ would look like:
\vspace{-1ex}
\[
\left(\begin{array}{cccc|cccc}
	c & b & z & w & x   &\cdot&\cdot&\cdots\\
	b & c & y & v &\cdot& x   &\cdot&\cdots\\
	z & y & c & x & w   & v   &\cdot&\cdots\\
	w & v & x & c & z   & y   &\cdot&\cdots\\
	\hline
  	&   &                &  &\cdot&\cdot&  x  &\cdots\\
  	&   &\hspace{-0.6cm}P&  &\cdot&\cdot&\cdot&\cdots\\
  	&   &                &  &\cdot&\cdot&\cdot&\cdots\\
\end{array}\right).
\]
If $M_{5,1}\in\{y,v\}$ or $M_{5,2}\in\{z,w\}$, then $M_{5,3}=b$ or $M_{5,4}=b$. Furthermore, if $M_{5,3}\in\{w,v\}$ or $M_{5,4}\in\{z,y\}$, then $M_{5,5}=c$ or $M_{5,6}=c$. A contradiction, hence $\{w,v,z,y,c\}$ do not appear in $P$. Consequently, $P$ has at most $5$ colors, since these colors have frequency $4$ in $M$. We take the frequencies $f_1,f_2,f_3,f_4,f_5$ of these colors in $P$, then $0\le f_i\le 3$ and $f_1+f_2+f_3+f_4+f_5=12$. We can suppose $f_1\le f_2\le\dotsb\le f_5$, then $f_5=3$. By Lemma~\ref{not_matrix3x4} we have $(f_5,f_4,f_3,f_2,f_1)=(3,3,3,3,0)$. We take $d,e,f,g$ as the colors of $P$, then $M$ has the form:

\vspace{-2ex}
\[
\left(
\begin{array}{cccc|ccccc}
c & b & z & w & x     & \cdot & \cdot & \cdot & \cdots\\
b & c & y & v & \cdot & x     & \cdot & \cdot & \cdots\\
z & y & c & x & w     & v     & g     & \cdot & \cdots\\
w & v & x & c & z     & y     & f     & \cdot & \cdots\\
\hline
d     & e     & f     & g     & \cdot & \cdot & x     & \cdot &\cdots  \\
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & x     &\cdots\\
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot &\cdots\\
\end{array}
\right).
\]
If $M_{6,3}=g$ or $M_{6,4}=f$, then $M_{6,7}=c$. A contradiction, since $c$ has frequency $4$. Consequently, $M_{6,1}=f$ or $M_{6,1}=g$. This implies $M_{6,7}=w=M_{5,8}$ or $M_{6,7}=z=M_{5,8}$. This is a contradiction, since $w$ and $z$ have frequency $4$. Therefore, $x$ has frequency $4$. Then there exists a row in $P$ without color $x$. Assume it is row $5$, hence
\vspace{-2ex}
\[
M = 
\left(\begin{array}{cccc|c}
	c    & b   & z   & w   &   \\
	b    & c   & y   & v   & B \\
	z    & y   & c   & x   &   \\
	w    & v   & x   & c   &   \\
	\hline
	d    & e   & f   & g   &   \\
	\cdot&\cdot&\cdot&\cdot& C \\
	\cdot&\cdot&\cdot&\cdot&   \\
\end{array}\right)
\]
with $x\notin\{d,e,f,g\}$. By latinicity of column $1$, we have $d\notin\{c,b,z,w\}$. Since $b\ne f$ and $g\ne b$, it follows that $d\notin\{y,v\}$ and $e\notin\{z,w\}$. Furthermore, $e,c,y,v$ are pairwise different by latinicity of column $2$. If $f\in\{v,w\}$ or $g\in\{y,z\}$, then $e=x$ or $d=x$. A contradiction, therefore $z,y,c,x,w,v,d,e,f,g$ are the $10$ pairwise different colors of frequency $4$. If color $x$ appears in $P$, then we can assume $M_{6,1}=x$ and $M$ would have the form:
\vspace{-1ex}
\[
\left(\begin{array}{cccc|c}
	c    & b   & z   & w   &   \\
	b    & c   & y   & v   & B \\
	z    & y   & c   & x   &   \\
	w    & v   & x   & c   &   \\
	\hline
	d    & e   & f   & g   &   \\
	x    & h   & w   & z   & C \\
	\cdot&\cdot&\cdot&\cdot&   \\
\end{array}\right)
\]
where $M_{6,2}=h$. By latinicity of column $2$ and row $6$, we have $h\notin\{c,y,v,e,x,$ $w,z\}$. Furthermore, since $e\notin\{x,w,z\}$, then by intercalacy $h\notin\{d,f,g\}$. A contradiction, since $h$ has frequency $4$. Hence, $x$ is not in $P$ and $d,e,f,g$ are the colors of $P$. Since $P$ is a $3\times 4$ matrix, it follows that $d,e,f,g$ have frequency $3$ in $P$. Furthermore, there is a color of $P$ that appears in columns $1$ and $2$, since $P$ has $3$ rows. Thus, without loss of generality, we can assume $M_{5,1}=M_{6,2}=M_{7,3}=d$ and
\vspace{-1ex}
\[
M = 
\left(\begin{array}{cccc|c}
	c & b & z & w &   \\
	b & c & y & v & B \\
	z & y & c & x &   \\
	w & v & x & c &   \\
	\hline
	d & e & f & g &   \\
	e & d & g & f & C \\
	f & g & d & e &   \\
\end{array}\right),
\]
since every row of $P$ has the colors $d,e,f,g$. Furthermore, $d$ has frequency $4$, and we can suppose $M_{i,5}=d$ for some $i\in\{1,2,3,4\}$. If $1\le i\le 3$, then $M_{4+i,5}=c$. A contradiction, so $M_{4,5}=d$. Hence, $M_{6,5}=v$ and $M_{7,5}=x$. Thus, $M_{3,5}=e$ since $M_{7,4}=e$. Consequently, $M_{6,5}=z$ by intercalacy of $M_{3,5}$ with $M_{3,1}$ and $M_{6,1}$. This is a contradiction because $M_{6,5}=v$ and $z\ne v$. Hence, $c$ cannot have frequency $4$.

\vspace{1ex}

Since $c$ cannot have frequency neither $4$ nor $7$,  this concludes the proof of the theorem. \qed
	\end{enumerate}
\end{enumerate}






\section{The conjecture in the range $32\times 32$}

As mentioned in the introduction, Yiu~\cite{yiu1990} verified Yuzvinsky's Conjecture whenever $r,s\le 16$. In this section we extend his result to $r,s\le 32$, except for $19$ integer pairs $(r,s)$ in this range. 

%\vspace{2ex}

\begin{lemma}\label{lemmaII}
If $2^{k-1}<r\le s\le 2^k$ for some $k$, then $r\circ s=2^k=r\circ(s-1)$.
\end{lemma}

\proof
If $s\ne 2^{k-1}+1$, then $s-1>2^{k-1}$ and by Pfister's formula, $r\circ s=2^k=r\circ (s-1)$. Now, if $s=2^{k-1}+1$, then $r=2^{k-1}+1$ and $r\circ s=2^k$. Thus, by Pfister's formula, $r\circ (s-1)=2^{k-1}\circ r=2^{k-1}+2^{k-1}\circ (r-2^{k-1})=2^k$. Hence, $r\circ s=2^k=r\circ (s-1)$.
\qed


\begin{lemma}\label{lemma5_1}
Let $r,s$ be integers such that $1\le r\le s$, then 
\[
\max\{(r-1)\circ s,\ r\circ(s-1)\}\ge (r\circ s)-1.
\]
\end{lemma}

\proof
By induction on $r+s$. If $r=1$, then $1\circ (s-1)=s-1=(1\circ s)-1$. Thus, by Lemma~\ref{lemmaII}, we can assume $2\le r\le 2^k<s$ for some integer $k$. Hence, by Pfister's formula, $r\circ s=2^k+r\circ (s-2^k)$. By the induction hypothesis 
\[
\max\bigl\{(r-1)\circ(s-2^k),\ r\circ (s-2^k-1)\bigr\}\ge r\circ (s-2^k)-1.
\] 

If $s\ne 2^k+1$, then Pfister's formula implies $(r-1)\circ s=2^k+(r-1)\circ(s-2^k)$ and $r\circ (s-1)=2^k+r\circ(s-2^k-1)$. Hence, $\max\{(r-1)\circ s,\ r\circ(s-1)\}\ge r\circ s-1$. Now, we suppose $s=2^k+1$. By Pfister's formula, $r\circ s=2^k+r\circ 1=2^k+r$ and $(r-1)\circ s=2^k+(r-1)\circ 1=2^k+r-1$. Therefore, $(r-1)\circ s=(r\circ s)-1$.
\qed          

\vspace{1ex}
We give a shorter proof of the following lemma found in~\cite{zaragoza1998}.

\begin{lemma}\label{lem:6_3}
If $M$ is an intercalate matrix of type $[r,s,n]$ which is a counterexample to Yuzvinsky's Conjecture with minimal $r+s$, then $n=r\circ s-1=r+s-2$.
\end{lemma}

\proof
Since $M$ is a counterexample to the conjecture, $r\circ s>n$. By the minimality of $r+s$, it follows that $f(r,s-1)=r\circ (s-1)$ and $f(r-1,s)=(r-1)\circ s$. Consequently, the monotonicity of $f$ together with Lemma~\ref{lemma5_1}, imply $f(r,s)\ge\max\{f(r,s-1),f(r-1,s)\}\ge r\circ s-1$. Furthermore, $n\ge f(r,s)$, hence $n=r\circ s-1=r+s-2$. 
\qed

\vspace{1ex}

Finally, we obtain the following result in the range $32\times 32$.


\begin{theorem}
If $M$ is an $r\times s$ intercalate matrix which is a counterexample to Yuzvinsky's Conjecture with minimal $r+s$ and $r\le s\le 32$, then one of the following conditions holds:
\begin{enumerate}
\item $r = 9$ and $s\in\{17, 18, 19, 20, 21, 22, 23\}$.
\item $r = 10$ and $s\in\{17, 19, 21\}$.
\item $r = 11$ and $s\in\{17, 18, 21\}$.
\item $r\in\{12, 14, 15\}$ and $s = 17$.
\item $r = 13$ and $s\in\{17, 18, 19\}$.
\end{enumerate}
\end{theorem}

\noindent
\textit{Proof sketch.} By Theorem~\ref{eightless}, there are no counterexamples with $r\le 8$. By Yiu's result~\cite{yiu1990}, there are no counterexamples with $r\le s\le 16$. Hence, if $M$ is a minimal counterexample, then $17\le s\le 32$ and $9\le r\le s$. The only values of $r$ and $s$ in this range satisfying the conditions of Lemma~\ref{lem:6_3} and not covered by Theorem~\ref{general} nor Corollary~\ref{triangle} are those listed above. 
\qed

\vspace{1ex}

\noindent
{\bf{Acknowledgments}}


\noindent
The authors are grateful to an anonymous referee, whose generous advice made this paper significantly more readable.



\bibliographystyle{plain}
\begin{thebibliography}{10}
\bibitem{alon1992}{N. Alon and M. Tarsi, \emph{Colorings and orientations of graphs}, Combinatorica, 12:125--134, 1992.}
 
\bibitem{calvillo1997A}{G. Calvillo, I. Gitler, and J. Martínez-Bernal, \emph{Intercalate matrices: I. Recognition of dyadic type}, Bol. Soc. Mat. Mexicana, 3(3):57--67, 1997.}

\bibitem{calvillo1997B}{G. Calvillo, I. Gitler, and J. Martínez-Bernal, \emph{Intercalate matrices: II. A characterization of Hurwitz--Radon formulas and an infinite family of forbidden matrices}, Bol. Soc. Mat. Mexicana, 3(3):207--220, 1997.}

\bibitem{eliahou1998}{S. Eliahou and M. Kervaire, \emph{Sum sets in vector spaces over finite fields}, J. Number Theory, 71(1):12--39, 1998.}

\bibitem{eliahou2005}{S. Eliahou and M. Kervaire, \emph{Old and new formulas for the Hopf-Stiefel and related functions}, Exp. Math., 23(2):127--145, 2005.}

\bibitem{hopf1941}{H. Hopf, \emph{Ein topologischer Beitrag zur reellen Algebra}, Comment. Math. Helv., 13:219--239, 1940/41.}

\bibitem{karolyi2006}{G. Károlyi, \emph{A note on the Hopf-Stiefel function}, European J. Combin., 27:1135--1137, 2006.}

\bibitem{lam1985}{K.~Y. Lam, \emph{Some new results on composition of quadratic forms}, Invent. Math., 79:467--474, 1985.}

\bibitem{lam1987}{K.~Y. Lam and P. Yiu, \emph{Sums of squares formulae near the Hurwitz--Radon range}, Contemp. Math., 58:51--56, 1987.}

\bibitem{lam1989}{K.~Y. Lam and P. Yiu, \emph{Geometry of normed bilinear maps and the $16$-square problem}, Math. Ann., 284:437--447, 1989.}

\bibitem{lam2016}{K.~Y. Lam, \emph{Intercalate coloring of matrices and the Yuzvinsky conjecture}, Bol. Soc. Mat. Mexicana, 23(1):79--86, 2017.}

\bibitem{pfister1987}{A. Pfister, \emph{Quadratsummen in Algebra und Topologie}, Wiss. Beitr., Martin-Luther-Univ. Halle
Wittenberg, 195--208, 1987/88.}

\bibitem{pfister1965}{A. Pfister, \emph{Zur Darstellung von -1 als summe von quadraten in einem Körper}, J. London Math. Soc. 40:159--165, 1965.}

\bibitem{plagne2003}{A. Plagne, \emph{Additive number theory sheds new light on the Hopf-Stiefel $\circ$ function}, L'Enseignement
Math., 49:109--116, 2003.}

\bibitem{romero1995}{D. Romero, \emph{New constructions for integral sums of squares formulae}, Bol. Soc. Mat. Mexicana, 1(3):87--90, 1995.}

\bibitem{sanchez1996}{A. Sánchez-Flores, \emph{A method to generate upper bounds for the sums of squares formulae problem},
Bol. Soc. Mat. Mexicana, 2(2):79--92, 1996.}

\bibitem{shapiro2000}{D. Shapiro, Compositions of Quadratic Forms, \emph{de Gruyter Expositions in Mathema\-tics}, 33, 2000.}

\bibitem{stiefel1941}{E. Stiefel, \emph{Über Richtungsfelder in den projecktiven Räumen und einen Satz aus der reellen Algebra},
Comment. Math. Helv., 13:201--208, 1941.}

\bibitem{yiu1987}{P.~Y.~H. Yiu, \emph{Sums of squares formulae with integer coefficients}, Can. Math. Bull., 30:318--324, 1987.}

\bibitem{yiu1990}{P.~Y.~H. Yiu, \emph{On the product of two sums of 16 squares as a sum of squares of integral bilinear forms}, Quart. J. Math. Oxford, 41(2):463--500, 1990.}

\bibitem{yuzvinsky1981}{S. Yuzvinsky, \emph{Orthogonal pairings of Euclidean spaces}, Michigan Math. J., 28:131--145, 1981.}

\bibitem{zaragoza1998}{F.~J. Zaragoza-Martínez, \textit{Intercalate matrices and algebraic varieties}, Morfismos, 2(1):67--81, 1998.}
\end{thebibliography}

\end{document}
