CRETAN MATRICES Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin and Jennifer Seberry, 1.05.2014

Definition 1. A real square matrix X=(xij) of order n is called quasi-orthogonal if it satisfies

XTX = XXT = c In,

where In is the n×n identity matrix, c is constant real number. In this and future work we will only use quasi-orthogonal to refer to matrices with real elements. At least one entry in each row and column must be 1. Hadamard matrices are the best known of these matrices with entries from the unit disk .

Definition 2. An Hadamard matrix of order n is an n×n matrix with elements 1, –1 such, that

HTH = HHT = n In,

where In is the identity matrix and “T” stands for transposition.

The Hadamard inequality  says, that Hadamard matrices have maximum of determinant for the class of matrices with entries from the unit disk (the moduli of the elements are | xij |≤1 by default). Hadamard matrices can only exist for orders 1, 2 and n=4t, t an integer (the so called Hadamard conjecture).

The class of quasi-orthogonal matrices with maximal determinant and entries from the unit disk may have a very large set of solutions. Different solutions may give the same maximal determinant. Symmetric conference matrices, a particularly important class of 0, ±1 matrices, are the most well known .

Definition 3. A symmetric conference matrix, C, is an n×n matrix with elements 0, 1 or –1, satisfying

CTC = CCT = (n–1) In.

Conference matrices can only exist if the number n–1 is the sum of two squares. Similar to symmetric conference matrices are quasi-orthogonal matrices W = W(2t,2tm) of order n = 2t, with elements 0, +1 or –1, satisfying WTW = WWT = (2t,2tm) In. These are called weighing matrices. It has been conjectured  that for n = 4t, there exists a W = W(4t,4tm) for all integers 0≤m≤4t.

Definition 4. The values of the entries of the quasi-orthogonal matrix, X, are called levels, so Hadamard matrices are two-level matrices and symmetric conference matrices and weighing matrices are three-level matrices. Quasi-orthogonal matrices with maximal determinant of odd orders have been discovered to have a larger number of levels .

Definition 5. A Balonin-Mironovski  matrix, An, of order n, is quasi-orthogonal matrix of maximal determinant. In this remark they are called BM matrices. They are: Balonin-Mironovski – Cretan(3;2;2.25) circ(–b,a,a); Balonin-Mironovski – Cretan(5;3;30,5,5;3.3611) circ(–a,a,b,a,c);Balonin-Mironovski – Cretan(7;5;30,6,3,4,6;5.0777) first row and column d,b,b,b,a,a,a; core [[backcirc(–a,e,–c), circ(–a,a,a)],[circ(–a,a,a), backcirc(e,–a,–d)]];Balonin-Mironovski – Cretan(9;4;40,16,24,1;6.4308) first row and column –d,b,b,b,b,b,b,b,b; core circ(a,–a,c,c,a,c,–a,–a);Balonin-Mironovski – Cretan(11;6;121,11,11,11,11,11;8.5022) circ (c,a,e,a,a,–a,–a,d,–f,b,–a)

Conjecture (Balonin, [6, 7]): there are only 5 Balonin-Mironovski matrices A3, A5, A7, A9, A11 with (n+1)/2±m, m≤1, levels.

The 2006 paper  gave 5 examples of BM matrices. Order 13 was unresolved. During 2006-2011 Balonin and Sergeev carried out many computer experiments to find the absolute maximum of the determinant of A13.

It was speculated  that 13 is a critical order for matrices of odd orders with maximal determinant. Starting from this odd order, the number of levels k>>(n+1)/2.

An example of a 6-level (by moduli) matrix of even order was found and called Yura's matrix Y22 , see Fig. 1a. A student Yura found this rare solution using DOS–MatLab [8, 9]. The matrix levels are captured by the colour of the squares.  a)                                                       b)

Fig. 1. a) Yura's matrix Y22 and b) a weighing matrix W(22,20)

 Yura-Cretan(22;6; 17×22,22,22,22,22,22; 19.4311) it does describe the construction via two circulantscirc(–f,b,a,–a,a,a,a,a,–a,a,–a) and circ(a,a,–a,–c,–a,a,d,a,e,a,–a)

Order n = 22 is special, n–1 is not sum of two squares, and a symmetric conference matrix does not exist. The two circulant matrix Y22 based on the sequences {–f b aa a a a aa aa}, {a aaca a d a e aa} has elements with moduli a=1, b=0.9802, c=0.7845, d=0.6924, e=0.5299, f=0.3076. It appears similar to a conference matrix of order 22 because of the small value for f. A non optimal determinant version was also found with f=0.0055.

It was then discovered that there is a 22×22 matrix W(22,20) constructed using Golay sequences which gave det(W(22,20)) > det(Y22), see Fig 1b.

Conjecture I. (Balonin-Seberry, 2014): Suppose a W(2n,2n–1) does not exist. Suppose a W(2n,2n–2) exists. Then the quasi-orthogonal matrix with maximal determinant is constructed using the W(2n,2n–2).

Conjecture II. (Balonin-Seberry, 2014): Suppose a W(2n,2n–1) does not exist. Suppose that W(2n,k) is the weighing matrix with largest k that exists, then W(2n,k) will give a quasi-orthogonal matrix with near maximal determinant.

For order 58 Balonin found  a two-circulant matrix Y58: Cretan(58;16;54.2444) with only a few levels and determinant 2•1050, the weighing matrices W(58,k), k = 54, 55, 56, 57, do not exist. The weighing matrix W(58,53) has determinant 1050, so conjecture I only applies for W(2n,2n–2) matrices, see Fig. 2.  a)                                                       b)

Fig. 2. a) A low number of levels matrix of order 58 and b) a weighing matrix W(58,53)

The absence of a solution with a low number of levels for n≥13, led Balonin and Sergeev to search for and classify quasi-orthogonal matrices with other properties [5, 6, 11–13].

Definition 6. A quasi-orthogonal matrix with extremal or fixed properties: global or local extremum of the determinant, saddle points, the minimum number of levels, or matrices with fixed numbers of levels is called a Balonin-Sergeev matrix. They are called here BSM-matrices.

A Balonin-Mironovski matrix is a Balonin-Sergeev matrix with the absolute maximum determinant. Balonin-Sergeev matrices with fixed numbers of levels were first mentioned during a conference in Crete, so we will call them Cretan matrices (CM-matrix). Definition 7. A Cretan matrix, X, of order n, which has indeterminate entries, x1, x2, x3, x4, … , xk is said to have k levels.

It satisfies XTX = XXT = ω(n)In, In the identity matrix, ω(n) the weight, that give a number of equations, called the CM-equations, which make X quasi-orthogonal when the variables (indeterminates) are replaced by real elements with moduli | xij |≤1.

The XTX = XXT have diagonal entries the weight ω(n) and off diagonal entries 0. CM-matrices can be defined by a function ω(n) or functions x1(n), x2(n), x3(n), x4(n), … , xk(n).

We write CM(n;k;ω(n);determinant) as shorthand.

Notation: When the variable (indeterminate) entries, x1, x2, x3, x4, … , xk occur s1, s2, s3, s4, … , sk times in each row and column, we write CM(n; k; s1, s2, s3, s4, … , sk; ω(n);determinant) as shorthand.

A review and questions of existence are discussed in [7, 13, 14].

Balonin and Sergeev concluded [7, 13] that the resolution of the question of the existence of quasi-orthogonal matrices and their generalizations discussed here depends on the order :

• for n = 4t, t an integer, at least 2 levels, a, –b, | a |= | b |, are needed;
• for n = 4t–1, at least 2 levels, a=1, –b, b < a, are needed;
• for n = 4t–2, at least 2 levels, a=1, –b, b < a, are needed for a two block circulant construction;
• for n = 4t–3, at least 3 levels, a=1, –b, c, b < a, c < a, are needed.

Definitions and examples of different types of Cretan matrices will be discussed in future papers and this catalogue.

Acknowledgements

The authors wish to sincerely thank Tamara Balonina for converting this note into printing and Internet format. Cretan Level

BM-MATRICES CATALOGUE  BM-matrices A3 and A5  BM-matrices A7 and A9  BM-matrices A11 and A13

HISTOGRAMS OF MODULI Of ELEMETS  BM-matrix A3  BM-matrix A5  BM-matrix A7  BM-matrix A9  BM-matrix A11  BM-matrix A13 !

CRETAN MATRICES  Balonin N.A., Seberry, Jennifer. "Remarks on Extremal and Maximum Determinant Matrices with Moduli of Real Entries ≤ 1", Informatsionno-upravliaiushchie sistemy, 2014, № 5.

References

1. Seberry, Jennifer, Yamada, Mieko. Hadamard matrices, sequences, and block designs, Contemporary Design Theory: A Collection of Surveys, J. H. Dinitz and D. R. Stinson, eds., John Wiley and Sons, Inc., 1992. pp. 431–560.
2. Hadamard J. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques. 1893. Vol. 17. pp. 240–246.
3. Balonin N. A., Seberry, Jennifer. A review and new symmetric conference matrices. Informatsionno-upravliaiushchie sistemy, 2014. № 4 (71), pp. 2–7.
4. Wallis (Seberry), Jennifer. Orthogonal (0,1,–1) matrices, Proceedings of First Australian Conference on Combinatorial Mathematics, TUNRA, Newcastle, 1972. pp. 61–84.
5. Balonin N. A., Mironovski L.A. Hadamard matrices of odd order, Informatsionno-upravliaiushchie sistemy, 2006. № 3, pp. 46–50 (In Russian).
6. Balonin N. A., Sergeev M. B. M-matrices. Informatsionno-upravliaiushchie sistemy, 2011, № 1, pp. 14-21 (In Russian)
7. Balonin N. A., Sergeev M. B. Local Maximum Determinant Matrices. Informatsionno-upravliaiushchie sistemy, 2014. № 1 (68), pp. 2–15 (In Russian).
8. Balonin Yu. N., Sergeev M. B. M-matrix of 22nd order. Informatsionno-upravliaiushchie sistemy, 2011. № 5 (54), pp. 87–90 (In Russian).
9. Balonin Yu. N., Sergeev M. B. The algorithm and program for searching and studying of M-matrices. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2013. № 3, pp.82 – 86 (In Russian).
10. Balonin N. A. Quasi-orthogonal matrix with maximal determinant, order 58, http://mathscinet.ru/catalogue/artifact58
11. Balonin N. A. Existence of Mersenne Matrices of 11th and 19th Orders. Informatsionno-upravliaiushchie sistemy, 2013. № 2, pp. 89 – 90 (In Russian).
12. Balonin N. A., Sergeev M. В. Two Ways to Construct Hadamard-Euler Matrices. Informatsionno-upravliaiushchie sistemy, 2013. № 1(62), pp. 7–10 (In Russian).
13. Sergeev A.M. Generalized Mersenne Matrices and Balonin’s Conjecture. Automatic Control and Computer Sciences, 2014. Vol. 48, № 4. pp. 214–220.
14. Balonin N. A., Sergeev M. B. On the Issue of Existence of Hadamard and Mersenne Matrices. Informatsionno-upravliaiushchie sistemy, 2013. № 5 (66), pp. 2–8 (In Russian).
15. Balonin N. A., Djokovic D. Z., Mironovski L.A., Seberry Jennifer, Sergeev M. B. Hadamard type Matrices Catalogue, http://mathscinet.ru/catalogue

 .. 