\documentstyle[12pt]{article}
%\def\Ipe#1{}
\def\Ipe#1{\def\IPEfile{#1}\input{\IPEfile}}
\sloppy
\def\e{equiangular}
\def\H{Hadamard}
\def\Hm{\H\ matrix}
\def\m{matchable}
\def\my{matchability}
\def\qed{$\Box$}
\newcounter{prob}
\setcounter{prob}{0}
\newenvironment{pr}{\par\medskip\noindent\refstepcounter{prob} {\bf
Problem \theprob.}}{\par\medskip}
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}[section]
\newtheorem{lm}[prop]{Lemma}
\newtheorem{obs}[prop]{Observation}
\newtheorem{cor}[prop]{Corollary}
\newenvironment{pf}{\par\medskip\noindent{\bf
Proof}}{\hfill\qed\par\medskip}
\newenvironment{case}[5]{\[#1\left\{\begin{array}{lp{5cm}}#2 \qquad & #3\\
#4 & #5\end{array}\right.}{\]}
\begin{document}
\title{Graph Designs, Hadamard Matrices and Geometric Configurations
\thanks{Parts of this work were done during visits of various subsets of
the authors to Prague and Seattle. This has been enabled by the Czech-US
Research grant No. 94 051. All authors ackowledge partial support of Czech Research Grants GA\v CR 0194/1996 and GAUK 194/1996.}}
\author{Jan Kratochv\'{\i}l\\
Charles University\\
Prague, Czech Republic\\
{\tt honza@kam.ms.mff.cuni.cz}
 \and Jaroslav Ne\v set\v ril\\
Charles University\\
Prague, Czech Republic\\
{\tt nesetril@kam.ms.mff.cuni.cz}
  \and Moshe Rosenfeld\\
Pacific Lutheran University\\
Tacoma\\
{\tt moishe@math.washington.edu}}
\maketitle
\begin{abstract}
Motivated by graphs arising from special geometrical configurations
(equiangular line systems and balanced incomplete block designs)
we investigate graph equations of the type
$(2n-1)G(2n,n-1)=(n-1)K_{2n}$. This rather special equation proves to be
general enough to cover Hadamard matrices and a new
concept: {\em matchability} of Hadamard matrices.
We show that several known constructions and matrix operations produce
matchable Hadamard matrices, thus supporting our general conjecture that
all Hadamard matrices are matchable.
\end{abstract}

\section{Introduction}\label{intr}

The 1-skeleton of the icosahedron and the great icosahedron are
isomorphic graphs. A search for explanation of this well known fact has
led us to
the beautiful theory of equiangular line systems and related graphs
developed by J.J.Seidel~\cite{S}. This theory centers around
the notion of graph switching. Motivated by this we consider graph
equations of the following types:
\begin{eqnarray}
K_{2n} & = & 2G(2n,n-1) + nK_2 \label{eq1}\\
(n-1)K_{2n} & = & (2n-1)G(2n,n-1) \label{eq2}
\end{eqnarray}
(here and throughout the paper, $G(n,m)$ denotes an $m$-regular graph on
$n$ vertices).
%While the solutions of equation (\ref{eq1}) can be
%completely characterized (in terms of switching equivalence), the
%problem arising from the related equation (\ref{eq2}) appears to be much
%harder.
We believe that this
particular graph equation (which can be also interpreted as graph
designs in the sense of Hell and Rosa \cite{H}) is interesting even in rather special
cases of the simplest $G(2n,n-1)$ graphs. For $G(2n,n-1)=2K_n$, we show
that (\ref{eq2}) is equivalent to the existence of Hadamard matrices of
order $2n$. For $G(2n,n-1)= K_{n,n}-nK_{2}$ (sometimes called the
Hiraguchi graph), the situation is more involved. In this case we relate
the problem of solvability of (\ref{eq2}) to a new concept of {\em
matchability} of Hadamard matrices. While this notion will be defined
later on in a more technical way, here is a concise definition of the
matchability concept:

Let $H=(a_{ij})_{i,j=1}^{4m}$ be a Hadamard matrix of order $4m$ in
standard form (i.e., the first row and the first column consist of
+1's).
Delete the first column of $H$ to get a $4m\times(4m-1)$ matrix $A$, in
which every column contains exactly $2m$ $+1$'s and $2m$ $-1$'s, and in
which every two rows have Hamming distance $2m$. We say that the
matrix $A$ (and the \Hm\ $H$) are {\em \m} if for every column $j$ there
exists an involution (i.e., a matching)
$\phi_j:\{1,2,\ldots,2m\}\rightarrow \{1,2,\ldots,2m\}$ such that
$$a_{ij}a_{\phi_j(i),j}=-1$$
and such that for every pair $i< i'$ of distinct rows there is a unique
$j$ such that $\phi_j(i)=i'$.

Presently we do not know if there exist non-matchable \H\ matrices. In
fact, we show that several well known standard
constructions of \H\ matrices yield
\m\ matrices. Particularly, we show that the tensor product of \m\ \H\
matrices is \m\ (Theorem~\ref{tens}) and that some \H\
matrices derived from quadratic residues
are matchable (Theorem~\ref{qres}). We believe that
problems raised in this context are of independent interest.

Our work builds upon the work of several authors and in the first part
is necessarily partly of expository nature. One should mention again
Seidel's papers~\cite{S} which provide the original motivation. A nice
exposition of Seidel's theory is the recent paper~\cite{sst}. Another
related area is presented by graph designs, which were first defined and
studied by Hell and Rosa~\cite{H}.
%However, we tried to keep the paper selfcontained.

\section{Geometric examples and Seidel's switching}

Let $L=\{L_1,L_2,\ldots,L_n\}$ be a system of $n>d$ \e\ lines in the
$d$-dimensional euclidean space passing
through the origin. (A system of lines is \e\ if all angles among the
lines are the same and smaller than $\frac{\pi}{2}$.)
Let $X=\{x_1,x_2,\ldots,x_{2n}\}$ be the
intersection of these lines with the unit sphere centred in the origin,
i.e., $X$ contains 2 points of unit distance from the origin
on each of the lines. We define three graphs on the vertex set $X$:

\smallskip
$G_L=(X,\{x_ix_j|\angle x_i0x_j<\frac{\pi}{2}\}),$

$\widetilde{G_L}=(X,\{x_ix_j|\angle x_i0x_j>\frac{\pi}{2}\})$,

$M_L=(X,\{x_ix_j|x_i=-x_j\})$.

\smallskip\noindent
The graph $M_L$ is a perfect matching and we
denote it by $nK_2$. The edge set of the complete graph on $2n$
vertices is the disjoint union of the edge sets of $G_L$, $\widetilde{G_L}$
and $nK_2$, we say that $K_{2n}$ decomposes into $G_L$, $\widetilde{G_L}$
and $nK_2$. Formally, this fact is expressed in the graph equation
\begin{eqnarray}
K_{2n} & = & G_L + \widetilde{G_L} + nK_2 \label{eq3}.
\end{eqnarray}
Note that both $G_L$  and $\widetilde{G_L}$ are $(n-1)$-regular graphs on
$2n$ vertices, i.e., they are both $G(2n,n-1)$ graphs in our notation.

\medskip
\noindent
{\bf Example 1.} Let $L_1,L_2,L_3$ be the longest diagonals of a regular
hexagon $x_1x_2x_3x_4x_5x_6$ in $E^2$, centered in the origin (cf.
Figure~\ref{hex}). These lines form an \e\ line system, as any two of
them determine an angle of $\frac{\pi}{3}$. The edges of the hexagon
form our graph $G_L=C_6$ and the shorter diagonals determine
$\widetilde{G_L}=2K_3$. Equation (\ref{eq3}) thus becomes
$$K_{6}=C_6+2K_3+3K_2.$$

\begin{figure}[ht]
\begin{center}
\thinlines%\thicklines
\unitlength=1.00mm
\begin{picture}(41.00,52.00)
\put(10.00,10.00){\line(-1,2){10.00}}
\put(0.00,30.00){\line(1,2){10.00}}
\put(10.00,50.00){\line(1,0){20.00}}
\put(30.00,50.00){\line(1,-2){10.00}}
\put(40.00,30.00){\line(-1,-2){10.00}}
\put(30.00,10.00){\line(-1,0){20.00}}
\put(10.00,10.00){\line(1,2){20.00}}
\put(30.00,50.00){\line(-3,-2){30.00}}
\put(0.00,30.00){\line(3,-2){30.00}}
\put(30.00,10.00){\line(-1,2){20.00}}
\put(10.00,50.00){\line(3,-2){30.00}}
\put(40.00,30.00){\line(-3,-2){30.00}}
\put(10.00,10.00){\line(0,1){40.00}}
\put(0.00,30.00){\line(1,0){40.00}}
\put(30.00,10.00){\line(0,1){40.00}}
\put(10.00,52.00){\makebox(0,0)[cc]{$x_1$}}
\put(30.00,52.00){\makebox(0,0)[cc]{$x_2$}}
\put(41.00,34.00){\makebox(0,0)[cc]{$x_3$}}
\put(30.00,7.00){\makebox(0,0)[cc]{$x_4$}}
\put(10.00,7.00){\makebox(0,0)[cc]{$x_5$}}
\put(-2.00,33.00){\makebox(0,0)[cc]{$x_6$}}
\end{picture}
\end{center}
\caption{}
\label{hex}
\end{figure}

\medskip\noindent
{\bf Example 2.} Consider a regular icosahedron in the 3-dimensional
space. The lines passing through the longest diagonals form a system
of 6 \e\ lines. The edges of the icosahedron form our $G_L$. In this
case, the graph $\widetilde{G_L}$ formed by the
shorter diagonals, the great icosahedron,
turns out to be isomorphic to the icosahedron itself.
Hence equation (\ref{eq3}) becomes
$$K_{12}=2Ico+6K_2$$
(here $Ico$ denotes the graph of the icosahedron).


\medskip
Comparing Examples 1 and 2, we see that the icosahedron provides a solution
to equation (\ref{eq1}), while the hexagon does not ($C_6$ is not
isomorphic to $2K_3$). (This does not mean that {\em any} system of 6
\e\ lines would provide a solution to (\ref{eq1}) -- one can construct
systems of \e\ lines in higher-dimensional space such that $G_L$ and
$\widetilde{G_L}$ are non-isomorphic.) At this point it seems that
the theory of \e\ lines may be a
source of many solutions to (\ref{eq1}). Our first goal is to study the
pattern suggested by the icosahedron and great icosahedron, which leads
to the
following natural question:
{\em When are the graphs $G_L$ and $\widetilde{G_L}$ isomorphic?}

\medskip
This problem fits into Seidel's theory and can be answered within this
framework. Recall that given any graph $G=(V,E)$ and a subset $A\subset
V$, the graph $S(G,A)=(V,\{xy|xy\in E, |A\cap\{x,y\}|\neq 1\}\cup
\{xy|xy\not\in E, |A\cap\{x,y\}|=1\})$ is obtained from $G$ by {\em
switching} the vertices of $A$. Graphs $G,H$ are called {\em switching
equivalent} if $H$ is isomorphic to $S(G,A)$ for some $A\subset V(G)$.

\medskip
Given a system $L$ of $n$ \e\ lines, choose an $n$-element subset $Y$ of
$X$ so that $Y$ contains one point of each line
$L_i$. Denote $H_L$ the subgraph of $G_L$ induced by $Y$, i.e.,
$H_L=(Y,\{xy|\angle x0y<\frac{\pi}{2}\})$. (The graph
$H_L$ is not unique, it depends on the choice of $Y$. However, it
follows from Seidel's theory that all graphs $H_L$ are switching
equivalent and form a switching class. We use this notation since we are
only interested in properties invariant under switching.) It is worth
mentioning that Seidel proved~\cite{S} that every graph $H$ can be
obtained in this way as $H_L$ for some \e\ line system $L$. Now we can
formulate the answer to our question:

\begin{thm}\label{sw}
The graphs $G_L$ and $\widetilde{G_L}$ are isomorphic if and only if $H_L$
is switching equivalent to its complement.
\end{thm}

Thanks to Theorem~\ref{sw} we can reverse our strategy: In order to find
all solutions of (\ref{eq1}), we

\smallskip
1. search for all graphs $H$ on $n$ vertices which are switchable to
their complements;

2. represent $H$ as $H_L$ for an \e\ line system $L$;

3. build $G_L$ which then becomes a solution to (\ref{eq1}).

\smallskip\noindent
Let us note that $G_L$ can be constructed from $H$ in a purely
combinatorial way (without the intermediate step of \e\ line systems).
Given a graph $H$ we define $G_H$ as follows:
$$V(G_H)=\{(h,i)|h\in V(H),i=1,2\},$$
$$E(G_H)=\{(h,i)(h',i)|hh'\in E(H)\}\cup\{(h,i)(h',j)|i\neq j, h\neq
h',hh'\not\in E(H)\}.$$
It is clear that for any $n$-vertex graph $H$, $G_H$ is a $G(2n,n-1)$
graph and $G_H= G_L$ if $H=H_L$. Seidel's result says that any $G_H$ can
be also constructed geometrically via \e\ line systems. The following
simple observation is important for the proof of Theorem~\ref{sw} ($\bar
H$ denotes the complement of $H$):

\begin{obs}\label{gcomp}
For any graph $H$, $$G_{\bar{H}}=\widetilde{G_H}.$$
\qed
\end{obs}

Theorem~\ref{sw} then follows directly from this Observation and from
the following Theorem (in the proof, as well as in the rest of the
paper, $n$ is reserved to denote the number of vertices of $H$):

\begin{thm}\label{switchiso}
For any two graphs $H$ and $H'$, the graphs $G_H$ and $G_{H'}$ are
isomorphic if and only if $H$ and $H'$ are switching equivalent.
\end{thm}

\begin{pf}
The `if' part is easy. If $f:V(H)\rightarrow V(H')$ is an isomorphism of
$S(H,A)$ onto $H'$ for some $A\subset V(H)$, then $g:V(G_H)\rightarrow
V(G_{H'})$ defined by
\begin{case}
{g(h,i)=}{(f(h),i)}{if $h\in A$}{(f(h),3-i)}{if $h\in V(H)-A$}
\end{case}
is an isomorphism of $G_H$ onto $G_{H'}$.

\smallskip
For the `only if' part, suppose that $G_H$ and $G_{H'}$ are isomorphic.
It then follows from the first part of the theorem that $G_{H^*}$ and
$G_{H'^*}$ are isomorphic for any $H^*$ switching equivalent to $H$, and
$H'^*$ switching equivalent to $H'$.

For a graph $G$ and two of its vertices $u,v$, we write $u\sim_G v$ if
$u$ and $v$ have the same closed neighborhoods. This $\sim_G$ is an
equivalence relation and each equivalence class induces a complete
subgraph of $G$. Let $H_0=S(H,A)$ be a graph switching equivalent to $H$
such that the equivalence $\sim_{H_0}$ is the coarsest possible. We
claim that $H_0$ has the following property:
\begin{eqnarray}
\label{eq4}\forall x,y:\;xy\not\in E(H_0)\;\Rightarrow\;\exists
z:\{xz,yz\}\subset E(H_0)\;\vee\;\{xz,yz\}\cap E(H_0)=\emptyset
\end{eqnarray}
Indeed, if not then $H_0$ contains vertices $x,y$ such that every other
vertex is adjacent either to $x$ or to $y$. If $[x]_{\sim_{H_{0}}}$ and
$[y]_{\sim_{H_{0}}}$ are the equivalence classes containing $x$ and $y$,
respectively, then in $S(H_0,[y]_{\sim_{H_{0}}})$ their union
$[x]_{\sim_{H_{0}}}\cup [y]_{\sim_{H_{0}}}$ is a larger equivalence
class, while the other equivalence classes remain unchanged. This would
contradict the choice of $H_0$.

Next we show the key observation. If $H_0$ fulfils (\ref{eq4}) then the
distance of $(x,i)$ and $(y,j)$ in $G_{H_0}$ is $\ge 3$ if and only if
$i\neq j$ and $x\sim_{H_0}y$. To see this, observe first that for $i\neq
j$, $d_{G_{H_0}}((x,i),(y,j))\le 2$ if and only if $xy\not\in E(H_0)$ or
there is a $z$ which is adjacent to exactly one of $x,y$. None of these
may occur for $x\sim_{H_0}y$. For $i=j$ and $xy\in E(H_0)$, we have
$d_{G_{H_0}}((x,i),(y,j))=1$, and for $i=j$ and $xy\not\in E(H_0)$, the
existence of $z$ guaranteed by (\ref{eq4}) implies
$d_{G_{H_0}}((x,i),(y,j))=2$. Finally, let $i\neq j$ and
$x\not\sim_{H_0}y$. Then
$d_{G_{H_0}}((x,i),(y,j))=1$, provided
$xy\not\in E(H_0)$. If $xy\in E(H_0)$ then the nonequivalence
of $x$ and $y$ implies the existence of a vertex $z$ which is adjacent
to exactly one of $x,y$, say to $x$. Then
$\{(x,i)(z,i),(z,i)(y,j)\}\subset E(G_{H_0})$ and
$d_{G_{H_0}}((x,i),(y,j))=2$.

Now we complete the proof of the theorem. We let $H'_0=S(H',B)$ be a
graph switching equivalent to $H'$ with a coarsest possible equivalence
$\sim_{H'_0}$. Since $G_H\cong G_{H'}$ by the assumption and
$G_{H}\cong G_{H_0}$ and $G_{H'}\cong G_{H'_0}$ according to the first
part of this theorem, we have $G_{H_0}\cong G_{H'_0}$.

Let $f:V(G_{H_0})\rightarrow V(G_{H'_0})$, $f(x,i)=(f_1(x,i),f_2(x,i))$
be an isomorphism of $G_{H_0}$ and $G_{H'_0}$. Since $f$ preserves
distances, $H'_0$ must have equivalence classes of $\sim_{H'_0}$ of the
same sizes as $H_0$, and $f_2(x,i)=f_{2}(y,i)$ whenever $x\sim_{H_0}y$.
It follows that for $C=\{x|f_2(x,1)=2\}$, the mapping $g$ defined by
$$g(x)=f_1(x,1), \;x\in V(H_0)$$
is an isomorphism of $H_0$ onto $S(H'_0,C)$. Hence $H_0$ and $H'_0$, and
consequently also $H$ and $H'$, are switching equivalent.

\end{pf}



\medskip
\noindent
{\bf Examples.}

(i) There is no graph with 3 vertices switchable to its complement, and
thus (\ref{eq1}) has no solution for $n=3$. More generally, it is easy
to show that if $H$ is switchable to its complement then $n$ is even or
$n\equiv 1\mbox{ mod } 4$. Therefore (\ref{eq1}) has no solution for
$n\equiv 3\mbox{ mod } 4$.

(ii) If $G_1$ and $G_2$ are selfcomplementary graphs then their disjoint
union $G_1+G_2$ is switchable to its complement ($G_1\oplus G_2$ - the
complete join or Zykov sum of $G_1$ and $G_2$). Thus $C_5+K_1$ is
switchable to its complement $W_5$ (the 5-wheel) and this pair gives
rise to the solution
$$K_{12}=2Ico+6K_2$$
of (\ref{eq1}).

\medskip
One can ask how difficult it is to test the condition of
Theorem~\ref{sw}. It is well known that switching equivalence is
isomorphism-complete~\cite{CC},
and we have the similar result about switchability
to complements:

\begin{thm}
The following problem

Instance: A graph $H$.

Question: Is $H$ switchable to its complement?\\
is isomorphism-complete.
\end{thm}

\begin{pf}
Being a special case of switching equivalence, it is obvious that our
problem is not harder then isomorphism test. To show that it is at least
that hard, we use the well known fact that testing selfcomplementarity
of graphs is isomorphism-complete:

Given a graph $G$, in order to decide whether $G\cong \bar{G}$, we
consider the complete join of two copies of $G$, $G'=G\oplus G=
(V(G)\times\{0,1\},\{(h,i)(h',j)|i\neq j\mbox{ or }hh'\in E(G)\})$.
Without loss of generality we assume that both $G$ and its complement
$\bar G$ are connected (otherwise they could not be isomorphic). We
claim that $G\cong\bar{G}$ if and only if $G'$ is switching equivalent
to $\bar{G'}$.

If $G$ is  selfcomplemetary then $\bar{G'}=\bar{G}+\bar{G}\cong G+G=
S(G',V(G)\times\{0\})$.

Suppose $\bar{G'}\cong S(G',A)$ for some $A\subset V(G')$. Since
$\bar{G'}$ consists of two connected components of size $|V(G)|$ and
$S(G',A)$ has all edges between $A\cap (V(G)\times\{0\})$ and
$A\cap (V(G)\times\{1\})$  (and between $(V(G)\times\{1\})-A$ and
($V(G)\times\{0\})-A$), there must be no edges between $(V(G)\times\{0\})-A$
and $(V(G)\times\{0\})\cap A$ (and between $(V(G)\times\{1\})-A$
and $(V(G)\times\{1\})\cap A$) in $S(G',A)$. Then for $i=0,1$,
$A\subset (V(G)\times\{i\})$ or $A\cap (V(G)\times\{i\})=\emptyset$
(otherwise $\bar G$ would not be connected), and the only possibilities
are $A=V(G)\times\{0\}$ or $A=V(G)\times\{1\}$. In both cases
$S(G',A)=G+G$ and $S(G',A)$ is isomorphic to $\bar{G'}=\bar{G}+\bar{G}$
only if $G\cong G'$.
\end{pf}

Our approach often exhibits an interesting additional property of the
solution of (\ref{eq1}). The following is the key observation:

\begin{prop}
\label{fact}
If $n$, the number of vertices of $H$, is even then the chromatic index
of $G_H$ is $n-1$ (i.e., $G_H$ is Vizing class 1).
\end{prop}

\begin{pf}
Let $M_1,M_2,\ldots,M_{n-1}$ be a 1-factorization of the complete graph
on the vertex $V(H)$. Define $F_t=\{(h,i)(h',j)|(h,i)(h',j)\in E(G_H),
hh'\in M_t\}$ for $t=1,2,\ldots,n-1$. Then $F_1,F_2,\ldots,F_{n-1}$ is a
1-factorization of $G_H$.
\end{pf}

Incidently, this result proves that the chromatic index
of Icosahedron is 5. Combining 5
solutions of (\ref{eq1})
$$K_{12} = 2Ico + 6K_2$$
in such a way that the five matchings $6K_2$ factorize a copy of
Icosahedron, we obtain the following solution of (\ref{eq2}):
$$5K_{12} = 11Ico.$$
This is a particular instance of graph designs introduced and studied by
Hell and others ~\cite{H}. (A graph design $kG=tH$ is a system $\cal H$
of $k$
subgraphs of a graph $H$, each of them isomorphic to $G$, such that
every edge of $H$ belongs to exactly $t$ graphs of $\cal H$. In this
sense Balanced Incomplete Block Designs, which obviously motivated the
definition of Graph Designs, are graph designs of type
$bK_{n}=\lambda K_{v}$. It is natural to talk about Spanning Graph
Designs if in addition to $kG=tH$, the order of $G$ is the same as the
order of $H$. Thus
the solutions of (\ref{eq2}) are Spanning Graph Designs of a special
type.)



Theorem~\ref{sw} and Proposition~\ref{fact} immediately yield:

\begin{thm}\label{swsol}
Let $H$ be a graph of even order switchable to its complement.
Then $G_H$ provides a solution to (\ref{eq2}), i.e.
$$(2n-1)G_H=(n-1)K_{2n}.$$
\qed
\end{thm}

\noindent
{\bf Remarks}
Theorem~\ref{swsol} suggests the following problems, some of which may
be of an independent interest:

\begin{pr}\label{prswchi}
Suppose that $H$ is switching equivalent to its complement. Does it
follow that $\chi'(G_H)=n-1$?
\end{pr}

By Proposition~\ref{fact}, this is a problem for odd $n$'s only. Thus
the smallest example is $C_5$, for which the problem has an affirmative
solution depicted in Figure~\ref{figgc5}.
Note that $C_5$ and $K_1+P_3$
are switching equivalent and hence the graphs $G_{K_1+P_3}$ and $G_{C_5}$
are isomorphic.
Thus $G_{C_5}$ presents a
solution to (\ref{eq2}) for $n=5$.

\begin{figure}[ht]
\begin{center}
\thinlines%\thicklines
\unitlength=1.00mm
\begin{picture}(76.41,66.41)
\put(5.00,35.00){\line(2,-3){20.00}}
\put(25.00,5.00){\line(0,1){60.00}}
\put(25.00,65.00){\line(-2,-3){20.00}}
\put(5.00,35.00){\line(2,-1){20.00}}
\put(55.00,65.00){\line(2,-3){20.00}}
\put(75.00,35.00){\line(-2,-3){20.00}}
\put(55.00,5.00){\line(0,1){60.00}}
\put(55.00,45.00){\line(2,-1){20.00}}
\put(75.00,35.00){\line(-2,-1){20.00}}
\put(25.00,45.00){\line(-2,-1){20.00}}
\put(5.00,35.00){\circle*{2.83}}
\put(25.00,65.00){\circle*{2.83}}
\put(55.00,65.00){\circle*{2.83}}
\put(55.00,45.00){\circle*{2.83}}
\put(25.00,45.00){\circle*{2.83}}
\put(25.00,25.00){\circle*{2.83}}
\put(55.00,25.00){\circle*{2.83}}
\put(25.00,5.00){\circle*{2.83}}
\put(55.00,5.00){\circle*{2.83}}
\put(75.00,35.00){\circle*{2.83}}
\put(12.00,49.00){\makebox(0,0)[cc]{1}}
\put(14.00,42.00){\makebox(0,0)[cc]{2}}
\put(14.00,33.00){\makebox(0,0)[cc]{3}}
\put(11.00,23.00){\makebox(0,0)[cc]{4}}
\put(23.00,53.00){\makebox(0,0)[cc]{3}}
\put(23.00,35.00){\makebox(0,0)[cc]{4}}
\put(23.00,15.00){\makebox(0,0)[cc]{1}}
\put(33.00,58.00){\makebox(0,0)[cc]{2}}
\put(30.00,51.00){\makebox(0,0)[cc]{4}}
\put(30.00,41.00){\makebox(0,0)[cc]{1}}
\put(46.00,57.00){\makebox(0,0)[cc]{2}}
\put(50.00,50.00){\makebox(0,0)[cc]{3}}
\put(49.50,41.00){\makebox(0,0)[cc]{2}}
\put(57.00,53.00){\makebox(0,0)[cc]{4}}
\put(57.00,35.00){\makebox(0,0)[cc]{1}}
\put(57.00,15.00){\makebox(0,0)[cc]{3}}
\put(67.00,50.00){\makebox(0,0)[cc]{1}}
\put(65.00,43.00){\makebox(0,0)[cc]{3}}
\put(64.00,32.00){\makebox(0,0)[cc]{4}}
\put(68.00,21.00){\makebox(0,0)[cc]{2}}
\put(25.00,5.00){\line(3,4){30.00}}
\put(25.00,45.00){\line(3,-4){30.00}}
\put(55.00,5.00){\line(-1,2){30.00}}
\put(25.00,65.00){\line(3,-4){30.00}}
\put(25.00,5.00){\line(1,2){30.00}}
\put(55.00,65.00){\line(-3,-4){30.00}}
\end{picture}
\end{center}
\caption{Edge-coloring of $G_{K_1+P_3}$}
\label{figgc5}
\end{figure}

\smallskip
Let us also remark that Problem~\ref{prswchi} has a negative solution if
the switchability condition is dropped. For instance, for $H=K_n$ (and
more generally for every nearly complete graph $H$ with more than
${{n}\choose{2}}-\frac{n-1}{2}$ edges) we have $\chi'(G_H)=n$. This
motivates the following:

\begin{pr}
\label{predgeschi}
Suppose that every graph switching equivalent to $H$ has at most
${{n}\choose{2}}-\frac{n-1}{2}$ edges. Is it then true that
$\chi'(G_H)=n-1$?
\end{pr}

The condition on the number of edges is obviously necessary: For any
$H'$ switching equivalent to $H$, the graphs $G_H$ and $G_{H'}$ are
isomorphic. Thus $H'$ as a subgraph of $G_{H'}$ has itself chromatic
index $n-1$ and $|E(H')|\le{{n}\choose{2}}-\frac{n-1}{2}$ follows. An
evidence towards the validity of our conjecture may be the result of
Plantholt~\cite{Pl} which says that every graph  on $n$
vertices with exactly
${{n}\choose{2}}-\frac{n-1}{2}$ edges is $(n-1)$-edge-colorable (an
$(n-1)$-edge-coloring of $G_H$ then follows).

\smallskip
Let us list two more problems directly related to Theorem~\ref{swsol}:

\begin{pr}
\label{prswsol}
Suppose that $H$ is switchable to its complement. Does $G_H$
solve  (\ref{eq2})?
\end{pr}

This is true for all even $n$, and by inspection of cases also for
$n=5,9,13,\ldots$.

\begin{pr}
\label{prsolchi}
Suppose $G$ is a solution of $(2n-1)G(2n,n-1)=(n-1)K_{2n}$. Does
$\chi'(G)=n-1$?
\end{pr}



\section{Hadamard matrices}\label{Had}

In this section we start analyzing particular solutions of the equation
(\ref{eq2}) which are not induced by switching equivalence via
Theorem~\ref{swsol}. First we consider the case $H=K_n$ and hence
$G_H=K_n+K_n$. We have the following slightly surprising connection to
the existence of Hadamard matrices:

\begin{thm}\label{had1}
Equation (\ref{eq2}) has a solution $G=K_n+K_n$ if and only if there
exists a Hadamard matrix of order $2n$.
\end{thm}

\begin{pf}
Assume that $G_1 + G_2 + \ldots + G_{2n-1} = (n-1)K_{2n}$, $G_i\cong
K_n+K_n$, is a solution of (\ref{eq2}). Let
$V(K_{2n})=V(G_i)=\{1,2,\ldots,2n\}$. For each $j=1,2,\ldots,2n-1$,
define an indicator function
$f_j:\{1,2,\ldots,2n-1\}\rightarrow\{+1,-1\}$ by
\begin{case}
{f_j(x)}{+1}{if $x$ is in the same component of $G_j$ as vertex 1}
{-1}{otherwise.}
\end{case}
Now form an $2n\times(2n-1)$ matrix $A=(a_{ij})$ with $a_{ij}=f_{j}(i)$.

Consider two rows $r_m,r_k$ of $A$. The edge $mk$ of $K_{2n}$ appears in
exactly $n-1$ of the graphs $G_j$ which means that the inner product of
rows $r_m$ and $r_k$ is $-1$. Thus if we extend $A$ to a square matrix
by adding an all 1 column we get a Hadamard matrix.

As one can clearly reverse the argument, we get the statement of the
theorem.
\end{pf}

\noindent
{\bf Remarks.} Note that Hadamard matrices of order $2n$ exist only if
$n$ is even and thus the solutions of type $G=K_n+K_n$ do not provide a
counterexample to Problem~\ref{prsolchi}.

Characterization of orders of Hadamard matrices is currently
considered a tough and important problem of contemporary combinatorics.
Therefore the problem of determining all solutions $G=G(2n,n-1)$ of
equation (\ref{eq2}) seems to be very hard and currently beyond the
reach of standard combinatorial methods.

As mentioned earlier,  equation (\ref{eq2}) is a special case of
Graph Designs. Given a graph $G$, let us define $k_G$ as the minimum $t$
for which the equation
\begin{eqnarray}
aG & = & tK_{|V(G)|} \label{eq5}
\end{eqnarray}
has a solution for some $a$. (For this definition, $G$ does not have to
be regular.) For $G=G(2n,n-1)$, the degrees of $G$ and $K_{2n}$ are
relatively prime and hence $k_G\ge n-1$. Equation (\ref{eq2}) is thus
asking for graphs with minimum possible $t$. Note also that $k_G$ is
finite for every $G$ -- obviously $t_G\le 2|E(G)|\cdot(|V(G)|-2)!$
(taking all $|V(G)|!$ copies of $G$ on its vertex set). The following
problem is then of particular interest:

\begin{pr}\label{prtkn}
Determine upper bounds on $k_{K_n+K_n}$. In particular, is
$\frac{k_{K_n+K_n}}{n-1}$ bounded by an absolute constant?
\end{pr}

Another more general extremal problem suggests itself:

\begin{pr}\label{prtmax}
Give estimates on $k_n=\max\{k_G:|V(G)|=n\}$. Is it an exponential
function of $n$?
\end{pr}

\section{Bipartite case and Hadamard matchability}\label{match}


\begin{figure}[ht]
\begin{center}
\thinlines%\thicklines
\unitlength=.50mm
\begin{picture}(128.00,83.00)
\put(13.00,10.00){\line(1,0){20.00}}
\put(33.00,10.00){\line(0,1){30.00}}
\put(33.00,40.00){\line(-1,0){20.00}}
\put(13.00,40.00){\line(1,-1){10.00}}
\put(23.00,30.00){\line(1,1){10.00}}
\put(13.00,40.00){\line(0,-1){30.00}}
\put(13.00,10.00){\line(1,1){10.00}}
\put(23.00,20.00){\line(1,-1){10.00}}
\put(23.00,20.00){\line(0,1){10.00}}
\put(33.00,10.00){\circle*{2.00}}
\put(33.00,40.00){\circle*{2.00}}
\put(23.00,30.00){\circle*{2.00}}
\put(23.00,20.00){\circle*{2.00}}
\put(13.00,10.00){\circle*{2.00}}
\put(13.00,40.00){\circle*{2.00}}
\put(46.00,52.00){\line(1,0){20.00}}
\put(66.00,52.00){\line(0,1){30.00}}
\put(66.00,82.00){\line(-1,0){20.00}}
\put(46.00,82.00){\line(1,-1){10.00}}
\put(56.00,72.00){\line(1,1){10.00}}
\put(46.00,82.00){\line(0,-1){30.00}}
\put(46.00,52.00){\line(1,1){10.00}}
\put(56.00,62.00){\line(1,-1){10.00}}
\put(56.00,62.00){\line(0,1){10.00}}
\put(76.00,82.00){\line(1,-2){10.00}}
\put(86.00,62.00){\line(1,2){10.00}}
\put(96.00,82.00){\line(-2,-3){20.00}}
\put(76.00,52.00){\line(1,2){10.00}}
\put(86.00,72.00){\line(1,-2){10.00}}
\put(96.00,52.00){\line(-2,3){20.00}}
\put(76.00,82.00){\circle*{2.00}}
\put(96.00,82.00){\circle*{2.00}}
\put(86.00,72.00){\circle*{2.00}}
\put(86.00,62.00){\circle*{2.00}}
\put(96.00,52.00){\circle*{2.00}}
\put(76.00,52.00){\circle*{2.00}}
\put(66.00,52.00){\circle*{2.00}}
\put(66.00,82.00){\circle*{2.00}}
\put(56.00,72.00){\circle*{2.00}}
\put(56.00,62.00){\circle*{2.00}}
\put(46.00,52.00){\circle*{2.00}}
\put(46.00,82.00){\circle*{2.00}}
\put(40.00,67.00){\makebox(0,0)[rc]{$K_6\;=\;$}}
\put(72.00,67.00){\makebox(0,0)[cc]{$+$}}
\put(7.00,25.00){\makebox(0,0)[rc]{$2$}}
\put(47.00,10.00){\line(1,0){20.00}}
\put(67.00,10.00){\line(0,1){30.00}}
\put(67.00,40.00){\line(-1,0){20.00}}
\put(47.00,40.00){\line(1,-1){10.00}}
\put(47.00,10.00){\line(1,1){10.00}}
\put(57.00,20.00){\line(0,1){10.00}}
\put(67.00,10.00){\circle*{2.00}}
\put(67.00,40.00){\circle*{2.00}}
\put(57.00,30.00){\circle*{2.00}}
\put(57.00,20.00){\circle*{2.00}}
\put(47.00,10.00){\circle*{2.00}}
\put(47.00,40.00){\circle*{2.00}}
\put(97.00,10.00){\line(0,1){30.00}}
\put(77.00,40.00){\line(1,-1){10.00}}
\put(87.00,30.00){\line(1,1){10.00}}
\put(77.00,40.00){\line(0,-1){30.00}}
\put(77.00,10.00){\line(1,1){10.00}}
\put(87.00,20.00){\line(1,-1){10.00}}
\put(97.00,10.00){\circle*{2.00}}
\put(97.00,40.00){\circle*{2.00}}
\put(87.00,30.00){\circle*{2.00}}
\put(87.00,20.00){\circle*{2.00}}
\put(77.00,10.00){\circle*{2.00}}
\put(77.00,40.00){\circle*{2.00}}
\put(107.00,10.00){\line(1,0){20.00}}
\put(127.00,40.00){\line(-1,0){20.00}}
\put(117.00,30.00){\line(1,1){10.00}}
\put(107.00,40.00){\line(0,-1){30.00}}
\put(117.00,20.00){\line(1,-1){10.00}}
\put(117.00,20.00){\line(0,1){10.00}}
\put(127.00,10.00){\circle*{2.00}}
\put(127.00,40.00){\circle*{2.00}}
\put(117.00,30.00){\circle*{2.00}}
\put(117.00,20.00){\circle*{2.00}}
\put(107.00,10.00){\circle*{2.00}}
\put(107.00,40.00){\circle*{2.00}}
\put(40.00,25.00){\makebox(0,0)[cc]{$=$}}
\put(72.00,25.00){\makebox(0,0)[cc]{$+$}}
\put(102.00,25.00){\makebox(0,0)[cc]{$+$}}
\end{picture}
\end{center}
\caption{The prism}
\label{prism}
\end{figure}

In this section we consider the next simplest case of
$G(2n,n-1)=K_{n,n}-nK_2$ (the complete bipartite graph minus a perfect
matching, sometimes called the Hiraguchi graph) which arises as $G_H$
for the edgless graph $H$ on $n$ vertices.

\medskip
{\bf Example.} Consider again $n=3$. We have $K_{3,3}-3K_2=C_6$. Since
the complement of $C_6$ is the prism which can be double covered by 3
copies of $C_6$ (cf. Figure~\ref{prism}), we have
$$5C_6=2K_6.$$
Thus we see that not every solution of equation (\ref{eq2}) is induced
by \e\ lines via solutions of (\ref{eq1}) and Theorem~\ref{swsol}.

\medskip
In order to analyze the feasible values of $n$ for which
$G={K_{n,n}-nK_2}$ solves (\ref{eq2}), we introduce two notions about
matrices. First, a $\pm1$ matrix is called {\em column balanced} if
every column contains the same number of symbols $+1$ and $-1$. Let $A$
be a column balanced $2n\times m$ matrix and let $d_{i,j}$ denote the
Hamming distance of the $i$-th and $j$-th row of $A$. Counting the sum
of these distances columnwise, we see that
$$\sum_{i,j\in\{1,2,\ldots,2n\}}d_{i,j}= m\cdot n^2.$$
We say that $A$ is {\em matchable} if it is possible to equalize the row
distances by removing a perfect matching in each column, i.e., if there
exist $m$ sets $M_{k}\subset{\{1,2,\ldots,2n\}\choose{2}}$, each
containing $n$ disjoint pairs, such that
$$\mbox{(i) }\{i,j\}\in M_{k}\mbox{ implies }A_{i,k}\cdot A_{j,k}=-1\mbox{ and}$$
$$\mbox{(ii) }d_{i,j}-|\{k:\{i,j\}\in M_k\}|\;=\;\frac{m(n-1)}{2n-1}.$$
(The matchings are understood as a device to reduce distances of rows of $A$.
If the $i$-th and $j$-th row differ in the
$k$-th coordinate, then the occurrence of
$\{i,j\}$ in $M_k$ reduces the distance $d_{ij}$ by one. The total reduction is
then $mn$ and the sum of the reduced distances is $mn^2-mn$. Hence
$\frac{m(n-1)}{2n-1}=\frac{mn^2-mn}{{{2n}\choose{2}}}$ is the average
reduced row
distance in $A$. Obviously, the number of columns of a matchable matrix is
divisible by
$2n-1$ and a necessary condition for a $2n\times m$ matrix to be
matchable is that the Hamming distance of any two rows is
$\ge \frac{m(n-1)}{2n-1}.$) The role of these notions is captured by the
following observation:

\begin{obs}\label{matchob}
The graph ${K_{n,n}-nK_2}$ solves equation (\ref{eq2}) if and only if
there exists a column balanced matchable matrix of type $2n\times(2n-1).$
\end{obs}

\begin{pf}
Let $G_1,G_2,\ldots,G_{2n-1}$ be subgraphs of $K_{2n}$ isomorphic to
$K_{n,n}-nK_2$ such that every edge of $K_{2n}$ belongs to exactly $n-1$
of them. Assume $V(K_{2n})=\{1,2,\ldots,2n\}$ and define a
$2n\times(2n-1)$ matrix $A$ by
\begin{case}
{A_{ik}\;=}{+1}{if $i$ lies in the same part of $G_{k}$ as 1}
{-1}{otherwise.}
\end{case}
Then $A$ is obviously column balanced. The matchings $M_{k}$ such
that $G'_k=G_k\cup\{ij|\{i,j\}\in M_k\}\simeq K_{n,n}$ satisfy (i-ii)
and $A$ is matchable, since $\frac{m(n-1)}{2n-1}=n-1$ for $m=2n-1$.

On the other hand, the graphs $G_k$ can be read out straightforwardly
from columns of a column balanced matchable $2n\times(2n-1)$ matrix.
\end{pf}

\smallskip\noindent
{\bf Example.} The $4\times 3$ matrix
$$A=\left(\begin{array}{ccc}+1&+1&+1\\ +1&-1&-1\\ -1&+1&-1\\
-1&-1&+1\end{array}\right)$$
is column balanced and all row distances are 2. The matchings
$M_{1}=\{\{1,3\},\{2,4\}\}, M_2=\{\{1,4\},\{2,3\}\}, M_3=\{\{1,2\},\{3,4\}\}$
depicted in Figure~\ref{morg} show that $A$ is matchable. Therefore
$K_{2,2}-2K_2=C_4$ solves (\ref{eq2}) for $n=2$.

This $A$ is not the only matchable matrix of size $4\times 3$. Another
example is
$$B=\left(\begin{array}{ccc}+1&+1&+1\\ +1&-1&+1\\ -1&+1&-1\\
-1&-1&-1\end{array}\right)$$
with matchings
$M_{1}=\{\{1,4\},\{2,3\}\}, M_2=\{\{1,4\},\{2,3\}\},
M_3=\{\{1,3\},\{2,4\}\}$
(cf. Fig.~\ref{morg}~right). Note that this example is cosiderably
different -- the row distances are not all the same (we have $d_{12}=
d_{34}=0, d_{13}=d_{24}=2$ and $d_{14}=d_{23}=3$).

\begin{figure}[h]
\begin{center}
\Ipe{pokus.ipe}
\caption{Column balanced matchable matrices of type $4\times 3$.}
\label{morg}
\end{center}
\end{figure}

Incidentally, in the transposed form the pattern of Figure~\ref{morg} goes
back to Ch. Morgenstern (cf.~\cite{M}):


\begin{figure}[ht]
\begin{center}
\Ipe{morgs.ipe}
\caption{Fisches Nachtgesang.}

\end{center}
\end{figure}

\medskip
Another example is the incidence matrix of the Fano plane (incidences are +1)
completed by an all+1 row to the following $8\times7$ matrix:
$$A=\left(\begin{array}{ccccccc}
+1&+1&+1&+1&+1&+1&+1\\
+1&+1&+1&-1&-1&-1&-1\\
+1&-1&-1&+1&+1&-1&-1\\
+1&-1&-1&-1&-1&+1&+1\\
-1&+1&-1&+1&-1&+1&-1\\
-1&+1&-1&-1&+1&-1&+1\\
-1&-1&+1&+1&-1&-1&+1\\
-1&-1&+1&-1&+1&+1&-1\\
\end{array}\right)$$
This matrix is column balanced and the row distances all equal 4.
It's matchability is left to the reader.

\medskip
Observation~\ref{matchob} suggests how to construct solutions of $(\ref{eq2})$
for $G=K_{n,n}-nK_2$ in two steps:

\smallskip
1. Construct a $2n\times(2n-1)$ column balanced matrix $A$ such that the
Hamming distance of any two rows is $\ge n-1$;

2. Show that $A$ is matchable and use the matchings to derive a
solution.

\smallskip
\noindent
It is surprising that even Step~1 is not obvious for every $n$. We
give two methods for construction of column balanced matrices with large row
distances in Subsection~\ref{col} and we then pay closer attention to
matchability of matrices constructed in this way in the last subsection.
Observing the difficulties in constructing column balanced matrices with
large row distances, we feel that the following generalization may be of some
interest on its own:

\begin{pr}
Given $m,n$ and integers $e_{ij},\; i,j=1,2,\ldots,2n$ such that
$0\le e_{ij}\le m$ for every $i\neq j$ and $\sum_{i\neq j}e_{ij}=mn^2$. Does
there exist a column balanced matrix $A$ of type $2n\times m$ such that
the Hamming distance of any two  rows $r_i, r_j$ is $e_{ij}$? State necessary
and sufficient conditions for the existence of such a matrix $A$.
\end{pr}

\subsection{Column balanced matrices}\label{col}

We show two general constructions of column balanced matrices which are
based on well known combinatorial structures.

\begin{thm}\label{hadbal}
If there exists a Hadamard matrix of order $4m$ then column balanced
matrices of size $2n\times(2n-1)$ with row distances $\ge(n-1)$ exist
for both $n=2m$ and $n=2m+1$.
\end{thm}

\begin{pf}
Suppose $H_{4m}$ is a Hadamard matrix of order $4m$ in the standard form,
i.e., the first row and column contain only symbols +1. Let $A$ be the
truncation of $H_{4m}$, i.e., the matrix obtained from $H_{4m}$ by
deletion of the all+1 column. Then $A$ is column balanced and every
two rows have inner product $-1$, hence any two rows coincide in $2m-1$
coordinates and differ in $2m$ coordinates. Thus $A$ is a $4m\times(4m-1)$
column balanced matrix with row distances $2m\ge(2m-1)$.

\smallskip
Now take any $2m+1$ rows of $H_{4m}$ and construct a matrix $B$ by
adding an all+1 column to these rows. Let $C$ be the tensor product of
$B$ and $(+1,-1)$ ($C$ is the $(4m+2)\times(4m+1)$ matrix whose first
$2m+1$ rows form $B$ and last $2m+1$ rows form $-B$). The row distances
within the first or last $2m+1$ rows are $2m$, the distances of the
complementary rows $C_i=B_i$ and $C_{2m+1+i}=-B_i$
are $4m+1$ and the distances of
the remaining pairs of rows from $B$ and $-B$ are $d_{i,2m+1+j}=4m+1-
d_{i,j}=2m+1$. Hence $C$ is a column balanced matrix with row distances
$\ge 2m$.
\end{pf}

\noindent
{\bf Example} Matrix $A$ from Figure~\ref{morg} is a truncated Hadamard
matrix $H_4$. The same Hadamard matrix yields the following $6\times 5$
matrix via the second construction:
$$\left(\begin{array}{ccccc}
+1&+1&+1&+1&+1\\
+1&+1&-1&-1&+1\\
+1&-1&+1&-1&+1\\
-1&-1&-1&-1&-1\\
-1&-1&+1&+1&-1\\
-1&+1&-1&+1&-1
\end{array}\right).$$

\medskip
The second construction actually suggests a more general construction
which might prove the existence of column balanced $2n\times(2n-1)$
matrices with row distances $\ge (n-1)$ regardless of the existence of
Hadamard matrices:

\begin{obs}
If $A$ is a  $\pm1$ matrix of size $n\times(2n-1)$ with row distances $n-1$ or
$n$, then the tensor product $B$ of $A$ and ${+1\choose -1}$ is a $2n\times
(2n-1)$ column balanced matrix with row distances $\ge n-1$.
\end{obs}

\begin{pf}
Obviously, $B$ is column balanced. The row distances within $A$ and
within $-A$ are $\ge
(n-1)$.
The row
distances of the complementary rows in $A$ and $-A$ are $2n-1$ and the
distances of the remaining pairs from $A$ and $-A$ are $\ge 2n-1-n=n-1$.
\end{pf}

If there exists a matrix $A$ as in the observation, we may suppose that
the first row contains all symbols $-1$. It follows that every other row
contains $n-1$ or $n$ symbols $+1$. Then we  may  view the rows of $A$
as characteristic vectors of sets $A_i\subset\{1,2,\ldots,2n-1\}$. Thus
$A_1=\emptyset$ and $|A_i|\in\{n-1,n\}$ for $i=2,3,\ldots,n$. The
Hamming distance conditions then imply unique restrictions on the
cardinalities of the intersections of $A_i$'s:

If $|A_i|=|A_j|=n$, then $|A_i\cap A_j|=\frac{1}{2}(|A_i|+|A_j|-|A_i\div
A_j|)=\frac{1}{2}(|A_i|+|A_j|-d_H(A_i,A_j))
=\frac{1}{2}(2n-2\lfloor\frac{n}{2}\rfloor)=\lceil\frac{n}{2}\rceil$, as
the symmetric difference of two sets of the same cardinality is even,
and hence $d_H(A_i,A_j)=2\lfloor\frac{n}{2}\rfloor$ in this case.

Similarly, if $|A_i|=|A_j|=n-1$, then
$|A_i\cap A_j|=\frac{1}{2}(|A_i|+|A_j|-|A_i\div
A_j|)
=\frac{1}{2}(2n-2-2\lceil\frac{n-1}{2}\rceil)=\lfloor\frac{n-1}{2}\rfloor$.

If $|A_i|=n$ and  $|A_j|=n-1$, then
$|A_i\cap A_j|=\frac{1}{2}(|A_i|+|A_j|-|A_i\div
A_j|)
=\frac{1}{2}(2n-1-2(\lfloor\frac{n-1}{2}\rfloor+1))=
\lceil\frac{n-1}{2}\rceil$.

\smallskip
Hence the affirmative solution to the next problem would imply the
existence of column balanced $2n\times (2n-1)$ matrices with large row
distances:

\begin{pr}
Do there exist $n-1$ sets $A_i\subset\{1,2,\ldots,2n-1\}$, for any $n\ge 2$,
such that

(i) $|A_i|\in\{n-1,n\}$ for $i=1,2,\ldots,n-1$,

(ii) for $i\neq j$, $|A_i\cap A_j|=\left\{\begin{array}{ll}
\lceil\frac{n}{2}\rceil & \quad \mbox{if } |A_i|=|A_j|=n,\\
\lfloor\frac{n-1}{2}\rfloor & \quad \mbox{if } |A_i|=|A_j|=n-1,\\
\lceil\frac{n-1}{2}\rceil & \quad \mbox{if } |A_i|\neq |A_j|?
\end{array}\right.$
\end{pr}

\medskip
A slightly different construction is based on conference matrices.
Recall that a conference matrix
$C$ of order $n$ is an $n \times n$ orthogonal matrix with diagonal entries $0$
and all other entries $\pm 1$. We say that a conference matrix $C$ is in
{\em standard form} if
all entries in the first row and first column are $+1$ (except the first
entry which is $0$).
It is easy to see that if $C$ is a conference matrix in standard form then
except for the first row and column each row and each column consists of $1$
zero, $n-2 \over 2$ $-1's$ and $n \over 2$ $+1's$.

\begin{obs}\label{conf}
Let $C$ be an $n \times n$ conference matrix in standard form, $B=C-I_n$
and $A$ be the truncation of $B$. Then $A$ is a column balanced matrix of
type $n\times(n-1)$ with row distances $\ge {n \over 2}-1$.
\end{obs}

\begin{pf}
Every column of $C$ (except the first one) has  $n-2 \over 2$ $-1's$ and
$n \over 2$ $+1's$, and so every column of $A$ has $n \over 2$ $-1's$ and
$n \over 2$ $+1's$. Similarly, every row of $A$ (except the first one)
has $n \over 2$ $-1's$ and hence the Hamming distance of the first and any
other row is $n \over 2$. Any other pair of rows of $C$ differ in $n+2 \over 2$
positions, and hence the rows of $A$ (after replacing one zero in each by
-1) will differ in at least $n-2 \over 2$ positions.
\end{pf}


\subsection{Matchability of Hadamard and Conference matrices}\label{hadmatch}

In this section we show that certain classical combinatorial structures yield
matchable
column balanced matrices of type $2n \times (2n-1)$.
In particular we show that Hadamard and Conference matrices derived from
quadratic residues over
 $GF(q)$ (Paley's construction, for more details see~\cite{Mar})
can be used to construct matchable
column balanced matrices of type $2n \times (2n-1)$.
We first attend to
Hadamard matrices. Since the truncation of a Hadamard matrix
(in standard form) is uniquely defined, we say that a Hadamard
matrix is {\em matchable} if its truncation is matchable. We conjecture
that every Hadamard matrix is matchable:

\begin{pr}
Is every \Hm\ matchable? Or at least, is it true that if a \Hm\ of order
$4m$ exists then there also exists a matchable \Hm\ of the same order?
\end{pr}

We support our conjecture by showing that the well known standard
constructions of \H\ matrices give matchable matrices.


\medskip
Let $q$ be a prime power.
We denote by ${\bf 1}=(1,1,\ldots , 1)$ the all-one vector (of appropriate
length, which will be clear from context),
and by $I_n$ the identity matrix of size $n\times n$.
Let  $\chi(x)$ denote the quadratic residue character over $GF(q)$ (i.e.,
$\chi(0)=0$, $\chi(x)=+1$ iff $x=y^2$ for some $y\in GF(q)-\{0\}$ and
$\chi(x)=-1$ otherwise). We define the following matrices over $GF(q)$:

$$R=(\alpha - \beta)_{\alpha,\beta\in GF(q)},$$
            $$Q= (\chi(\alpha - \beta))_{\alpha,\beta\in GF(q)},$$
$$H'_{q+1} = \pmatrix{
0 & {\bf 1} \cr
-{\bf 1}^T & Q \cr
} + I_{q+1}.$$

As shown in \cite{Mar}, $H'_{q+1}$ is a Hadamard matrix of order $q+1$ if
$q\equiv 3\mbox{ mod }4$.
The equivalent
Hadamard matrix in standard form is
$$H_{q+1}=\pmatrix{
1 & {\bf 1} \cr
{\bf 1}^T & -Q - I_q  \cr
}.$$

We denote the first row of this matrix by $H^*$ and the other rows by
$H^\alpha, \alpha \in GF(q)$.

\begin{thm}\label{qres} If $q\equiv 3\mbox{ mod }4$ then the Hadamard
matrix $H=H_{q+1}$ is  matchable.
\end{thm}

\begin{pf} We say that row $H^\alpha$ is matched with row $H^\beta$ in column
$\gamma$ if $\{\alpha, \beta\}\in M_{\gamma}$ (where $M_\gamma$, $\gamma\in
GF(q)$ are the columnwise matchings that witnes matchability of $H$).
As noted
before, in each column of the truncated $(q+1)\times q$ matrix we need to
construct a perfect matching such that every pair of distinct rows is
matched in some column. We set
$$M_\beta=\{\{*,\beta\}\}\cup\{\{\alpha,2\beta-\alpha\}:\alpha\in
GF(q)-\{\beta\}\}, \beta\in GF(q).$$
In other words, in column $\beta$, we match $H^*$ with row $H^\beta$
and
we match row $H^\alpha$, $\alpha\neq \beta$,
with row $H^{2\beta - \alpha}$.
It is simple to describe this matching in terms of the matrix $R$. Each column
of $R$ is a permutation of the $q$ elements of $GF(q)$. In each column we
match the row containing $\alpha$ with the row containing $-\alpha$.
The row containing $0$ is matched with the added top row.
Since $q \equiv \; 3 \mbox{ mod } 4$,  $\chi(-1) = -1$ and hence
$\chi (\alpha - \beta) = - \chi (\beta - \alpha)$ and since
$H_{\beta, \beta} = -1$ our match indeed matches a $+1$ with a $-1$.
Also if $\alpha \not = \alpha',\;\;  2\beta - \alpha \not = 2\beta - \alpha'$.
Therefore in each column we get a perfect matching.

We show that every pair of rows are matched in some column:
Row $H^*$ is matched with row $H^\beta$ in column $\beta$ and rows
$H^\alpha$ and $H^{\gamma}$ are matched in column
$\beta = \frac{\alpha + \gamma}{2}$.
\end{pf}

When $q \equiv \; 1\mbox{ mod }4$ the Hadamard matrix $H$ derived from $Q$
is more complex. We first form the matrix:
$$S_{q+1} = \pmatrix{
0 & {\bf 1} \cr
{\bf 1}^T & Q  \cr
}.$$
This is a symmetric conference matrix of order $q + 1$.
 Let $A$ be the
$(q+1) \times q$ matrix obtained from $S_{q+1} - I_{q+1} $ by deleting the
first column.
We know that $A$ is a column balanced matrix of type $(q+1) \times q$ and the
Hamming distance between the first row and any other row is $q+1 \over 2$.
It is easy to see that  $dist_H
(A^\alpha , A^\beta) = {q+1 \over 2} + \chi(\alpha - \beta)$.

\begin{thm}\label{confmatch} The matrix $A$ is matchable.
\end{thm}

\begin{pf} We denote the first row of $A$ by $A^*$. All other rows and all
columns of $A$ will be indexed by the
corresponding elements of $GF(q)$. We need to show that in each column we can
select a perfect matching so that in all these $q$ matchings the pair
$\{A^*,A^\alpha\}$ is matched once for each $\alpha$ and the pairs
$\{A^\alpha,A^\beta\}$ are matched twice whenever $\chi(\alpha - \beta) = 1$.

Let $\nu \in GF(q)$ be a quadratic non-residue such that $\nu - 1$ is a
quadratic residue in $GF(q)$. It is easy to see that if $q$ is odd then one can
always find such an element.
In column $\alpha$ we match the first row $A^*$ with row $A^\alpha$.
In the matrix
$R$ each column is a permutation of all the elments of $GF(q)$. In each column
we match the row containing a quadratic residue $\alpha$ with the row
containing the element $\nu\alpha$. Clearly in $A$ the first row contains a
$1$ while the second row contains a $-1$, hence this is indeed a perfect
matching in each column. It is easy to see that for each $\alpha \in GF(q)$
the rows
$A^*$ and $A^\alpha$ are matched once. If $\alpha - \beta$ is a quadratic
residue we need to
show that there are two columns $\gamma$ and $\delta$ in which these two rows
are matched.
First let $\gamma = {\nu\beta-\alpha \over \nu -1}$. A simple calculation
shows that

\begin{eqnarray}
 \gamma - \alpha = & {\nu(\beta-\alpha) \over \nu -1} \label{m1}\\
 \alpha - \gamma = & \nu(\beta-\gamma) \label{m2}
\end{eqnarray}


Since $\alpha - \beta$ and $\nu - 1$ are quadratic residues, from $(\ref{m1})$
we get
that $\gamma - \alpha$
is a quadratic non-residue and from (\ref{m2}) we see that $\beta-\gamma$ is a
quadratic residue.
It then follows from (\ref{m2}) that
$A^\alpha$ and $A^\beta$ are matched in column $\gamma$. Similarly, if
we let
$\delta = {\nu\alpha - \beta \over \nu - 1}$ we get that $A^\alpha$ and
$A^\beta$ are also
matched in column $\delta$ and $\delta \ne \gamma$. In these calculations we
use the fact
that if $q \equiv 1\mbox{ mod }4$ then if $\alpha$ is a quadratic residue
then so is $-\alpha$.
\end{pf}


%{\bf remark}. It is easy to see that a different set of matchings
%defined by matching a
%non quadratic residue element $\alpha$ in each column with $\nu\alpha$ can
%also be used
%to show that $A$ is matchable. We use both these matchings in the following
%construction.

%Semprijde lemmaz baton.
\begin{lm}\label{new2}
If a \Hm\ $H$ is  matchable then $H_2*H$ is also
matchable.
\end{lm}

\begin{pf}
Let $M$ be a
negative matching for $H$. We define ${\cal{M}}_{(k,l)}$ in the following way:

$${\cal{M}}_{(1,l)}=\{\{(1,j),(2,j')\}:\{j,j'\}\in M_l\},\; l>1,$$
$${\cal{M}}_{(2,l)}=\{\{(i,j),(i,j')\}:\{j,j'\}\in M_l, i=1,2\},\; l>1,$$
$${\cal{M}}_{(2,1)}=\{\{(1,j),(2,j)\}:j=1,2,\ldots,m\}.$$

It is easy to see that ${\cal M}$ is a
matching for $H_2*H$.
\end{pf}

\begin{cor}
For every $n=2^k$, $k\ge 1$, $G=K_{n,n}-nK_2$ solves (\ref{eq2}).
\end{cor}

\begin{pf}
The \Hm\ of order two $H_2$ is matchable and therefore by induction
$H_n$ (defined
recursively as $H_{2m}=H_2*H_m$) is both  matchable for $n=2^k$. Then
apply Observation~\ref{matchob}.
\end{pf}

\begin{cor}
For every $n=(q+1)\cdot 2^k$,
such that $k\ge 0$ and $q \equiv \; 3\mbox{ mod }4$,
$G=K_{n,n}-nK_2$ solves (\ref{eq2}).
\end{cor}

\begin{pf}
Similar to the previous proof, starting with a matchable
 \Hm\ of order $q+1$ (Theorem~\ref{qres}) and using Lemma~\ref{new2}.
\end{pf}


Another well known fact says that the tensor product of Hadamard matrices
is again a \Hm. A similar result is true about matchability of \H\
matrices.
We need to introduce two auxiliary notions. Let $A$ be
a column balanced $\pm1$ matrix of size $2n\times(2n-1)$. We say that
$A$ is {\em positive matchable} (resp. {\em negative matchable}) if
there exist column-wise matchings $M_k,k=1,2,\ldots,2n-1$ such that
$$\mbox{(i') }\{i,j\}\in M_{k}\mbox{ implies }A_{i,k}\cdot
A_{j,k}=+1\mbox{ (resp. } A_{i,k}\cdot
A_{j,k}=-1\mbox{) and}$$
$$\mbox{(ii') }\mbox{for any two distinct $i,j$, there is exactly one $k$
such that }\{i,j\}\in M_k.$$
We say that a \Hm\ in the standard form
is positive matchable (negative matchable) if its truncation is positive
(negative) matchable.
Note that a \Hm\ is matchable if and only if it is negative
matchable in the sense of this definition.


\medskip\noindent
{\bf Example.} The \Hm\ $H_4$ is both positive and negative matchable,
as shown in Fig.~\ref{posneg4}.

\begin{figure}[ht]
\begin{center}
\Ipe{h4posneg.ipe}
\caption{Positive and negative matchability of $H_4$.}
\label{posneg4}
\end{center}
\end{figure}

\begin{thm}\label{tens}
If \H\ matrices $H$ and $H'$ are both positive matchable
then their tensor product
$H*H'$ is positive matchable as well.
If one of the matrices $H$ and $H'$ is both positive and negative matchable
and the other one is negative matchable
then their tensor product
$H*H'$ is negative matchable as well.
\end{thm}

\begin{pf}
Let $H=(a_{ik})_{i,k=1}^n$ and $H'=(a'_{jl})_{j,l=1}^m$ be \H\ matrices in
standard form (namely, $a_{i1}=a'_{j1}=+1$ for every $i=1,\ldots,n$ and
$j=1,\ldots,m$).
Recall that the tensor product $H*H'$ is the $mn\times mn$ matrix with
entries
$$b_{(i,j),(k,l)}=a_{ik}\cdot a'_{jl}.$$
It is well known and easy to see that the tensor product of \H\ matrices
is again a \Hm.

For each $i,k$, denote by $H'_{i,k}$ the $m\times m$ submatrix of $H*H'$
formed by all entries $b_{(i,j),(k,l)}, j,l=1,\ldots,m$. Clearly, $H'_{i,k}$
is a copy of $H'$ if $a_{i,k}=+1$, and $H'_{i,k} = -H'$
 if $a_{i,k}=-1$.
Let $M_k,
N_k, k=2,3,\ldots,n$  ($M'_l,
M'_l,  l=2,3,\ldots,m$) be
matchings of $H$  ($H'$, resp.) that satisfy (ii').
 We define column-wise matchings ${\cal{M}}_{(k,l)}$ of $H*H'$ as
follows:

$${\cal{M}}_{(1,l)}=\{\{(i,j),(i,j')\}:\{j,j'\}\in M'_l,
i=1,2,\ldots,n\}, l>1,$$
$${\cal{M}}_{(k,1)}=\{\{(i,j),(i',j)\}:\{i,i'\}\in M_k,
j=1,2,\ldots,m\}, k>1,$$
$${\cal{M}}_{(k,l)}=\{\{(i,j),(i',j')\}:\{i,i'\}\in N_k,\{j,j'\}\in N'_l,
\}, k>1, l>1.$$

It is easy to see that ${\cal{M}}$ satisfies (ii'): for any pair of
distinct rows of $H*H'$, say $(i,j)$ and $(i',j')$, there exists exactly
one column $(k,l)$ such that $\{(i,j),(i',j')\}\in {\cal{M}}_{(k,l)}$ --
if $i=i'$, this is $(k,l)=(1,l)$ for the unique $l$ such that
$\{j,j'\}\in M'_l$; if $j=j'$, this is $(k,l)=(k,1)$
for the unique $k$ such that
$\{i,i'\}\in M_k$; and for $i\neq i', j\neq j'$, this is $(k,l)$ for the
unique $k,l$ such that $\{i,i'\}\in N_k$ and $\{j,j'\}\in N'_l$.

Consider any $\{(i,j),(i',j')\}\in{\cal{M}}_{(k,l)}$. We have
$$b_{(i,j),(k,l)}\cdot b_{(i',j'),(k,l)}=a_{ik}\cdot a'_{jl} \cdot
a_{i'k}\cdot a'_{j'l} =a_{ik}\cdot a_{i'k} \cdot
a'_{jl}\cdot a'_{j'l}$$
and we see that ${\cal{M}}$ is positive if all $M,N,M',N'$ are positive
(and also if $M,M'$ are positive and $N,N'$ negative) and ${\cal{M}}$ is
negative if $M,M'$ are negative and exactly one of $N,N'$ is positive
and the other one negative.
\end{pf}

\medskip\noindent
{\bf Example.} Consider $H_2=\left(\begin{array}{cc}
+1 & +1 \\ +1 & -1
\end{array}\right)$ (this is the only \Hm\ whose order is not
divisible by 4). Clearly, $H_2$ is negative matchable (but not positive
matchable). Since $H_4$ is both positive and negative matchable,
it follows from  Theorem~\ref{tens} that $H_8=H_2*H_4$ is
negative matchable. The matrix $H_8$ is positive matchable as well, as
it follows from an extension of Lemma \ref{new2}:

\begin{lm}
If a \Hm\ $H'$ is both positive and negative matchable then $H_2*H'$ is
positive matchable.
\end{lm}

\begin{pf}
As in the proof of Theorem~\ref{tens}, let $M'$ be positive and $N'$
negative matching for $H'$. Let us first define ${\cal{M}}_{(k,l)}$ for
$l>1$ as in the
previous proof:

$${\cal{M}}_{(1,l)}=\{\{(i,j),(i,j')\}:\{j,j'\}\in M'_l\},$$
$${\cal{M}}_{(2,l)}=\{\{(1,j),(2,j')\}:\{j,j'\}\in M'_l\}.$$

So far every pair $\{(i,j),(i',j')\}, i,i'=1,2,\; j,j'=1,2,\ldots,m$
occurs in exactly one ${\cal{M}}_{(k,l)}$, except for the pairs
$\{(1,j),(2,j)\}, j=1,2,\ldots,m$. To cover also these pairs, we
modify  $\cal M$ in column $(1,2)$ and then complete the matching in
column $(2,1)$. Thus we set

$$\overline{{\cal{M}}}_{(1,2)}=\{\{(1,j),(2,j)\}:j=1,2,\ldots,m\},$$
$$\overline{{\cal{M}}}_{(2,1)}={\cal{M}}_{(1,2)},$$
$$\overline{{\cal{M}}}_{(k,l)}={\cal{M}}_{(k,l)},\; (k,l)\neq(1,2),(2,1).$$

It is straightforward to verify that $\overline{\cal M}$ is a positive
matching for $H_2*H'$.
\end{pf}

Some of our other results on matchability of \H\  matrices can be extended
to positive matchability as well. E.g., it is true that for every $n=2^k$,
the \Hm\ $H_n=H_2^k$ is positive matchable. One may actually ask if every
negative matchable \Hm\ is also positive matchable.


Another daring  conjecture would be that every column balanced
$2n\times(2n-1)$ matrix with row distances $\ge (n-1)$ is matchable. The
truth is, however, that we were not able to find any counterexample to
this conjecture.

\bigskip
\noindent
{\large\bf Acknowledgment.}
\quad The authors thank Andrzej Proskurowski, Walt Wallis and Rob Craigen 
for fruitful discussions.

\begin{thebibliography}{aaa}

\bibitem{CC}
Colbourn, C., J., Corneil, D., G.: {\sl On deciding switching equivalence
     of graphs}, Discrete Appl. Math. 2 (1980), No. 3, 181-184


\bibitem{Mar}
Hall, M. Jr.: Combinatorial Theory, Wiley, New York, 1986


\bibitem{H}
Hell, P., Rosa, A.: {\sl Graph decompositions, handcuffed prisoners and
     balanced p-designs}, Discrete Math. 2 (1972), No. 3, 229-252.


\bibitem{KNZ}
Kratochv\'{\i}l,J., Ne\v{s}et\v{r}il,J., Z\'yka,O.: {\sl On the computational
   complexity of Seidel's switching},
      In: Combinatorics, Graphs and
   Complexity (M.Fiedler and J.Ne\v{s}et\v{r}il eds.),
   Proceedings 4th Czechoslovak
   Symposium on Combinatorics, Prachatice 1990, Annals of Discrete Math.
   51, North Holland, Amsterdam, 1992 (MR 93j:05156)

\bibitem{M}
Morgenstern,Ch.: Fisches Nachtgesang, in {\sl Alle Galgenlieder}, Aufban-Verlag,
Berlin und Weimar, 1983, p. 14

\bibitem{Pl}
Plantholt,M.: {\sl The chromatic index of graphs with a spanning star}, 
J. Graph Theory 5 (1981), 5-13

\bibitem{S}
Seidel,J.J.: {\sl Discrete non-Euclidean geometry}, in Handbook of Incidence Geometry
      ed. F. Buekenhout, North Holland publ.

\bibitem{ST}
Seidel,J.J.: {\sl A survey of two-graphs,} Teorie combinatorie, ed. B. Segre,
International Colloq. 1973, Rome, Atti Conv. Lincei,  Vol. 17, Academia
Nazionale dei Lincei, Rome, 1973, pp. 481-511

\bibitem{sst}
Seidel,J.J., Taylor, D.E.: {\sl Two-graphs: A second survey},
in Algebraic methods
      in graph theory, L. Lovasz and V.T. Sos, eds. Elsevier Science Publishers,
      (1981), 689-711

\end{thebibliography}
\end{document}

\section{Introduction}\label{intr}
\begin{pr}\label{pr1} Problem o isomorfismu G a tilde G
\begin{thm}\label{sw} Veta G tilde G iso iff H switchable to complement
\begin{obs}\label{gcomp} G_comp H = tildeG_H
\begin{thm}\label{switchiso} G_H iso G_H' iff H switch eq H'
\begin{prop} \label{fact}  n sudy pak chi'(G_H)=n-1
\begin{thm}\label{swsol} H switch + n sude then G_H is solution
\begin{pr}\label{prswchi} probl H switch then ch'G_H=n-1?
\begin{pr}\label{predgeschi} probl every graph sw eq s H few edges then
                             chi'?
\begin{pr}\label{prswsol} H sw then G_H soltuion?
\begin{pr}\label{prsolchi} G solution then ch'G?
\section{Hadamard solutions}\label{Had}
\begin{thm}\label{had1} K_n+K_n iff Hadamard
\begin{pr}\label{prtkn} probl t_{K_n+K_n}
\begin{pr}\label{prtmax} probl max t_G
\section{Bipartite case and Hadamard matchability}\label{match}
\begin{obs}\label{matchob} K_{n,n}-nK_2 is sol iff exists matchable
\subsection{Column balanced matrices}\label{col}

\subsection{Matchability of Hadamard matrices}\label{hadmatch}
\begin{thm}\label{hadbal} exists had implies column balanced
\begin{thm}\label{conf} moshe conference matricse
\begin{thm}\label{tens} tensor product of match had is match


\vskip 10 pt%moje varianta
$$\pmatrix {
+1 & +1 & +1 & +1 & +1 & +1  & +1 & +1 & +1 & +1 & +1 & +1 \cr
+1 & +1 & +1 & -1 & -1 & +1  & -1 & -1 & +1 & -1 & -1 & +1 \cr
+1 & +1 & +1 & +1 & -1 & -1  & -1 & +1 & -1 & +1 & -1 & -1 \cr
+1 & -1 & +1 & +1 & +1 & -1  & -1 & -1 & +1 & -1 & +1 & -1 \cr
+1 & -1 & -1 & +1 & +1 & +1  & -1 & -1 & -1 & +1 & -1 & +1 \cr
+1 & +1 & -1 & -1 & +1 & +1  & -1 & +1 & -1 & -1 & +1 & -1 \cr
+1 & -1 & -1 & -1 & -1 & -1  & -1 & +1 & +1 & +1 & +1 & +1 \cr
+1 & -1 & +1 & -1 & -1 & +1  & +1 & -1 & -1 & +1 & +1 & -1 \cr
+1 & +1 & -1 & +1 & -1 & -1  & +1 & -1 & -1 & -1 & +1 & +1 \cr
+1 & -1 & +1 & -1 & +1 & -1  & +1 & +1 & -1 & -1 & -1 & +1 \cr
+1 & -1 & -1 & +1 & -1 & +1  & +1 & +1 & +1 & -1 & -1 & -1 \cr
+1 & +1 & -1 & -1 & +1 & -1  & +1 & -1 & +1 & +1 & -1 & -1 \cr}$$

////////---------------

When $q \equiv \; 1\mbox{ mod }4$ the Hadamard matrix $H$ derived from $Q$
is more complex. We first form the matrix
$$S_{q+1} = \pmatrix{
0 & {\bf 1} \cr
{\bf 1}^T & Q  \cr
.}$$
This is a symmetric conference matrix of order $q + 1$.
We form the matrix $H'_{2q+2}$ by the following tensor product
$$H'_{2q+2} = S_{q+1}  \times \pmatrix {1 & 1 \cr
1 & -1}
 + I_{2q+2} \times \pmatrix {1 & -1 \cr
-1 & -1} .$$
It can be easily shown (see~\cite{Mar}) that $H'_{2q+2}$ is a symmetric
Hadamard matrix. To obtain the equivalent Hadamard matrix $H_{2q+2}$ in
standard form we need to multiply the second row and the second
column by $-1$.
The figure below shows the Hadamard matrix of order $12$ obtained from $GF(5)$
by this process.



\vskip 10 pt
$$\left(\begin{array}{|cc|cc|cc|cc|cc|cc|}
+1 & +1 & +1 & +1 & +1 & +1 & +1 & +1 & +1 & +1 & +1 & +1 \cr
+1 & -1 & -1 & +1 & -1 & +1 & -1 & +1 & -1 & +1 & -1 & +1 \cr
+1 & -1 & +1 & -1 & +1 & +1 & -1 & -1 & -1 & -1 & +1 & +1 \cr
+1 & +1 & -1 & -1 & +1 & -1 & -1 & +1 & -1 & +1 & +1 & -1 \cr
+1 & -1 & +1 & +1 & +1 & -1 & +1 & +1 & -1 & -1 & -1 & -1 \cr
+1 & +1 & +1 & -1 & -1 & -1 & +1 & -1 & -1 & +1 & -1 & +1 \cr
+1 & -1 & -1 & -1 & +1 & +1 & +1 & -1 & +1 & +1 & -1 & -1 \cr
+1 & +1 & -1 & +1 & +1 & -1 & -1 & -1 & +1 & -1 & -1 & +1 \cr
+1 & -1 & -1 & -1 & -1 & -1 & +1 & +1 & +1 & -1 & +1 & +1 \cr
+1 & +1 & -1 & +1 & -1 & +1 & +1 & -1 & -1 & -1 & +1 & -1 \cr
+1 & -1 & +1 & +1 & -1 & -1 & -1 & -1 & +1 & +1 & +1 & -1 \cr
+1 & +1 & +1 & -1 & -1 & +1 & -1 & +1 & +1 & -1 & -1 & -1 \cr
\end{array}\right)$$

\begin{thm}\label{qres1} The Hadamard matrix $H=H_{2q+2}$ is matchable.
\end{thm}

\begin{pf} For convenience we shall number the rows and columns by the
integers $1,\ldots,2q+2$. In the second column of $H$ we match row
$H^{2k-1}$
with row  $H^{2k}$, $k=1,2,\ldots,q+1$.
 Our match will proceed by matching square pairs
of $2\times 2$ blocks in adjacent columns.
The top two rows are matched in columns
$2k-1$ and $2k$ ($k=2,3,\ldots,q+1$) as follows:

(*)  $H^1$ is matched with $H^{2k}$ in column number $2k - 1$ and with
$H^{2k-1}$ column number $2k$.
$H^2$ is matched with $H^{2k-1}$ colum number  $2k-1$ and with $H^{2k}$
in column number $2k$.

To describe the remainder of the matchings we use the entries of the matrix
$R = (\alpha - \beta)_{\alpha,\beta\in GF(q)}$.
Let $\nu$ be a primitive root in $GF(q)$, that is
$\nu^{q-1 \over 2} = -1$.  In $R$ every column is a permutation
of the elements of $GF(q)$. Out of these $q$ elements,
$q-1 \over 2$ of the entries in each column are
quadratic residues. We match in each column of $R$ the quadratic residue
$\alpha$ with the entry $\alpha \cdot \nu$ in the same column. Since $\nu$
is a primitive element $\alpha \cdot \nu$ is a not a quadratic residue. This
means that in the matrix  $Q_{\alpha,\beta} = \chi(\alpha - \beta)$ there
is a $1$ in the location corresponding to $\alpha$ and a $-1$ in the location
corresponding to $\alpha \cdot \nu$. This implies that in each column of $Q$
there are exactly $q-1 \over 2$ matches (only the diagonal entry which is $0$
is not matched). For any pair of matched entries in the matrix $R$ we do the
following: consider the two $2\times 2$ blocks in the corresponding locations in
the matrix $H$. If for instance $\alpha$ is in location $(i,j)$ in $R$ then
the corresponding $2\times 2$ block in $H$ will be
in rows $2i +1, 2i+2$ and in columns $2j +1, 2j+2$. Similarly, the location of
the $2\times 2$ block corresponding to $\alpha \cdot \nu$ in location $(k,j)$ in
$R$  is in rows $2k+1, 2k+2$ and columns $2j +1, 2j+2$.
Then we match
the rows $H^{2i+1}$ with $H^{2k +2}$ and
$H^{2i+2}$ with $H^{2k+1}$ in column number $2j+1$, and $H^{2i+1}$ with
$H^{2k+1}$
and $H^{2i+2}$ with $H^{2k+2}$ in column number $2j+2$. It follows from the
definition of $H$ that these are proper matches.

It remains to show that every pair of rows are matched. From (*) it is clear
that rows $H_1$ and $H_2$ are matched with every row $H_m$. Let $i > j > 2$
be any pair of row numbers of the matrix $H$. If $i = 2m-1$ and $j = 2m-2$ then
these rows are matched in column number $1$ else we look at the source entries
of $i$ and $j$ in the matrix $R$. Clearly they come from different  rows in
$R$. Let the source row of $i$ be $\alpha$ and the source row of $j$ be
$\beta$. In order to find the column in which  $H^i$ is matched with $H^j$
we first need to identify the column in which $\alpha$ and $\beta$ are matched
in $R$.
\end{pf}


----------

(cf. Fig.~\ref{h12pos} for positive matchings
and Theorem~\ref{qres} for negative matchings).
\end{pf}

\begin{figure}[ht]
\begin{center}
\Ipe{h12pos.ipe}
\caption{Positive  matchability of $H_{12}$.}
\label{h12pos}
\end{center}
\end{figure}

\noindent
{\bf Example} The positive matchings of $H_{12}$ depicted in Fig.~\ref{h12pos}
are
$$M_2=\{\{1,2\},\{3,5\},\{4,6\},\{7,8\},\{9,11\},\{10,12\}\},$$
$$M_3=\{\{1,3\},\{2,8\},\{4,5\},\{6,12\},\{7,9\},\{10,11\}\},$$
$$M_4=\{\{1,4\},\{2,11\},\{3,5\},\{6,9\},\{7,10\},\{8,12\}\},$$
$$M_5=\{\{1,8\},\{2,6\},\{3,7\},\{4,11\},\{5,9\},\{10,12\}\},$$
$$M_6=\{\{1,12\},\{2,9\},\{3,8\},\{4,7\},\{5,11\},\{6,10\}\},$$
$$M_7=\{\{1,6\},\{2,9\},\{3,12\},\{4,6\},\{5,10\},\{8,11\}\},$$
$$M_8=\{\{1,8\},\{2,7\},\{3,12\},\{4,11\},\{5,6\},\{9,10\}\},$$
$$M_9=\{\{1,11\},\{2,4\},\{3,10\},\{5,8\},\{6,9\},\{7,12\}\},$$
$$M_{10}=\{\{1,10\},\{2,11\},\{3,7\},\{4,9\},\{5,8\},\{6,12\}\},$$
$$M_{11}=\{\{1,9\},\{2,3\},\{4,12\},\{5,10\},\{6,7\},\{8,11\}\},$$
$$M_{12}=\{\{1,5\},\{2,10\},\{3,4\},\{6,8\},\{7,11\},\{9,12\}\}.$$
%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
