CRETAN MATRICES
Hadamard matrix family catalogue and online algorithms © Nickolay A. Balonin and Jennifer Seberry, 1.05.2014 Definition 1. A real square matrix X=(x_{ij}) of order n is called quasiorthogonal if it satisfies
X^{T}X = XX^{T} = c I_{n}, where I_{n} is the n×n identity matrix, c is constant real number. In this and future work we will only use quasiorthogonal 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 [1]. Definition 2. An Hadamard matrix of order n is an n×n matrix with elements 1, –1 such, that
H^{T}H = HH^{T} = n I_{n}, where I_{n} is the identity matrix and “T” stands for transposition. The Hadamard inequality [2] 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  x_{ij} ≤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 quasiorthogonal 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 [3]. Definition 3. A symmetric conference matrix, C, is an n×n matrix with elements 0, 1 or –1, satisfying
C^{T}C = CC^{T} = (n–1) I_{n}.Conference matrices can only exist if the number n–1 is the sum of two squares. Similar to symmetric conference matrices are quasiorthogonal matrices W = W(2t,2t–m) of order n = 2t, with elements 0, +1 or –1, satisfying W^{T}W = WW^{T} = (2t,2t–m) I_{n}. These are called weighing matrices. It has been conjectured [4] that for n = 4t, there exists a W = W(4t,4t–m) for all integers 0≤m≤4t. Definition 4. The values of the entries of the quasiorthogonal matrix, X, are called levels, so Hadamard matrices are twolevel matrices and symmetric conference matrices and weighing matrices are threelevel matrices. Quasiorthogonal matrices with maximal determinant of odd orders have been discovered to have a larger number of levels [5]. Definition 5. A BaloninMironovski [5] matrix, A_{n}, of order n, is quasiorthogonal matrix of maximal determinant. In this remark they are called BM matrices.
They are: BaloninMironovski – Cretan(3;2;2.25) circ(–b,a,a); BaloninMironovski – Cretan(5;3;30,5,5;3.3611) circ(–a,a,b,a,c); BaloninMironovski – 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)]]; BaloninMironovski – 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); BaloninMironovski – 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 BaloninMironovski matrices A_{3}, A_{5}, A_{7}, A_{9}, A_{11} with (n+1)/2±m, m≤1, levels. The 2006 paper [5] gave 5 examples of BM matrices. Order 13 was unresolved. During 20062011 Balonin and Sergeev carried out many computer experiments to find the absolute maximum of the determinant of A_{13}. It was speculated [6] 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 6level (by moduli) matrix of even order was found and called Yura's matrix Y_{22} [8], 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 Y_{22} and b) a weighing matrix W(22,20)YuraCretan(22;6; 17×22,22,22,22,22,22; 19.4311) it does describe the construction via two circulants circ(–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 Y_{22} based on the sequences {–f b a –a a a a a –a a –a}, {a a –a –c –a a d a e a –a} 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(Y_{22}), see Fig 1b. Conjecture I. (BaloninSeberry, 2014): Suppose a W(2n,2n–1) does not exist. Suppose a W(2n,2n–2) exists. Then the quasiorthogonal matrix with maximal determinant is constructed using the W(2n,2n–2). Conjecture II. (BaloninSeberry, 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 quasiorthogonal matrix with near maximal determinant. For order 58 Balonin found [10] a twocirculant matrix Y_{58}: Cretan(58;16;54.2444) with only a few levels and determinant 2•10^{50}, the weighing matrices W(58,k), k = 54, 55, 56, 57, do not exist. The weighing matrix W(58,53) has determinant 10^{50}, 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 quasiorthogonal matrices with other properties [5, 6, 11–13]. Definition 6. A quasiorthogonal 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 BaloninSergeev matrix. They are called here BSMmatrices. A BaloninMironovski matrix is a BaloninSergeev matrix with the absolute maximum determinant. BaloninSergeev matrices with fixed numbers of levels were first mentioned during a conference in Crete, so we will call them Cretan matrices (CMmatrix).
Definition 7. A Cretan matrix, X, of order n, which has indeterminate entries, x_{1}, x_{2}, x_{3}, x_{4}, … , x_{k} is said to have k levels. It satisfies X^{T}X = XX^{T} = ω(n)I_{n}, I_{n} the identity matrix, ω(n) the weight, that give a number of equations, called the CMequations, which make X quasiorthogonal when the variables (indeterminates) are replaced by real elements with moduli  x_{ij} ≤1. The X^{T}X = XX^{T} have diagonal entries the weight ω(n) and off diagonal entries 0. CMmatrices can be defined by a function ω(n) or functions x_{1}(n), x_{2}(n), x_{3}(n), x_{4}(n), … , x_{k}(n). We write CM(n;k;ω(n);determinant) as shorthand. Notation: When the variable (indeterminate) entries, x_{1}, x_{2}, x_{3}, x_{4}, … , x_{k} occur s_{1}, s_{2}, s_{3}, s_{4}, … , s_{k} times in each row and column, we write CM(n; k; s_{1}, s_{2}, s_{3}, s_{4}, … , s_{k}; ω(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 quasiorthogonal matrices and their generalizations discussed here depends on the order [15]: • 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
BMMATRICES CATALOGUE BMmatrices A_{3} and A_{5} BMmatrices A_{7} and A_{9} BMmatrices A_{11} and A_{13} HISTOGRAMS OF MODULI Of ELEMETS BMmatrix A_{3} BMmatrix A_{5} BMmatrix A_{7} BMmatrix A_{9} BMmatrix A_{11} BMmatrix A_{13} !
CRETAN MATRICES
Balonin N.A., Seberry, Jennifer. "Remarks on Extremal and Maximum Determinant Matrices with Moduli of Real Entries ≤ 1", Informatsionnoupravliaiushchie 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. Informatsionnoupravliaiushchie 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, Informatsionnoupravliaiushchie sistemy, 2006. ¹ 3, pp. 46–50 (In Russian). 6. Balonin N. A., Sergeev M. B. Mmatrices. Informatsionnoupravliaiushchie sistemy, 2011, ¹ 1, pp. 1421 (In Russian) 7. Balonin N. A., Sergeev M. B. Local Maximum Determinant Matrices. Informatsionnoupravliaiushchie sistemy, 2014. ¹ 1 (68), pp. 2–15 (In Russian). 8. Balonin Yu. N., Sergeev M. B. Mmatrix of 22nd order. Informatsionnoupravliaiushchie 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 Mmatrices. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2013. ¹ 3, pp.82 – 86 (In Russian). 10. Balonin N. A. Quasiorthogonal matrix with maximal determinant, order 58, http://mathscinet.ru/catalogue/artifact58 11. Balonin N. A. Existence of Mersenne Matrices of 11th and 19th Orders. Informatsionnoupravliaiushchie sistemy, 2013. ¹ 2, pp. 89 – 90 (In Russian). 12. Balonin N. A., Sergeev M. Â. Two Ways to Construct HadamardEuler Matrices. Informatsionnoupravliaiushchie 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. Informatsionnoupravliaiushchie 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

