Hankel and Toeplitz X-rays of permutations. (English) Zbl 1286.05014
Summary: After considerable discussion intended to elucidate the connections between permutation matrices and their Hankel and Toeplitz X-rays, tournaments, transversals of partial Latin squares, and Skolem sequences, we prove several theorems concerning the existence of permutation matrices whose Hankel and Toeplitz X-rays have special properties such as being binary, palindromic, skew-palindromic, and equal. We give several methods of construction and many problems for further investigation. We also provide some numerical data obtained by computer calculation.
MSC:
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
| 05B30 | Other designs, configurations |
| 05B15 | Orthogonal arrays, Latin squares, Room squares |
| 15B34 | Boolean and Hadamard matrices |
Software:
OEISReferences:
| [1] | Bebeacua, C.; Mansour, T.; Postnikov, A.; Severini, S., On the X-rays of permutations, Electron. Notes Discrete Math., 20, 193-203 (2005) · Zbl 1179.05003 |
| [2] | Brualdi, R. A., Combinatorial Matrix Classes (2006), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK · Zbl 1106.05001 |
| [3] | Nordh, G., Perfect Skolem sets, Discrete Math., 308, 1653-1664 (2008) · Zbl 1135.05002 |
| [4] | Gardner, R. J.; Gritzmann, P.; Prangenberg, D., On the computational complexity of reconstructing lattice sets from their X-rays, Discrete Math., 202, 45-71 (1999) · Zbl 0947.68160 |
| [5] | Riven, I.; Vardi, I.; Zimmermann, P., The \(n\)-queens problem, Amer. Math. Monthly, 101, 629-639 (1994) · Zbl 0825.68479 |
| [6] | Shalaby, N., Skolem and Langford sequences, (Dinitz, J. H.; Colbourn, C. J., Handbook of Combinatorial Designs (2006), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL), 612-616, (Chapter 53) |
| [8] | Szaniszlo, Z.; Tomova, M.; Wyels, C., The \(N\)-queens problem on a symmetric Toeplitz matrix, Discrete Math., 309, 969-974 (2009) · Zbl 1197.05020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
