<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Weighing Matrices and String Sorting
Ilias S. Kotsireas1, Christos Koukouvinos2, and Jennifer Seberry3
Department of Physics and Computer Science, Wilfrid Laurier University, 75 University Avenue West, Waterloo, Ontario N2L 3C5, Canada
ikotsire@wlu.ca
Department of Mathematics, National Technical University of Athens, Zografou 15773, Athens, Greece
ckoukouv@math.ntua.gr
Centre for Computer Security Research, School of Information Technology and Computer Science, University of Wollongong, Wollongong, NSW 2522, Australia
j.seberry@uow.edu.au
Annals of Combinatorics 13 (3) pp.305-313 September, 2009
AMS Subject Classification: 05B20, 62K05
Abstract:
In this paper we establish a fundamental link between the search for weighing matrices constructed from two circulants and the operation of sorting strings, an operation that has been studied extensively in computer science. In particular, we demonstrate that the search for weighing matrices constructed from two circulants using the power spectral density criterion and exploiting structural patterns for the locations of the zeros in candidate solutions, can be viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. This allows us to bring into bear efficient algorithms from the string sorting literature. We also state and prove some new enhancements to the power spectral density criterion, that allow us to treat successfully the rounding error effect and speed up the algorithm. Finally, we use these ideas to find new weighing matrices of order $2n$ and weights $2n-13$, $2n-17$ constructed from two circulants.
Keywords: weighing matrices, algorithm, pattern, locations of zeros, power spectral density, rounding error

References:

1. Arasu, K.T., Gulliver, T.A.: Self-dual codes over Fp and weighing matrices. IEEE Trans. Inform. Theory 47, 2051-–2055 (2001)

2. Craigen, R.: Weighing matrices and conference matrices. In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, pp. 496–-504. CRC Press, Boca Raton (1996)

3. Craigen, R.: The structure of weighing matrices having large weights. Des. Codes Cryptogr. 5, 199-–216 (1995)

4. Craigen, R., Kharaghani, H.: Orthogonal designs. In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, pp. 280-–295. CRC Press, Boca Raton (2006)

5. Fletcher, R.J., Gysin, M., Seberry, J.: Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices. Australas. J. Combin. 23, 75-–86 (2001)

6. Geramita, A.V., Seberry, J.: Orthogonal Designs: Quadratic Forms and Hadamard Matrices. Marcel Dekker Inc., New York (1979)

7. Knuth, D.E.: The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison- Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Mass.- London-Don Mills (1973)

8. Koukouvinos, C., Seberry, J.: New weighing matrices and orthogonal designs constructed using two sequences with zero autocorrelation function-a review. J. Statist. Plann. Inference 81, 153-–182 (1999)

9. Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration and Search. CRC press, Boca Raton (1998)