Cocyclic Hadamard matrices over Latin rectangles

Cocyclic Hadamard matrices over Latin rectangles Ra´ul M. Falc´on Department of Applied Mathematics I. University of Seville. (Joint work with V. ´ Alvarez, M. D. Frau, M. B. G¨uemes and F. Gudiel). Budapest. July 14, 2017. 5th Workshop on Real and Complex Hadamard Matrices and Applications Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles Ra´ul M. Falc´on Department of Applied Mathematics I. University of Seville. (Joint work with V. ´ Alvarez, M. D. Frau, M. B. G¨uemes and F. Gudiel). Budapest. July 14, 2017. 5th Workshop on Real and Complex Hadamard Matrices and Applications Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles CONTENTS I. Preliminaries. II. Cocycles over Latin rectangles. III. Cocyclic Hadamard matrices over Latin rectangles. IV. Further work. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles I. Preliminaries. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices. Kathy J. Horadam. Warwick De Launey. Cocycle over a finite group G: ψ:G×G→ h 1,−1isuch that ψ(ij,k)ψ(i,j)ψ(j,k)ψ(i,jk) = 1, for all i,j,k∈G. Cocyclic matrix: Mψ= (ψ(i,j))i,j∈G. MψHadamard →Cocyclic Hadamard matrix over G. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 ⇒  1 1 1 1 1 1 −1−1 1−1−1 1 1−1 1 −1  . Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices. Kathy J. Horadam. Warwick De Launey. Cocycle over a finite group G: ψ:G×G→ h 1,−1isuch that ψ(ij,k)ψ(i,j)ψ(j,k)ψ(i,jk) = 1, for all i,j,k∈G. Cocyclic matrix: Mψ= (ψ(i,j))i,j∈G. MψHadamard →Cocyclic Hadamard matrix over G. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 ⇒  ++++ + + − − +− − + +−+−  . Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices. Kathy J. Horadam. Warwick De Launey. Cocycle over a finite group G: ψ:G×G→ h 1,−1isuch that ψ(ij,k)ψ(i,j)ψ(j,k)ψ(i,jk) = 1, for all i,j,k∈G. Cocyclic matrix: Mψ= (ψ(i,j))i,j∈G. MψHadamard →Cocyclic Hadamard matrix over G. Dane L. Flannery. Cocyclic Hadamard matrices over D4t:= ha,b|a2t=b2= (ab)2= 1 i, for all positive integer t≤11. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Latin rectangles (Rr,n). Andalusian Mathematical Olympiad. Seville, 2016. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Latin rectangles (Rr,n). Let r,nbe two positive integers such that r≤n. Latin rectangle:r×narray where 1each cell contains one symbol of [n]:= {1,...,n}. 2each symbol occurs once per row and at most once per column. L≡ 1 4 3 2 3 2 1 4 2 3 4 1 ∈ R3,4. Latin square:r=n→Quasigroup ([n],·). Reduced: Symbols appearing in its first row and its first column are displayed in natural order. L≡ 1 2 3 4 2 4 1 3 3 1 4 2 ∈ R3,4. r=n→Loop (quasigroup with unit element). Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles. L≡23416785 35687214⇒S(L) = {e1,e2,e3,e4}. ⇓ Mψ≡  +− − +++− − −+−+ + −+− − − +++− − + +++−+−−−  ⇒MψMt ψ= 8 Id4=nId|S(L)|. Rr,n:= {L∈ Rr,n:|S(L)|=n}. Let L∈ Rr,n. HL:= {MψHadamard: ψ∈ CL}. L≡2 3 4 1 3 4 1 2 ∈ R2,4→  + + − − +−+− −+ + − −−−−  ∈ HL. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles. L≡23416785 35687214⇒S(L) = {e1,e2,e3,e4}. ⇓ Mψ≡  +− − +++− − −+−+ + −+− − − +++− − + +++−+−−−  ⇒MψMt ψ= 8 Id4=nId|S(L)|. Rr,n:= {L∈ Rr,n:|S(L)|=n}. Let L∈ Rr,n. HL:= {MψHadamard: ψ∈ CL}. L≡2 3 4 1 3 4 1 2 ∈ R2,4→  + + − − +−+− −+ + − −−−−  ∈ HL. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles. L≡23416785 35687214⇒S(L) = {e1,e2,e3,e4}. ⇓ Mψ≡  +− − +++− − −+−+ + −+− − − +++− − + +++−+−−−  ⇒MψMt ψ= 8 Id4=nId|S(L)|. Rr,n:= {L∈ Rr,n:|S(L)|=n}. Let L∈ Rr,n. HL:= {MψHadamard: ψ∈ CL}. L≡2 3 4 1 3 4 1 2 ∈ R2,4→  + + − − +−+− −+ + − −−−−  ∈ HL. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles. L≡23416785 35687214⇒S(L) = {e1,e2,e3,e4}. ⇓ Mψ≡  +− − +++− − −+−+ + −+− − − +++− − + +++−+−−−  ⇒MψMt ψ= 8 Id4=nId|S(L)|. Rr,n:= {L∈ Rr,n:|S(L)|=n}. Let L∈ Rr,n. HL:= {MψHadamard: ψ∈ CL}. L≡2 3 4 1 3 4 1 2 ∈ R2,4→  + + − − +−+− −+ + − −−−−  ∈ HL. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles. L≡23416785 35687214⇒S(L) = {e1,e2,e3,e4}. ⇓ Mψ≡  +− − +++− − −+−+ + −+− − − +++− − + +++−+−−−  ⇒MψMt ψ= 8 Id4=nId|S(L)|. Rr,n:= {L∈ Rr,n:|S(L)|=n}. Let L∈ Rr,n. HL:= {MψHadamard: ψ∈ CL}. L≡ 12345678 21436587 34567812 43781265 ∈ R4,8→            ++++++++ +− − + + − − + +− − +−+ + − + + + + − − − − + + − − + + − − +−+− − +−+ +−+−+−+− + + − − − − + +            ∈ HL. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles (groups). L≡ 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 ∈ R4,4⇒S(L) = {1,2,3,4}.   ++++ + + − − +− − + +−+−  ∈ HL. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over Latin rectangles. Problem (1) L∈ Rr,n⇒ HL6=∅? Problem (2) Let Mbe a Hadamard matrix of order n. Does there exist L∈ Rr,n such that M∈ HL? Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles III. Cocyclic Hadamard matrices over Latin rectangles. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocycles over Latin rectangles. Lemma Let L= (lij )∈ Rr,nand ψ∈ CL. lij =i⇒ψ(lki ,j) = ψ(i,j), for all k≤r. lij =jfor some i,j≤r⇒ψ(i,k) = ψ(i,j), for all k≤n. 1 2 4 3 3 4 2 1 →  ++++ −+−+ +− − + + + − −   1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−   Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocycles over Latin rectangles. Lemma Let L= (lij )∈ Rr,nand ψ∈ CL. lij =i⇒ψ(lki ,j) = ψ(i,j), for all k≤r. lij =jfor some i,j≤r⇒ψ(i,k) = ψ(i,j), for all k≤n. 1 2 4 3 3 4 2 1 →  ++++ −+−+ +− − + + + − −   1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−   Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocycles over Latin rectangles. Lemma Let L= (lij )∈ Rr,nand ψ∈ CL. lij =i⇒ψ(lki ,j) = ψ(i,j), for all k≤r. lij =jfor some i,j≤r⇒ψ(i,k) = ψ(i,j), for all k≤n. 1 2 4 3 3 4 2 1 →  ++++ −+−+ +− − + + + − −   1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−   Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Proposition Let L= (lij )∈ Rr,nbe such that HL6=∅. lij =j, for some i,j≤r⇒lik =k, for all k≤r. ⇓ #{k≤n|lik =k}>n/2⇒lki =k, for all i≤r. 1 2 4 3 3 4 2 1 →  ++++ −+−+ +− − + + + − −   1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−   Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Proposition Let L= (lij )∈ Rr,nbe such that HL6=∅. lij =j, for some i,j≤r⇒lik =k, for all k≤r. ⇓ #{k≤n|lik =k}>n/2⇒lki =k, for all i≤r. 1 2 4 3 3 4 2 1 →  ++++ −+−+ +− − + + + − −   1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−   Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Proposition Let L= (lij )∈ Rr,nbe such that HL6=∅. lij =j, for some i,j≤r⇒lik =k, for all k≤r. ⇓ #{k≤n|lik =k}>n/2⇒lki =k, for all i≤r. 13547826 35821674 47618325 ∈ R3,8⇒ HL=∅. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Proposition Let L= (lij )∈ Rr,nbe such that HL6=∅. lij =j, for some i,j≤r⇒lik =k, for all k≤r. ⇓ #{k≤n|lik =k}>n/2⇒lki =k, for all i≤r. 1 2 4 3 3 4 2 1 →  ++++ −+−+ +− − + + + − −   1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−   Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Theorem Let L∈ Rn,nbe such that HL6=∅. Then, Lis the multiplication table of a loop. If ψ∈ CLand eis the unit element of the loop, then ψ(e,i) = ψ(j,e),∀i,j≤n. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−     ++++ −+−+ +− − + + + − −  ∈ HL,for none L∈ R4,4. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Theorem Let L∈ Rn,nbe such that HL6=∅. Then, Lis the multiplication table of a loop. If ψ∈ CLand eis the unit element of the loop, then ψ(e,i) = ψ(j,e),∀i,j≤n. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−     ++++ −+−+ +− − + + + − −  ∈ HL,for none L∈ R4,4. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Theorem Let L∈ Rn,nbe such that HL6=∅. Then, Lis the multiplication table of a loop. If ψ∈ CLand eis the unit element of the loop, then ψ(e,i) = ψ(j,e),∀i,j≤n. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 →  ++++ + + − − +− − + +−+−   1 2 4 3 3 4 2 1 →  ++++ −+−+ +− − + + + − −   Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Problem (3) Does there exist a non-associative loop L∈ Rr,nsuch that HL6=∅? 12345678 21436587 34127856 43218765 56873421 65784312 78651243 87562134 ∈ R8,8→     ++++++++ + + + + − − − − + + − − − − + + + + − − + + − − +− − +−+ + − +− − + + − − + +−+− − +−+ +−+−+−+−     Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Problem (3) Does there exist a non-associative loop L∈ Rr,nsuch that HL6=∅? 12345678 21436587 34127856 43218765 56873421 65784312 78651243 87562134 ∈ R8,8→     ++++++++ + + + + − − − − + + − − − − + + + + − − + + − − +− − +−+ + − +− − + + − − + +−+− − +−+ +−+−+−+−     Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Problem (4) What about the distribution of Latin rectangles into isomorphism (isotopism) classes? Lemma Let L1and L2be two Latin rectangles in Rr,nthat are isotopic by means of an isotopism (f,g,g)such that f(i) = g(i), for all i≤r. Then, there exists a 1-1correspondence between the sets CL1and CL2. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Problem (4) What about the distribution of Latin rectangles into isomorphism (isotopism) classes? Lemma Let L1and L2be two Latin rectangles in Rr,nthat are isomorphic. Then, there exists a 1-1correspondence between the sets CL1and CL2. Proposition Let L1and L2be two isomorphic Latin rectangles in Rr,n. Then, there exists a 1-1correspondence between HL1and HL2. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. Problem (4) What about the distribution of Latin rectangles into isomorphism (isotopism) classes? Lemma Let L1and L2be two Latin rectangles in Rr,nthat are isomorphic. Then, there exists a 1-1correspondence between the sets CL1and CL2. Proposition Let L1and L2be two isomorphic Latin rectangles in Rr,n. Then, there exists a 1-1correspondence between HL1and HL2. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Cocyclic Hadamard matrices over a Latin rectangle. r n L HL 1 1 1 + 2 21 + − −− 2 2 12 21 + + +− 4 1243 3421 + + + + + − − + + −+−+ + −− ++++ −+−+ + − − + + + −− ++++ −+ + −+−+− − − ++ ++++ +−+−+− − +− − ++ 2341 3412 + + − − +−+− − + + − − − −− +− − +−+−+− − + + + + ++ 2134 3421 + −+− − − + + + − − + + + ++ 2314 3421 + − − +−+−+−−−− + + −− 2314 4123 + −+− − − + + −+ + −+ + ++ 3 4 1234 2143 3412 + + + + + + − − +− − + + −+− ++++ ++− − +−+−+− −+ ++++ +−+−+− − + + + −− ++++ +−+−+ + − − +− −+ ++++ +− − + + −+−+ + −− ++++ +− − + + + − − +−+− 1234 2143 3421 + + + + + + − − +− − + + −+− ++++ ++− − +−+−+− −+ 2341 3412 4123 + + − − +−+− − + + − − − −− +− − +−+−+− − + + + + ++ 4 4 1234 2143 3412 4321 + + + + + + − − +− − + + −+− ++++ ++− − +−+−+− −+ ++++ +−+−+− − + + + −− ++++ +−+−+ + − − +− −+ ++++ +− − + + −+−+ + −− ++++ +− − + + + − − +−+− 1234 2143 3421 4312 + + + + + + − − +− − + + −+− ++++ ++− − +−+−+− −+ Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles IV. Further work. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Further work. Problem (2) Let Mbe a Hadamard matrix of order n. Does there exist L∈ Rr,n such that M∈ HL? Problem (5) Let Mbe a Hadamard matrix of order nfor which there exists L∈ Rr,nsuch that M∈ HL.Which is the minimum r∈Nfor which one such a Latin rectangle exists? Lemma Let L∈ Rr,nbe such that HL6=∅. Then, r≤n≤r+r2. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Further work. Problem (2) Let Mbe a Hadamard matrix of order n. Does there exist L∈ Rr,n such that M∈ HL? Problem (5) Let Mbe a Hadamard matrix of order nfor which there exists L∈ Rr,nsuch that M∈ HL.Which is the minimum r∈Nfor which one such a Latin rectangle exists? Lemma Let L∈ Rr,nbe such that HL6=∅. Then, r≤n≤r+r2. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Further work. Problem (2) Let Mbe a Hadamard matrix of order n. Does there exist L∈ Rr,n such that M∈ HL? Problem (5) Let Mbe a Hadamard matrix of order nfor which there exists L∈ Rr,nsuch that M∈ HL.Which is the minimum r∈Nfor which one such a Latin rectangle exists? Lemma Let L∈ Rr,nbe such that HL6=∅. Then, r≤n≤r+r2. Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Further work. r≤n≤r2+r. r= 1; n= 2. 2 1 →+− − −  r= 2; n= 4. 1243 3421→  + + + + +− − + +−+− + + − −   r= 3; n= 8. 1 2 3 4 7 8 5 6 2 5 8 3 1 6 7 4 4 7 6 2 8 3 1 5 →        ++++++++ + + + + − − − − + + − − − − + + + + − − + + − − +− − +−+ + − +− − + + − − + +−+− − +−+ +−+−+−+−        Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles Further work. r≤n≤r2+r. r= 3; n= 12 ? 4 5 6 7 8 9 10 11 12 →              ++++++++++++ +−+−+++− − − +− +− − +−+++− − − + + + − − +−+++− − − +−+− − +−+++− − +− − +− − +−+ + + − +− − − +− − +−+++ + + − − − +− − +−+ + + + + − − − +− − +−+ + + + + − − − +− − +− +−+++− − − +− − + + + −+++− − − +− −              Ra´ul M. Falc´on Cocyclic Hadamard matrices over Latin rectangles