Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
New Applications of γ-Quasiconvexity Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Computations for Minors of Weighing Matrices with Application to the Growth Problem

Author : Christos D. Kravvaritis

Published in: Applications of Nonlinear Analysis

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this expository paper we survey some important results concerning the computations for minors of weighing matrices. The applicability to the growth problem for weighing matrices is highlighted. The history of the problem is presented, the importance of determinant calculations is stressed and the relevant open problems are discussed. Emphasis is laid on the contribution of determinant calculations to the study of the growth factor for weighing matrices after application of Gaussian Elimination with complete pivoting on them, which is an important scientific open problem in Numerical Analysis.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Asymptotic Orbits in Hill’s Problem When the Larger Primary is a Source of Radiation
next chapter Robots That Do Not Avoid Obstacles
Literature
1.
V. Álvarez, J.A. Armario, M.D. Frau, F. Gudiel, Determinants of (−1,  1)-matrices of the skew-symmetric type: a cocyclic approach. Open Math. 13, 16–25 (2015)
2.
K.T. Arasu, K.H. Leung, S.L. Ma, A. Nabavi, D.K. Ray-Chaudhuri, Determination of all possible orders of weight 16 circulant weighing matrices. Finite Fields Appl. 12, 498–538 (2006)MathSciNetCrossRef
3.
4.
Y. Becis-Aubry, M. Boutayeb, M. Darouach, A parameter estimation algorithm for nonlinear multivariable systems subject to bounded disturbances, in Proceedings of the American Control Conference, Denver, vol. 4 (2003), pp. 3573–3578
5.
6.
J.D. Christian, B.L. Shader, Nonexistence results for Hadamard-like matrices. Electron. J. Comb. 11, #N1 (2004)
7.
8.
9.
B.N. Datta, Numerical Linear Algebra and Applications, 2nd edn. (SIAM, Philadelphia, 2010)
10.
11.
P. Delsarte, J.M. Goethals, J.J. Seidel, Orthogonal matrices with zero diagonal, II. Can. J. Math. 23, 816–832 (1971)MathSciNetCrossRef
12.
T.A. Driscoll, K.L. Maki, Searching for rare growth factors using Multicanonical Monte Carlo Methods. SIAM Rev. 49, 673–692 (2007)MathSciNetCrossRef
13.
A. Edelman, The complete pivoting conjecture for Gaussian elimination is false. Math. J. 2, 58–61 (1992)
14.
A. Edelman, W. Mascarenhas, On the complete pivoting conjecture for a Hadamard matrix of order 12. Linear Multilinear Algebra 38, 181–187 (1995)MathSciNetCrossRef
15.
P. Favati, M. Leoncini, A. Martiinez, On the robustness of Gaussian elimination with partial pivoting. BIT Numer. Math. 40, 62–73 (2000)
16.
G.E. Forsythe, C.B. Moler, Computer Solution of Linear Algebraic Systems (Prentice Hall, Englewood Cliffs, 1967)
17.
L.V. Foster, Gaussian elimination with partial pivoting can fail in practice. SIAM J. Matrix Anal. Appl. 15, 1354–1362 (1994)MathSciNetCrossRef
18.
L.V. Foster, The growth factor and efficiency of Gaussian elimination with rook pivoting. J. Comput. Appl. Math. 86,177–194 (1997)MathSciNetCrossRef
19.
F.R. Gantmacher, The Theory of Matrices, vol. 1 (Chelsea, New York, 1959)
20.
A.V. Geramita, J. Seberry, Orthogonal Designs: Quadratic Forms and Hadamard Matrices (Marcel Dekker, New York, 1979)
21.
A.V. Geramita, J.S. Wallis, Orthogonal designs. III. Weighing matrices. Utilitas Math. 6, 209–236 (1974)
22.
A.V. Geramita, J.M. Geramita, J.S. Wallis, Orthogonal designs. Linear Multilinear Algebra 3, 281–306 (1975/1976)
23.
24.
G.H. Golub, C.E. Van Loan, Matrix Computations, 4th edn. (John Hopkins University Press, Baltimore, 2013)
25.
N. Gould, On growth in Gaussian elimination with pivoting. SIAM J. Matrix Anal. Appl. 12, 354–361 (1991)
26.
K. Griffin, M.J. Tsatsomeros, Principal minors, Part I: A method for computing all the principal minors of a matrix. Linear Algebra Appl. 419, 107–124 (2006)MathSciNetCrossRef
27.
J. Hadamard, Résolution d’une question relative aux déterminants. Bull. Sci. Math. 17, 240–246 (1893)
28.
M. Hall, Combinatorial Theory (Wiley, New York, 1986)
29.
M. Harwit, N.J.A. Sloane, Hadamard Transform Optics (Academic, New York, 1979)CrossRef
30.
A.S. Hedayat, N.J.A. Sloane, J. Stufken, Orthogonal Arrays (Springer, New York, 1999)
31.
N.J. Higham, Accuracy and Stability of Numerical Algorithms (SIAM, Philadelphia, 2002)
32.
33.
N.J. Higham, D.J. Higham, Large growth factors in Gaussian elimination with pivoting. SIAM J. Matrix Anal. Appl. 10, 155–164 (1989)MathSciNetCrossRef
34.
K.J. Horadam, Hadamard Matrices and Their Applications (Princeton University Press, Princeton, 2007)
35.
R.A. Horn, C.R. Johnson, Matrix Analysis (Cambridge University Press, Cambridge, 1985)
36.
E. Howard, Elementary Matrix Theory (Dover Publications, Mineola, 1980)
37.
A. Karapiperi, M. Mitrouli, M.G. Neubauer, J. Seberry, An eigenvalue approach evaluating minors for weighing matrices W(n, n − 1). Linear Algebra Appl. 436, 2054–2066 (2012)
38.
39.
40.
C. Koukouvinos, M. Mitrouli, J. Seberry, Growth in Gaussian elimination for weighing matrices, W(n, n − 1). Linear Algebra Appl. 306, 189–202 (2000)
41.
C. Koukouvinos, M. Mitrouli, J. Seberry, An algorithm to find formulae and values of minors of Hadamard matrices. Linear Algebra Appl. 330, 129–147 (2001)MathSciNetCrossRef
42.
C. Koukouvinos, M. Mitrouli, J. Seberry, Values of minors of an infinite family of D-optimal designs and their application to the growth problem. SIAM J. Matrix Anal. Appl. 23, 1–14 (2001)MathSciNetCrossRef
43.
C. Kravvaritis, M. Mitrouli, Determinant evaluations for weighing matrices. Int. J. Pure Appl. Math. 34, 163–176 (2007)
44.
C. Kravvaritis, M. Mitrouli, Evaluation of minors associated to weighing matrices. Linear Algebra Appl. 426, 774–809 (2007)MathSciNetCrossRef
45.
C. Kravvaritis, M. Mitrouli, A technique for computing minors of binary Hadamard matrices and application to the growth problem. Electron. Trans. Numer. Anal. 31, 49–67 (2008)
46.
C. Kravvaritis, M. Mitrouli, The growth factor of a Hadamard matrix of order 16 is 16. Numer. Linear Algebra Appl. 16, 715–743 (2009)MathSciNetCrossRef
47.
C. Kravvaritis, M. Mitrouli, On the complete pivoting conjecture for Hadamard matrices: further progress and a good pivots property. Numer. Algorithms 62, 571–582 (2013)MathSciNetCrossRef
48.
C. Kravvaritis, E. Lappas, M. Mitrouli, An algorithm to find values of minors of Skew Hadamard and Conference matrices. Lect. Notes Comput. Sci. 3401, 375–382 (2005),
49.
C. Kravvaritis, M. Mitrouli, J. Seberry, Counting techniques specifying the existence of submatrices in weighing matrices. Lect. Notes Comput. Sci. 3718, 294–305 (2005)
50.
C. Kravvaritis, M. Mitrouli, J. Seberry, On the growth problem for skew and symmetric conference matrices. Linear Algebra Appl. 403, 83–206 (2005)MathSciNetCrossRef
51.
C. Kravvaritis, M. Mitrouli, J. Seberry, On the pivot structure for the weighing matrix W(12,  11). Linear Multilinear Algebra 55, 471–490 (2007)MathSciNetCrossRef
52.
M. Olschowka, A. Neumaier, A new pivoting strategy for Gaussian elimination. Linear Algebra Appl. 240, 131–151 (1996)MathSciNetCrossRef
53.
54.
55.
J. Seberry, M. Yamada, Hadamard matrices, sequences and block designs, in Contemporary Design Theory: A Collection of Surveys, ed. by D.J. Stinson, J.H. Dinitz (Wiley, New York, 1992), pp. 431–560
56.
J. Seberry, T. Xia, C. Koukouvinos, M. Mitrouli, The maximal determinant and subdeterminants of ± 1 matrices. Linear Algebra Appl. 373, 297–310 (2003)MathSciNetCrossRef
57.
58.
D. Souravlias, K.E. Parsopoulos, I.S. Kotsireas, Circulant weighing matrices: a demanding challenge for parallel optimization metaheuristics. Optim. Lett. 10, 1303–1314 (2016)MathSciNetCrossRef
59.
J.J. Sylvester, Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers. Philos. Mag. 34, 461–475 (1867)CrossRef
60.
61.
62.
L. Tornheim, Pivot size in Gauss reduction. Technical Report, California Resources Corporation, Richmond (1964)
63.
W. Trappe, L. Washington, Introduction to Cryptography with Coding Theory, 2nd edn. (Pearson Education, Upper Saddle River, 2006)
64.
L.N. Trefethen, Three mysteries of Gaussian elimination. ACM SIGNUM Newsl. 20, 2–5 (1985)CrossRef
65.
L.N. Trefethen, D. Bau III, Numerical Linear Algebra (SIAM, Philadelphia, 1997)CrossRef
66.
L.N. Trefethen, R.S. Schreiber, Average-case stability of Gaussian elimination. SIAM J. Matrix Anal. Appl. 11, 335–360 (1990)MathSciNetCrossRef
67.
68.
69.
W.D. Wallis, A.P. Street, J.S. Wallis, Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices. Lectures Notes in Mathematics, vol. 292 (Springer, New York, 1972)
70.
M. Wei, Q. Liu, On growth factors of the modified Gram-Schmidt algorithm. Numer. Linear Algebra Appl. 15, 621–626 (2008)MathSciNetCrossRef
71.
72.
J.H. Wilkinson, The Algebraic Eigenvalue Problem (Oxford University Press, London, 1965)MATH
73.
74.
S.J. Wright, A collection of problems for which Gaussian elimination with partial pivoting is unstable. SIAM J. Sci. Comput. 14, 231–238 (1993)MathSciNetCrossRef
75.
R.K. Yarlagadda, J.E. Hershey, Hadamard Matrix Analysis and Synthesis: With Applications to Communications and Signal/Image Processing (Kluwer, Boston, 1997)CrossRef
Metadata
Title
Computations for Minors of Weighing Matrices with Application to the Growth Problem
Author
Christos D. Kravvaritis
Copyright Year
2018
Book
Applications of Nonlinear Analysis

Print ISBN: 978-3-319-89814-8

Electronic ISBN: 978-3-319-89815-5

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-89815-5_19

Premium Partner

    Image Credits