Weighing Matrices and String Sorting

Ilias S. Kotsireas^{1}, Christos Koukouvinos^{2}, and Jennifer
Seberry^{3}

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

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.
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)