Hill Publishing Group | contact@hillpublisher.com

Hill Publishing Group

Location:Home / Journals / Journal of Applied Mathematics and Computation /

DOI:http://dx.doi.org/10.26855/jamc.2022.06.005

Fast and Parallel Algorithms Specifying Determinants of ±1 Matrices and a Theoretical Construction of the Spectrum

Date: May 25,2022 |Hits: 180 Download PDF How to cite this paper

Chrysovalantis A. Sfyrakis

Department of Mechanical Engineering Educators, School of Pedagogical & Technological Education (ASPETE), Marousi, Attica, Greece.

*Corresponding author: Chrysovalantis A. Sfyrakis

Abstract

In this paper, it is presented algorithms constructing all possible vectors of dimension n with elements ±1. This leads to the construction of efficient algorithms specifying the determinants of n×n matrices with elements ±1. Is presented the notion of lexicographically ordered sequences of integers and matrices and we describe algorithms creating all possible lexicographically ordered vectors of dimension. We give three sequential algorithms computing all possible determinants and we compare these algorithms according to their speed and efficiency. The parallel implementation of the algorithms is introduced and analysed the complexity, concerning the performance of the methods according to the number of available processors are given. The speedup and the efficiency of the proposed methods for the case of n=7 and 8 is presented and their efficiency is examined by comparing them with known ones.

References

[1] J. Hadamard. (1893). Resolution d’ une question relative aux determinants, Bulletin des Sciences mathematiques (1893), 17: 240-24.

[2] J. Day and B. Peterson. (1988). Growth in Gaussian elimination. Amer. Math. Monthly, 95(1988), 489-513.

[3] F. Szollosi. (2010). Exotic Complex Hadamard matrices and their equiralence. Cryptogr. Commun., 2, (2010), 187-198.

[4] C. W. Cryer. (1968). Pivot size in Gaussian Elimination. Numer. Math., 12(1968), 335-346.

[5] Spectrum of the determinant function. http://www.indiana.edu/ maxdet/spectrum.html.

[6] N. Metropolis. (1971). Spectra of determinant values in (0,1) matrices. In A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory: Proceedings of the Science Research Atlas Symposium No. 2 held at Oxford, 18-23 August, 1969, Academic Press, London, 1971, 271-276.

[7] R. Craigen. (1990). The range of the determinant function of a set of n×n (0,1)-Matrices. Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 8 (1990), 161-171.

[8] M. Z ̆ivkovic'. (2006). Classification of small (0,1) matrices. Linear Algebra Appl., 414(2006), 1, 310-346.

[9] W. P. Orrick. (2005). The maximal {-1, 1}-determinant of order 15. Metrika, 62(2005), 195-219.

[10] Horn, R. A., Johnson, C. R. (1985). Matrix Analysis. Cambridge University Press: Cambridge, 1985.

[11] Geramita, A. V., Seberry, J. (1979). Orthogonal Designs: Quadratic Forms and Hadamard Matrices Morcel Dekker, New York, Basel, 1979. 

[12] C. Krattenthaler. (2005). Advanced determinant calculus: A complement. Linear Algebra Appl., 411(2005), 68-166. 

[13] C. M. Ballantine, S. M. Frechette, and J. B. Little. (2005). Determinants associated to zeta matrices of posets. Linear Algebra Appl., 411(2005), 364-370.

[14] C. Kravvaritis, M. Mitrouli. (2007). Evaluation of minors associated to weighing matrices. Linear Algebra and its Appl., Vol. 426(2007), 774-809.

[15] J. Seberry, T. Xia, C. Koukouvinos, and M. Mitrouli. (2003). The maximal determinant and subdeterminants of ±1 matrices. Linear Algebra Appl., 373(2003), 297-310.

[16] L. N. Trefethen and D. Bau, III. (1997). Numerical Linear Algebra, SIAM, Philadelphia, 1997.

[17] C. Wenchang. (2006). The Faà di Bruno formula and determinant identities. Linear Multilinear Algebra, 54(2006), 1-25.

[18] J. Williamson. (1946). Determinants whose elements are 0 and 1. Amer. Math. Monthly, 53(1946), 427-434.

[19] Egan, R., Flannery, D. L. (2017). Automorphisms of generalized Sylvester Hadamard matrices. Discrete Math., 340 (2017), no. 3, 516-523.

[20] Mitrouli, M., Turek, O. (2018). Determinantal Properties of Generalized Circulant Hadamard Matrices. Electronic Journal of Linear Algebra, 34: 639-651, 2018.

How to cite this paper

Fast and Parallel Algorithms Specifying Determinants of ±1 Matrices and a Theoretical Construction of the Spectrum

How to cite this paper: Chrysovalantis A. Sfyrakis. (2022) Fast and Parallel Algorithms Specifying Determinants of ±1 Matrices and a Theoretical Construction of the Spectrum. Journal of Applied Mathematics and Computation6(2), 206-218.

DOI: http://dx.doi.org/10.26855/jamc.2022.06.005

Volumes & Issues

Free HPG Newsletters

Add your e-mail address to receive free newsletters from Hill Publishing Group.

Contact us

Hill Publishing Group

8825 53rd Ave

Elmhurst, NY 11373, USA

E-mail: contact@hillpublisher.com

Copyright © 2019 Hill Publishing Group Inc. All Rights Reserved.