MERSENNE, EULER, SEIDEL, FERMAT LEVELS



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin, 1.05.2014


TABLE OF LEVEL FUNCTIONS


There are 5 main families (Mersenne, Euler, Hadamard, Fermat, Seidel) of absolute and local maximum determinat matrices: |det(X)|→max; |xij|≤1; X'X=ω(n)I.

Local maximum determinant matrices [8], [15] can be described by functions of their levels. Varying levels a=1, Цb; 0≤b≤1 (can be irrational) allow to construct such simple structures (imposible with integer levels for some orders) as circulant and two-circulant matrices.

Definition 1. The values of the entries of a matrix are called levels [1].

Hadamard matrices are optimal two-level matrices [2, 3], symmetric conference matrices [4] and weighing matrices are three-level matrices [5]. Quasi-orthogonal matrices with maximal determinant of odd orders have been discovered with a larger number of levels [6].

Definition 2. Quasi-orthogonal matrix, X, of order n, satisfies XTX = ω(n)I, where ω(n)≤n is the weight, and defined by a function ω(n) or functions a(n)=1, b(n), .. of its levels.

We will denote the levels of two-level matrices as a, Цb; for positive 0 ≤ ba, a = 1.

Determinant |det(X)|=ω(n)n/2, ω(n)=nψ(n)2, where ψ Ц a normalized determinant, ψ(n)=1 for Hadamard matrices.

ω(n)=nψ(n)2


Hadamard inequality |det(X)|≤nn/2 gives an estimation of determinant, while |det(X)|=nn/2×ψ(n)n gives a possible value.

MAIN MATRIX FAMILIES



Hadamard matrices H12 and H16


Hadamard matrix. A quasi-orthogonal matrix, named Hadamard matrix [1] H, is a two-level quasi-orthogonal matrix of order n with level functions a=1,Цb; b=1.

Hadamard conjecture [3]: Hadamard matrices exist for n=1,2 and 4t, t is integer.
Their orders cover n = 2k, k is integer, for so called elementary Hadamard matrices set.
Normalized determinant ψ = 1.






Mersenne matrices M11 and M15


Mersenne matrix. A quasi-orthogonal matrix, named Mersenne matrix M [8], is a two-level quasi-orthogonal matrix of order n with level functions a=1, Цb; where b=t/(t+sqrt(t)), t=(n+1)/4.

Conjecture [8,12,15]: Mersenne matrices exist for n=4tЦ1, t is integer.
Their orders cover Mersenne numbers n = 2kЦ1, k is integer, for so called elementary Mersenne matrices set (or pure Mersenne matrices).
Invariant of Mersenne matrices is difference 1 between numbers of positive and negative entries in every column (row), so weight ω = (n+1)/2+(nЦ1)b2/2=2t+(2tЦ1)b2.
Normalized determinant ψ = sqrt((2t+(2tЦ1)b2))/(4tЦ1).




Euler matrices E10 and E14


Euler matrix. A quasi-orthogonal matrix, named Euler matrix E [8], is a four-level quasi-orthogonal matrix of order n, it can be observed as two-circulant (or two blocks A, B) matrices with two level functions a=1, Цb; where b=t/(t+sqrt(2t)), t=(n+2)/4.

Conjecture [8,12,15]: Euler matrices exist for n=4tЦ2, t is integer.
Their orders cover singular orders for the symmetric conference matrices: the latests do not exist if nЦ1 is not sum of two squares.
Invariant of Euler matrices is difference 2 between numbers of ±1 and ±b entries in every column (row), so weight ω = (n+2)/2+(nЦ2)b2/2=2t+2tЦ1)b2.
Normalized determinant ψ = sqrt((2t+2(tЦ1)b2))/(4tЦ2).




Seidel matrices S9 and S13


Seidel matrix. A quasi-orthogonal matrix, named Seidel matrix S [8], is a quasi-orthogonal matrix of order n with level functions a=1, Цb, d; where b=1Ц2d, d=1/(1+sqrt(n)) belongs to diagonal entries, t=(n+3)/4.

Their orders cover singular points of symmetric conference matrices; Seidel matrices do not exist if n is not sum of two squares [8].
Invariant of Seidel matrices is difference 1 between numbers of positive and negative entries in every column (row), so weight ω = (nЦ1)(1+b2)/2+d2=2(tЦ1)(1+b2)+d2.
Normalized determinant ψ = sqrt((2(tЦ1)(1+b2)+d2)/(4tЦ3).




Hadamard H16 anf Fermat F17


Fermat matrix. A quasi-orthogonal matrix, named Fermat matrix F [8], is a quasi-orthogonal matrix of order n with level functions a=1, Цb, s; for n=3, 2a=b=s=1; for n>3, q=nЦ1=4u2, p=q+sqrt(q), we have bs<a; where b=(2nЦp)/p=(2u2Цu+1)/(2u2+u)=1Ц(2uЦ1)/u(2u+1),
s=sqrt(nqЦ2sqrt(q))/p=sqrt(nu2Цu)/(2u2+u) is border.

Their orders cover Fermat numbers n = 22t+1, t is integer, for so called elementary Fermat matrices set (or pure Fermat matrices).
Invariant of Fermat matrices: every non border column has k=(qЦsqrt(q))/2=2u2Цu of entries a=1, so weight ω(n)=k+(qЦk)b2+s2.
Normalized determinant ψ = sqrt(ω(n)/n).


MERSENNE MATRIX LEVEL b

b=(qЦ(4q)1/2)/(qЦ4), q=n+1, n=4kЦ1.


EULER MATRIX LEVEL b

b=(qЦ(8q)1/2)/(qЦ8), q=n+2, n=4kЦ2.


DETERMINANT GRAPH D=1/mn=nn/2/hn

Hadamard H, Belevitch C, Euler E, Mersenne M, Fermat F matrices, Cyan is Proclus.


References

1. Balonin N.A., Seberry, Jennifer. Remarks on Extremal and Maximum Determinant Matrices with Moduli of Real Entries ≤ 1, Informatsionno-upravliaiushchie sistemy, 2014, є 5, pp. 2Ц7.
2. 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.
3. Hadamard J. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques. 1893. Vol. 17. pp. 240Ц246.
4. Balonin N. A., Seberry, Jennifer. A review and new symmetric conference matrices. Informatsionno-upravliaiushchie sistemy, 2014. є 4 (71), pp. 2Ц7.
5. Wallis (Seberry), Jennifer. Orthogonal (0,1,Ц1) matrices, Proceedings of First Australian Conference on Combinatorial Mathematics, TUNRA, Newcastle, 1972. pp. 61Ц84.
6. Balonin N. A., Mironovski L.A. Hadamard matrices of odd order, Informatsionno-upravliaiushchie sistemy, 2006. є 3, pp. 46Ц50 (In Russian).
7. Balonin N. A., Sergeev M. B. M-matrices. Informatsionno-upravliaiushchie sistemy, 2011, є 1, pp. 14-21 (In Russian)
8. Balonin N. A., Sergeev M. B. Local Maximum Determinant Matrices. Informatsionno-upravliaiushchie sistemy, 2014. є 1 (68), pp. 2Ц15 (In Russian).
9. Balonin Yu. N., Sergeev M. B. M-matrix of 22nd order. Informatsionno-upravliaiushchie sistemy, 2011. є 5 (54), pp. 87Ц90 (In Russian).
10. 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).
11. Balonin N. A. Quasi-orthogonal matrix with maximal determinant, order 58, http://mathscinet.ru/catalogue/artifact58
12. Balonin N. A. Existence of Mersenne Matrices of 11th and 19th Orders. Informatsionno-upravliaiushchie sistemy, 2013. є 2, pp. 89 Ц 90 (In Russian).
13. Balonin N. A., Sergeev M. ¬. Two Ways to Construct Hadamard-Euler Matrices. Informatsionno-upravliaiushchie sistemy, 2013. є 1(62), pp. 7Ц10 (In Russian).
14. Sergeev A.M. Generalized Mersenne Matrices and BaloninТs Conjecture. Automatic Control and Computer Sciences, 2014. Vol. 48, є 4. pp. 214Ц220.
15. 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

Rambler's Top100