\documentstyle{article}
\setlength{\textwidth}{5in}
\setlength{\textheight}{7.8in}
\setlength{\baselineskip}{13pt}
\begin{document}

 
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{defn}{Definition}[section]
\newtheorem{hyp}{Hypothesis}[section]
\newcommand{\proof}{\noindent{\bf Proof }}

 
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qed}{\hfill\hfill\vbox{\hrule\hbox{\vrule\squarebox
   {.667em}\vrule}\hrule}\smallskip}
 
 
\vspace{0.1in}

\begin{center} 
{\large \bf ON THE COMPLETE PIVOTING CONJECTURE \\
FOR A HADAMARD MATRIX OF ORDER 12 }
\\
\vspace{0.2in}
{\small ALAN EDELMAN}\footnote{
Supported by the Applied Mathematical Sciences subprogram of
the Office of Energy Research, U.S. Department of Energy under
Contract DE-AC03-76SF00098.
} \\
{\small \it Department of Mathematics \\
and Lawrence Berkeley Laboratory\\
University of California \\
Berkeley, California 94720 \\
\verb+edelman@math.berkeley.edu+\\}

\vspace{0.2in}
{\small WALTER MASCARENHAS\\
Dept. de Matematica \\
Universidade Estadual de Campinas \\
Caixa Postal 6065 \\
Barao Geraldo \\
Campinas SP 13081, Brazil} \\
{\verb+walterm@dcc.unicamp.br+}
\end{center}
\date{}


 

 
\begin{center}
ABSTRACT
\end{center}

\begin{quote}
{\small
This paper settles a conjecture by Day and Peterson that 
if Gaussian elimination with
complete pivoting is performed on a 12 by 12 Hadamard matrix,
then (1,2,2,4,3,10/3,18/5,4,3,6,6,12)  must be the (absolute) 
pivots.
In contrast, at least 30 patterns for the absolute values
of the pivots have been observed for 16 by 16 Hadamard matrices.
This problem is non-trivial because row and column
permutations do not preserve pivots.  A naive computer search
would require $(12!)^2$ trials.
}
\end{quote}

\section{Introduction}

Wilkinson and Cryer's conjecture \cite{Cr,W} stated 
that if $A$ is a real $n$ by $n$ matrix
such that $|a_{ij}|\le 1$, then the maximum pivot encountered
during the process of Gaussian elimination with complete pivoting,
the so called ``growth factor,''
would be bounded by $n$.
This conjecture is now known to be false, though the 
maximum pivot growth for $n$ by $n$ matrices  remains a mystery.


Given a choice of pivoting strategy, the growth factor of a matrix is
defined as
$$
g(A)= \frac{\max_{i,j,k} |A^{(k)}_{ij}|}
           {\max_{i,j} |A_{ij}|},
$$
where $A^{(k)}$ is the matrix obtained from $A$ after $k$ steps
of Gaussian elimination. 
In this paper, we consider mainly ``complete-pivoting,"
meaning that  at each step
the element of largest magnitude (the ``pivot") is moved 
by row and column exchanges to the upper left corner of the
current sublock.



Recently  Gould \cite{G,G1} has 
published or reported on matrices
that exhibited, in the presence of 
roundoff error,
growth larger than $n$:
\begin{center}
\begin{tabular}{|c|c|} \hline
$n$ & growth \\ \hline
13 & 13.02 \\
18 & 20.45 \\
20 & 24.25 \\
25 & 32.99 \\ \hline
\end{tabular}
\end{center}
These matrices were obtained computationally using sophisticated
numerical optimization techniques.
The first author \cite{Ed1,Ed2}  was only able
to reproduce 
Gould's large growth
in exact arithmetic
upon  
perturbing Gould's matrices in a non-trivial manner.  
This reminds us of the care needed when 
proving mathematical statements using rounded
arithmetic.



Trefethen and Schreiber \cite{TS} report on preliminary experiments
that suggest that if $A$ is a random
matrix with 
independent standard normal entries,  then the growth factor
for partial  pivoting seems to behave like $n^{2/3}$, though
they do not claim this behavior to be asymptotically valid.
The first author has performed more extensive experiments that
suggest that partial  pivoting grows more like $n^{1/2}$ 
than $n^{2/3}$.
Proving such a result to be true is probably very difficult.


We now know that the conjecture that
$g(A)\le n$ is false, but we believe a weaker
version of the conjecture  formulated by Cryer:  We believe
that $g(H)=n$ if $H$ is a {\bf Hadamard matrix}.
A Hadamard matrix $H$ has entries $\pm 1$ and $HH^T=nI$.
(Cryer's original formulation was that $g(A) \le n$ with equality
iff  $A$ is a Hadamard matrix.)
When performing Gaussian elimination with complete pivoting on a 
Hadamard matrix, the final pivot always has magnitude $n$
\cite[Theorem 2.4]{Cr}.



Here we take a small step towards proving 
the Hadamard portion of Cryer's conjecture
by settling a conjecture by Day and Peterson \cite{DP} that only one set of
pivot magnitudes is possible for a $12$ by $12$ Hadamard matrix.
Unfortunately many pivot patterns can be observed
by permuting the rows and columns of any 
16 by 16 Hadamard matrix, and it appears very difficult to 
proof that $g(H)=16$ when $H$ is a 16 by 16 Hadamard matrix.

Husain \cite{Hu} showed that there is only one Hadamard matrix
of order 12 up to Hadamard equivalence.  (Two matrices are
Hadamard equivalent if they can be obtained from each other
by row and column permutations and by row and column sign changes.)
However, the pivot  pattern is not  invariant under Hadamard 
equivalence. 



\section{Preliminary Notation and Lemmas}

Hadamard matrices are highly structured.  We collect here the important
properties that we will need for our proof. To begin, it is well
known that an Hadamard matrix of size $n=4t$ is equivalent to a
{\bf symmetric block design} with parameters $v=4t-1$, $k=2t-1$, and
$\lambda=t-1$ \cite{Hall}.  A symmetric block design 
with parameters $v,k$ and $\lambda$ is a collection of
$v$ objects and $v$ blocks such that
\begin{itemize}
\item every block contains $k$ objects,
\item every object is found in $k$ blocks,
\item every pair of blocks share $\lambda$ objects in common,
\item every pair of objects can be found in $\lambda$ blocks.
\end{itemize}
We can interpret an Hadamard matrix as a symmetric
block design by first negating rows and columns
of $H$ so that
its leading row
and column contains only  positive ones. 
We then have a design on the objects $1$ through $n-1$ by
saying  that $k$ is a member of                    
block $i$ iff $H_{i+1, k+1} = +1$.
When $n=12$, $t=3$, $v=11$, $k=5$, and $\lambda=2$.
Therefore  a 12 by 12 Hadamard matrix is equivalent to an
arrangement of 11 objects into 11 blocks containing 5 objects
such that each object appears in exactly 5 blocks, every
pair of distinct objects appears together exactly twice, and
every pair of distinct blocks has exactly 2 elements in common.


We say that a matrix $A$ is {\bf completely pivoted}, or CP, if
the rows and columns have been permuted so that Gaussian elimination
with no pivoting satisfies the requirements for complete pivoting. 
Following \cite{DP}, 
let $A(k)$ denote the 
absolute value of the determinant of 
the upper left $k$ by $k$ principal submatrix of $A$,
and
$A[k]$ denotes the absolute value of the determinant of the
lower right  $k$ by $k$ principal submatrix.
The determinant
of a $0$ by $0$ matrix is  $1$ by default.

Let
\begin{equation}
p_k \equiv A(k)/A(k-1).
\end{equation}
When $A$ is CP, $p_k$ 
is the magnitude  of
$A_{kk}$ after $k-1$ steps of Gaussian elimination, i.e.
the $k$th pivot.
For the remainder of this paper, we will simply use the
term ``pivot'' rathern than ``pivot magnitude.''


\begin{lemma}
\label{lemmaC}
If $H$ is an $n$ by $n$ Hadamard matrix, then
$$ n^{n/2} \,  H(k) =\, n^{k} \, H[n-k].$$
\end{lemma}

\proof  See \cite{DP}, Proposition 5.2.

\begin{cor}
\label{CorA}
If $H$ is an $n$ by $n$ Hadamard matrix,  then the
$k$th pivot from the end is 
\[p_{n+1-k}= \frac{ n H[k-1]}{H[k]}.\]
\end{cor}

\proof
This follows immediately from the lemma and the definition of $p_k$.

\begin{cor}
\label{corW}
If a Hadamard matrix $H$ is CP and $k<n$, then,
for all $(k-1) \times (k-1)$ minors $M_{k-1}$ of the $k \times k $
lower right submatrix of $H$, we have $H[k-1] \geq |\, \det(M_{k-1} ) \, |$.

\end{cor}

\proof
This follows from Corollary \ref{CorA} and the CP property of H,
for otherwise we could permute rows and columns of the lower right
$k \times k$ minor of $H$ to obtain a larger value for $p_{n+1-k}$.

\

This corollary is useful for telling us that 
$H[k-1]$ is  the magnitude of the largest $(k-1) \times (k-1)$
minor of the $k \times k $ lower right submatrix of $H$.
Thus $H[k-1]/H[k]$ is the largest 
magnitude of an element of the
inverse of the $k \times k $ lower right submatrix of $H$.


\begin{lemma}
\label{lemmaD}
Let $d_n$ denote the largest possible value of a determinant
of an $n$ by $n$ matrix consisting of entries $\pm 1$.
The first seven values of the sequence $(d_i)$ are
$1,2,4,16,48,160,576.$ For $n=2,\ldots,7$ if the determinant
of an $n$ by $n$ matrix of
$\pm1$'s is $d_n$, then the matrix must have an
$n-1$ by $n-1$ minor whose determinant's
magnitude  is $d_{n-1}$.
This can not happen  when $n=8$.
\end{lemma}



\proof  
The values of $d_1,\ldots,d_7$  were computed by
Williamson  \cite{Will}
who further showed that up to Hadamard equivalence there is only
one $n$ by $n$ matrix with determinant $d_n$ for $n=2,\ldots,7$.
It is easy to verify that
each of  these matrices has an $n-1$ by $n-1$
minor with absolute determinant $d_{n-1}$.
When $n=8$, $d_8= 4096$,
the matrix is Hadamard, so all 7 by 7 minors have determinant of
magnitude 512.

\begin{lemma}
\label{lemmaA}
If  $H$ is a CP Hadamard matrix,  then $H(4)=16$ so that
the $4 \times 4$ principal subminor of $H$ is an Hadamard matrix
of order $4$.
\end{lemma}

\proof See \cite{DP}, Proposition 5.8.
It follows that the first four pivots are 1,2,2,4 respectively.

\section{Pivot Sequence for $H_{12}$}

In this section we prove our main result: the 
pivots for a CP $12 \times 12$ Hadamard matrix are
(1,2,2,4,3,10/3,18/5,4,3,6,6,12).   The first four pivots
were determined by Day and Peterson  \cite{DP} as given in
 Lemma \ref{lemmaA}.  In  Lemma \ref{lemmaB} that
follows, we show that the fifth pivot must be $3$ from which 
the remaining pivots will be determined
to be unique  using Lemma \ref{lemmaD}.


\begin{lemma}
\label{lemmaB}
If $H$ is a $12 \times 12$ CP Hadamard matrix then 
$H(5)=48$. 
\end{lemma}

\proof 
The argument is simplified if we consider the design
interpretation of a Hadamard matrix so 
(without loss of generality) we assume that the first row and
column of $H$ are all $+1$, and also that the upper left $4 \times 4$
submatrix of $H$ is the $4 \times 4$ Hadamard matrix (Lemma 
\ref{lemmaA})
given by the block design with blocks
$B_1=\{1\}, \ B_2=\{2\}, \ B_3=\{3\}$.  

We  will  show that some $5 \times 5$ minor
of $H$ with determinant $48$ includes rows and columns 1 through 4.
Once we have done so, we can conclude that $H(5)=48$.
To see this, observe that
Lemma \ref{lemmaD} tells us that  $48$ is the maximum value of the 
determinant of a $5 \times 5$ matrix of $\pm 1$'s. If there 
is a minor $M_{5}$ with determinant
of magnitude  48 then, because of complete pivoting,
we must have $48 = |\det( M_{5} )| \leq H(5) \leq 48$, implying 
$H(5) = 48$.

When we interpret $H$ as a block design,
each block has
five objects,  each pair of blocks has two objects in common, 
and the  upper left $4 \times 4$ 
submatrix of $H$ is Hadamard.

There are a number of arbitrary choices that lead to no loss of 
generality.  We already mentioned a fixed choice for 
the objects $1,2,$ and $3$ as they appear in blocks $B_1,
B_2$ and $B_3$.
Further, there is no loss 
in generality by  letting
$$B_1=\{1\ 4\ 5\ 6\ 7\}, \ {\rm and } \
B_2=\{2\ 4\ 5\ 8\ 9\}.$$
This chooses $4$ and $5$ as the pair that appears in $B_1$ and
$B_2$ and lets $6,7,8,$ and $9$ fill in the remaining spots.


Either  $B_1 \cap B_2 \cap B_3$
is  empty or consists of one object which we can call
$5$ without loss of generality. (There could not be three blocks containing
the same pair.)
This leads to only two distinct possibilities for 
$B_1,$ $B_2$ and $B_3$. If
$ B_1 \cap B_2 \cap B_3$ is ${5},$ then
$$B_1=\{1\ 4\ 5\ 6\ 7\}, \ \ 
B_2=\{2\ 4\ 5\ 8\ 9\}, \ \ 
B_3=\{ 3\ 5\ 6\ 8\ 10\}.$$
We needed  $6$ and $8$ so that $B_1 \cap B_3$
and $B_2 \cap B_3$ contained two elements; the choice of 10 rather
than 11 was arbitrary.

If $ B_1 \cap B_2 \cap B_3=\emptyset$, then
$$B_1=\{1\ 4\ 5\ 6\ 7\}, \ \
B_2= \{2\ 4\ 5\ 8\ 9\}, \ \ B_3=\{ 3\ 6\ 7\ 8\ 9\}.$$
We needed to include $6,7,8$ and $9$ so that
the intersections of $B_1$ or $B_2$ with $B_3$ contained
two elements.

Let $B_4$ be a block that contains $1$ and $2$ but not $3$.
(There are two blocks that contain any pair such as $1$ and $2$,
and they both could not contain $3$ for otherwise there would
be too many elements in common.) 
The reader may  verify that $B_4$ can not contain a $4$ for if it did,
it would not be possible to choose the last two elements to be 
consistent with the either of the possibilities above.
Thus $B_4$ contains $1$ and $2$ but not $3$ and $4$.

The information from $B_1$ through $B_4$ about the objects $1$ through
$4$ tells us that we have a five by
five minor that includes rows and columns 1 through 4 with entries
$$
\left(
\begin{array}{rrrrr}
 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 has determinant 48
and thus $H(5)=48$.
\qed




\begin{cor}
If $H$ is a $12 \times 12$ CP Hadamard matrix then 
\[
p_{5}=H(5)/H(4)=3.
\]
\end{cor}

\begin{theorem}
No matter how the rows and columns of a CP 12 by 12 Hadamard matrix $H$
are ordered, the  pivots must be 
1, 2, 2, 4, 3, 10/3, 18/5, 4, 3, 6, 6, 12.
\end{theorem}

\proof
From Lemmas \ref{lemmaB} and \ref{lemmaC}, it follows that
$H[7]=576$.  Observe that, from Lemma \ref{lemmaD}, this
is the maximum value attained by the absolute value of the
determinant of a $7 \times 7$ matrix with entries $\pm 1$.
Lemma \ref{lemmaD} also tell us that the $7 \times 7$ lower right
corner has a $6 \times 6$ minor with maximal determinant $160$.
As a consequence of
Corollary \ref{corW}, 
$H[6]=160$.
Similarly, we conclude
$H[5]=48$,
$H[4]=16$,
$H[3]=4$,
$H[2]=2$,
and
$H[1]=1$.
The last seven pivots now follow from Corollary \ref{CorA}.

\section{Hadamard matrices of order 16 and open problems}


It is known \cite{Wa} that there are five equivalence
classes of Hadamard matrices of order 16.
Unfortunately, the pivot pattern is not an invariant of
the equivalence class, and thus the number of equivalence
classes may offer little useful information.
Extensive experiments revealed over
30 possible pivot patterns for Hadamard matrices
of order 16, though not all patterns appeared for each equivalence
class.  However, we found the number of possible values for
$H(k)$ to be quite small.  For example the only values
that appeared for $H(8)$ in our experiments  were
1024,  1536, 2048, 2304,  2560,  3072, and  4096. 
For $H(7)$ the values that appeared were
256,  384,   512, and  576.
We suspect that the paucity of different values for the determinants
might provide cludes to prove that  the growth factor for a 16 by 16
Hadamard matrix is 16.


An interesting conjecture by
Day and Peterson \cite{DP} that the fourth from last
pivot must be  $n/4$ remains unsolved.  
We  performed extensive experiments beyond those reported in \cite{DP}
for a large
variety of Hadamard matrices including some 
that were  discovered as recently as the  last seven years.
We too  believe their conjecture, though we have not
attempted to prove it yet.
Hadamard matrix problems sound tantalizingly easy, yet 
the existence of relatively small Hadamard matrices ($n=428$)
is still not known.

 
\newpage

\noindent

\vspace{0.1in}


\def\\{\medskip\noindent\hangindent .3in{}}
\setlength{\baselineskip 11pt}
\frenchspacing
\begin{thebibliography}{9}

\bibitem{Co}
A.M.Cohen,
A note on pivot size in Gaussian elimination,
{\sl Lin. Alg.  Appl. 8} (1974), 361--368.

\bibitem{Cr}
C.W.Cryer,
Pivot size in Gaussian elimination,
{\sl Num. Math. 12} (1968), 335--345.

\bibitem{DP}
J.Day and B.Peterson,
Growth in Gaussian elimination,
{\sl Amer. Math. Monthly} (June 1988),  489--513.

\bibitem{Ed1}
A.Edelman,
Note to the editor,
{\sl SIAM J. Matrix Anal. Appl., 12} (1991).

\bibitem{Ed2}
A.Edelman,
The complete pivoting conjecture for Gaussian elimination
is false.
{\sl The Mathematica Journal 2} (1992), 58--61.


\bibitem{GS}
A.Y.Geramita and J.Seberry,
{\sl Orthogonal Designs},
Marcel Dekker, Inc., New York, 1979.

\bibitem{G}
N.Gould,
On growth in Gaussian elimination with pivoting,
{\sl SIAM J. Matrix Anal. Appl., 12} (1991), 354--361.

\bibitem{G1}
N.Gould,
private communication.

\bibitem{Hall}
M.Hall,
{\sl Combinatorial Theory, 2nd ed.},
John Wiley, New York, 1986.

\bibitem{HH}
N.J.Higham and D.J.Higham,
Large growth factors in Gaussian elimination with pivoting,
{\sl SIAM J. Matrix Anal. Appl., 10} (1989), 155--164.

\bibitem{NN}
N.Higham and N.Trefethen,
Complete pivoting conjecture is disproved,
{\sl SIAM News 24} (January 1991), 9.


\bibitem{Hu}
Q.M.Husain,
On the totality of the solutions for the symmetrical incomplete block
designs: $\lambda=2,k=5$ or $6$,
{\sl Sankhya 7} (1945), 204--208.

\bibitem{T}
L.Tornheim,
Pivot size in Gauss reduction,
Tech Report, Chevron Research Co., Richmond CA., 1964.

\bibitem{T2}
L.Tornheim,
Maximum pivot size in Gaussian elimination with complete pivoting,
Tech Report, Chevron Research Co., Richmond CA., 1970.

\bibitem{TS}
L.N.Trefethen and R.S.Schreiber,
Average-case stability of Gaussian elimination,
{\sl SIAM J. Matrix Anal. Appl., 11} (1990), 335--360.

\bibitem{Wa} 
W.D.Wallis, A.P.Street, and J.S.Wallis,
{\sl Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices}
Lecture Notes in Math. 292, Springer Verlag, 1970.

\bibitem{W1}
J.H.Wilkinson,
Error analysis of direct methods of matrix inversion,
{\sl J. Assoc. Comp. Machinery 8} (1961), 281--330. 

\bibitem{W}
J.H.Wilkinson,
{\sl The Algebraic Eigenvalue Problem},
Oxford Univ. Press, London, 1965.

\bibitem{Will}
J.Williamson,
Determinants whose elements are 0 and 1,
{\sl American Math Monthly 53} (1946), 427--434.


\end{thebibliography} 

\end{document}







