On Ryser’s Conjecture
Antun Domic, Luis H. Gallardo · 2025
Read On Ryser’s Conjecture by Antun Domic, Luis H. Gallardo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00619.txt.
Introduction
Antun Domic and one co-author, Luis H Gallardo, give new sufficient conditions under which Ryser's conjecture holds. A sufficient condition is a test that, when met, guarantees the claim, even if the claim might also hold in other cases. The record presents the work at this level, as a contribution to settling a named open problem in combinatorics, the study of counting and arrangements.
Catalog record
| CREATOR | Antun Domic, Luis H. Gallardo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00619
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Ryser’s Conjecture Antun Domic, Luis H. Gallardo Abstract . We provide new sufficient conditions under which Ryser’s conjecture holds. 2000 Mathematics Subject Classification Primary 11B30, 15B34 Secondary 11C20 1. Introduction Let A be a square matrix of order n with complex coefficients. We denote by A^{*} the conjugate transpose of the matrix A . For any pair of rows R_{i},R_{j} of a matrix A with real coefficients, we denote by \langle R_{i},R_{j}\rangle the usual scalar product. A circulant matrix A:=\operatorname{circm}(a_{1},\ldots,a_{n}) of order n is a matrix of order n whose first row is [a_{1},\ldots,a_{n}] and in which each row after the first is obtained by a cyclic shift of its predecessor by one position. For example, the second row R_{2} of A is [a_{n},a_{1},\ldots,a_{n-1}] . With \pi:=\operatorname{circm}(0,1,0,\ldots,0) , one has that R_{2} is the first row of \pi A . A Hadamard matrix H of order n is a matrix of order n with entries in \{-1,1\} such that K:=\frac{H}{\sqrt{n}} is orthogonal. A circulant Hadamard matrix of order n is a circulant matrix that is also Hadamard. Besides the two trivial matrices of order 1 , H_{1}:=\operatorname{circm}(1) and H_{2}:=-H_{1} , the remaining 8 known circulant Hadamard matrices are H_{3}:=\operatorname{circm}(1,-1,-1,-1),H_{4}:=-H_{3},H_{5}:=\operatorname{circm}(-1,1,-1,-1),H_{6}:=-H_{5}, H_{7}:=\operatorname{circm}(-1,-1,1,-1),H_{8}:=-H_{7},H_{9}:=\operatorname{circm}(-1,-1,-1,1),H_{10}:=-H_{9}. If H=\operatorname{circm}(h_{1},\ldots,h_{n}) is a circulant Hadamard matrix of order n , then its representer polynomial is R(x):=h_{1}+h_{2}x+\cdots+h_{n}x^{n-1}. No other circulant Hadamard matrices are known. Ryser conjectured in 1963 (see [ 19 ] , [ 1 , p. 97] ) that no such matrices exist when n>4 . Previous work on the conjecture include [ 2 , 3 , 6 , 7 , 8 , 9 , 11 , 13 , 15 , 16 , 21 ] . Let H=\operatorname{circm}(h_{1},\ldots,h_{n}) be a circulant Hadamard matrix of order n\geq 4 . Define E_{1}:=\operatorname{circm}(h_{1},h_{3},h_{5},\ldots,h_{n-1}),\quad E_{2}:=\operatorname{circm}(h_{2},h_{4},h_{6},\ldots,h_{n}). When n=4 , both E_{1} and E_{2} have rank equal to 1 (as their determinant is 0, see the matrices H_{3},\ldots,H_{10} ). Two other interesting properties of E_{1} and E_{2} when n=4 are the following: Remark 1.1 . Let K_{1}:=\frac{E_{1}+E_{2}}{2} and K_{2}:=\frac{E_{1}-E_{2}}{2} . Then: (a) K_{1} and K_{2} are projections. (b) K_{1} and K_{2} , reduced modulo 2 , are symmetric orthogonal matrices. Property (b) in Remark 1.1 is significant because of a result of McWilliams [ 12 , Corollary 1.8] (see also Lemma 2.3 ) which states that for n>2 , the orthogonal group \mathbb{O}(n,\mathbb{F}_{2}) consists only of the identity matrix. In other words, n=4 is the only case in which (b) holds. When a circulant Hadamard matrix of order n\geq 4 is such that both E_{1} and E_{2} are non-singular, it follows from [ 9 ] and our Lemma 2.12 (see Section 2 ) that n must equal 4 . The rank- 1 property that we consider in the present paper is the first natural case to study in order to make progress on the open case when at least one of E_{1},E_{2} is singular. In this paper we prove two results. Essentially, the first shows that for circulant Hadamard matrices of order n , the rank- 1 property and properties (a) and (b) in Remark 1.1 hold for n=4 and do not hold when n>4 . Our second main result, which follows from a simple characterization of circulant matrices of rank \leq 2 together with the Plotkin bound for codewords, proves the more general statement that there is no circulant Hadamard matrix of order >4 in which either one of the submatrices E_{1},E_{2} has rank 1 while the other has arbitrary rank, or both have rank 2 . More precisely, in this paper we prove the following two theorems. Theorem 1.2 . Let H=\operatorname{circm}(h_{1},\ldots,h_{n}) be a circulant Hadamard matrix of order n\geq 4 . Let E_{1}:=\operatorname{circm}(h_{1},h_{3},h_{5},\ldots,h_{n-1}) and E_{2}:=\operatorname{circm}(h_{2},h_{4},h_{6},\ldots,h_{n}) . We denote by R_{j} , respectively S_{j} , the rows of E_{1} and E_{2} , for j=1,\ldots,n/2 . Let G_{1}:=E_{1}E_{1}^{*} and G_{2}:=E_{2}E_{2}^{*} be the Gram matrices of E_{1} and E_{2} . Assume that one of the following statements holds: (a) \operatorname{rank}(E_{1})=1=\operatorname{rank}(E_{2}) . (b) All entries of G_{1} and G_{2} have the same absolute value. (c) R_{1} and R_{2} are linearly dependent over \mathbb{Q} , and S_{1} and S_{2} are linearly dependent over \mathbb{Q} . (d) |\langle R_{1},R_{2}\rangle|=|\langle R_{1},R_{1}\rangle| , and |\langle S_{1},S_{2}\rangle|=|\langle S_{1},S_{1}\rangle| . Then n=4 . Remark 1.3 . All statements (a), (b), (c), and (d) of the theorem hold when n=4 . Moreover, for any entry e of G_{1} or G_{2} , we have |e|=2=n/2 . Remark 1.4 . Our results also cover the recent generalization of the circulant Hadamard conjecture [ 5 ] by Goyeneche and Turek, since a generalized circulant Hadamard matrix H(d):=\operatorname{circm}(d,h_{2},\ldots,h_{n}) satisfying our hypotheses necessarily has |d|=1 . Our second main result is as follows: Theorem 1.5 . With the notation of Theorem 1.2 , there is no circulant Hadamard matrix H of order n>4 in the following two cases: (a) One of E_{1},E_{2} has rank 1 . (b) Both E_{1} and E_{2} have rank 2 . The needed preliminaries for the proofs are given in Section 2 . The proof of Theorem 1.2 is presented in Section 3 . The proof of Theorem 1.5 is presented in Section 4 . 2. Preliminaries Our first lemma is well known and easy to prove. Lemma 2.1 . Let A be a real matrix. Then \operatorname{rank}(A^{*}A)=\operatorname{rank}(AA^{*})=\operatorname{rank}(A)=\operatorname{rank}(A^{*}) . The following lemma ( [ 1 ] ) is useful. Lemma 2.2 . Let C:=\operatorname{circm}(c_{1},\ldots,c_{k}) be a circulant matrix of order k . Let v:=[1,\ldots,1]\in\mathbb{R}^{k} . Then v is an eigenvector of C with associated eigenvalue \lambda:=c_{1}+\cdots+c_{k} . The following is a result of MacWilliams [ 12 ] . It was already used in [ 10 , Theorem 1] . Lemma 2.3 . The only circulant, symmetric, and orthogonal matrix over the binary field \mathbb{F}_{2} of order n>2 is the identity matrix I_{n} . The next lemma (see [ 20 , Lemma 8.6] ) is frequently used in the theory of group representations. Here it is useful for the proof of part (d) of Theorem 1.2 . Lemma 2.4 . Let c_{1},\ldots,c_{\ell} be \ell complex numbers of absolute value 1 . If |c_{1}+\cdots+c_{\ell}|=\ell, then c_{1}=\cdots=c_{\ell} . The following lemma gives some properties of certain circulant matrices of rank 1 . Lemma 2.5 . Let C:=\operatorname{circm}(c_{1},\ldots,c_{2k}) be a circulant matrix of order 2k and rank 1 such that c_{j}^{2}=1 for all j=1,\ldots,2k . Then for all s=1,\ldots,k we have c_{2s-1}=a and c_{2s}=b , with \{a,b\}\subseteq\{-1,1\} . Moreover, if a\neq b then c_{1}+c_{2}+\cdots+c_{2k}=0. Proof. Since \operatorname{rank}(C)=1 , the second row R_{2} of C is a multiple of the first row R_{1} . As each entry of C is 1 or -1 , there are two cases to consider: (a) R_{1}=R_{2} and (b) R_{1}=-R_{2} . In case (a), comparing the first entries of R_{1} and R_{2} gives c_{2k}=c_{1} , and comparing the others shows c_{1}=c_{2}=c_{3}=\cdots=c_{2k-1} . Thus all entries of R_{1} are equal, so a=b\in\{-1,1\} . In case (b), a similar argument gives the stated result. If a\neq b , then \{a,b\}=\{-1,1\} , so c_{1}+c_{2}+\cdots+c_{2k}=a+b=0 . ∎ The following lemma gives some properties of certain circulant matrices of rank 2 . Lemma 2.6 . Let D:=\operatorname{circm}(d_{1},\ldots,d_{2k}) be a circulant matrix of order 2k\geq 6 and rank 2 such that d_{j}^{2}=1 for all j=1,\ldots,2k . Assume that the