ON THE COMPLETE PIVOTING CONJECTURE FOR A HADAMARD MATRIX OF ORDER 12

ALAN EDELMAN^{1} Department of Mathematics and Lawrence Berkeley Laboratory University of California Berkeley, California 94720

                          edelman@math.berkeley.edu

WALTER MASCARENHAS Dept. de Matematica Universidade Estadual de Campinas Caixa Postal 6065 Barao Geraldo Campinas SP 13081, Brazil

                       walterm@dcc.unicamp.br

ABSTRACT

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.

1 Introduction

Wilkinson and Cryer’s conjecture [2, 18] stated that if A is a real n by n matrix such that |a_{ij}| ≤ 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_{ij}^{(k)}|}{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 [7, 8] has published or reported on matrices that exhibited, in the presence of roundoff error, growth larger than n:

1Supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under Contract DE-AC03-76SF00098.

\begin{matrix}n & growth \\ 13 & 13.02 \\ 18 & 20.45 \\ 20 & 24.25 \\ 25 & 32.99 \end{matrix}

These matrices were obtained computationally using sophisticated numerical optimization techniques. The first author [4, 5] 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 [15] 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) ≤ 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 Hadamard matrix. A Hadamard matrix H has entries ±1 and HH^{T} = nI. (Cryer’s original formulation was that g(A) ≤ 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 [2, Theorem 2.4].

Here we take a small step towards proving the Hadamard portion of Cryer’s conjecture by settling a conjecture by Day and Peterson [3] 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 [12] 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.

2 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 symmetric block design with parameters v = 4t − 1, k = 2t − 1, and λ = t − 1 [9]. A symmetric block design with parameters v, k and λ is a collection of v objects and v blocks such that

• every block contains k objects,

• every object is found in k blocks,

• every pair of blocks share λ objects in common,

• every pair of objects can be found in λ blocks.

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 λ = 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 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 [3], 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

p_{k} ≡ A(k)/A(k − 1).  (1)

When A is CP, p_{k} is the magnitude of A_{kk} after k −1 steps of Gaussian elimination, i.e. the kth pivot. For the remainder of this paper, we will simply use the term “pivot” rathern than “pivot magnitude.”

Lemma 2.1 If H is an n by n Hadamard matrix, then

n^{n/2} H(k) = n^{k} H[n − k].

Proof See [3], Proposition 5.2.

Corollary 2.1 If H is an n by n Hadamard matrix, then the kth pivot from the end is

p_{n+1−k} = \frac{nH[k − 1]}{H[k]}.

Proof This follows immediately from the lemma and the definition of p_{k}.

Corollary 2.2 If a Hadamard matrix H is CP and k < n, then, for all (k − 1) × (k − 1) minors M_{k−1} of the k × k lower right submatrix of H, we have H[k − 1] ≥ | det(M_{k−1}) |.

Proof This follows from Corollary 2.1 and the CP property of H, for otherwise we could permute rows and columns of the lower right k × 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)×(k−1) minor of the k×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×k lower right submatrix of H.

Lemma 2.2 Let d_{n} denote the largest possible value of a determinant of an n by n matrix consisting of entries ±1. The first seven values of the sequence (d_{i}) are 1, 2, 4, 16, 48, 160, 576. For n = 2, …, 7 if the determinant of an n by n matrix of ±1’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.

Proof The values of d_{1}, …, d_{7} were computed by Williamson [19] who further showed that up to Hadamard equivalence there is only one n by n matrix with determinant d_{n} for n = 2, …, 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.

Lemma 2.3 If H is a CP Hadamard matrix, then H(4) = 16 so that the 4 × 4 principal subminor of H is an Hadamard matrix of order 4.

Proof See [3], Proposition 5.8. It follows that the first four pivots are 1,2,2,4 respectively.

3 Pivot Sequence for H_{12}

In this section we prove our main result: the pivots for a CP 12 × 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 [3] as given in Lemma 2.3. In Lemma 3.1 that follows, we show that the fifth pivot must be 3 from which the remaining pivots will be determined to be unique using Lemma 2.2.

Lemma 3.1 If H is a 12 × 12 CP Hadamard matrix then H(5) = 48.

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 × 4 submatrix of H is the 4 × 4 Hadamard matrix (Lemma 2.3) given by the block design with blocks B_{1} = {1}, B_{2} = {2}, B_{3} = {3}.

We will show that some 5 × 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 2.2 tells us that 48 is the maximum value of the determinant of a 5 × 5 matrix of ±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})| ≤ H(5) ≤ 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 × 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}, 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}∩B_{2}∩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} ∩ B_{2} ∩ 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} ∩ B_{3} and B_{2} ∩ B_{3} contained two elements; the choice of 10 rather than 11 was arbitrary.

If B_{1} ∩ B_{2} ∩ B_{3} = ∅, 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

( \begin{matrix}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{matrix} ) .

This matrix has determinant 48 and thus H(5) = 48.

Corollary 3.1 If H is a 12 × 12 CP Hadamard matrix then

p_{5} = H(5)/H(4) = 3.

Theorem 3.1 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.

Proof From Lemmas 3.1 and 2.1, it follows that H[7] = 576. Observe that, from Lemma 2.2, this is the maximum value attained by the absolute value of the determinant of a 7×7 matrix with entries ±1. Lemma 2.2 also tell us that the 7×7 lower right corner has a 6 × 6 minor with maximal determinant 160. As a consequence of Corollary 2.2, 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 2.1.

4 Hadamard matrices of order 16 and open problems

It is known [16] 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 [3] that the fourth from last pivot must be n/4 remains unsolved. We performed extensive experiments beyond those reported in [3] 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.

References

[1] A.M.Cohen, A note on pivot size in Gaussian elimination, Lin. Alg. Appl. 8 (1974), 361–368.

[2] C.W.Cryer, Pivot size in Gaussian elimination, Num. Math. 12 (1968), 335–345.

[3] J.Day and B.Peterson, Growth in Gaussian elimination, Amer. Math. Monthly (June 1988), 489–513.

[4] A.Edelman, Note to the editor, SIAM J. Matrix Anal. Appl., 12 (1991).

[5] A.Edelman, The complete pivoting conjecture for Gaussian elimination is false. The Mathematica Journal 2 (1992), 58–61.

[6] A.Y.Geramita and J.Seberry, Orthogonal Designs, Marcel Dekker, Inc., New York, 1979.

[7] N.Gould, On growth in Gaussian elimination with pivoting, SIAM J. Matrix Anal. Appl., 12 (1991), 354–361.

[8] N.Gould, private communication.

[9] M.Hall, Combinatorial Theory, 2nd ed., John Wiley, New York, 1986.

[10] N.J.Higham and D.J.Higham, Large growth factors in Gaussian elimination with pivoting, SIAM J. Matrix Anal. Appl., 10 (1989), 155–164.

[11] N.Higham and N.Trefethen, Complete pivoting conjecture is disproved, SIAM News 24 (January 1991), 9.

[12] Q.M.Husain, On the totality of the solutions for the symmetrical incomplete block designs: λ = 2, k = 5 or 6, Sankhya 7 (1945), 204–208.

[13] L.Tornheim, Pivot size in Gauss reduction, Tech Report, Chevron Research Co., Richmond CA., 1964.

[14] L.Tornheim, Maximum pivot size in Gaussian elimination with complete pivoting, Tech Report, Chevron Research Co., Richmond CA., 1970.

[15] L.N.Trefethen and R.S.Schreiber, Average-case stability of Gaussian elimination, SIAM J. Matrix Anal. Appl., 11 (1990), 335–360.

[16] W.D.Wallis, A.P.Street, and J.S.Wallis, Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices Lecture Notes in Math. 292, Springer Verlag, 1970.

[17] J.H.Wilkinson, Error analysis of direct methods of matrix inversion, J. Assoc. Comp. Machinery 8 (1961), 281–330.

[18] J.H.Wilkinson, The Algebraic Eigenvalue Problem, Oxford Univ. Press, London, 1965.

[19] J.Williamson, Determinants whose elements are 0 and 1, American Math Monthly 53 (1946), 427–434.