Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

implement more constructions for Hadamard matrices, e.g. for size 116 #34690

Closed
dimpase opened this issue Oct 24, 2022 · 61 comments
Closed

implement more constructions for Hadamard matrices, e.g. for size 116 #34690

dimpase opened this issue Oct 24, 2022 · 61 comments
Labels
c: combinatorics p: major / 3 t: enhancement
Milestone
sage-9.8

Comments

@dimpase
Copy link
Member

dimpase commented Oct 24, 2022

With #32267 done, the next not yet implemented construction is for n=116. This was originally constructed by Williamson,
cf e.g. Marshall Hall's book https://onlinelibrary.wiley.com/doi/book/10.1002/9781118032862

Implementing Williamson construction would be a natural way here.

Depends on #32267

CC: @MatteoCati

Component: combinatorics

Author: Matteo Cati

Branch/Commit: bd025a2

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/34690
@dimpase dimpase added this to the sage-9.8 milestone Oct 24, 2022
@dimpase

This comment has been minimized.

Sign in to view
@MatteoCati
Copy link
Contributor

Branch: u/gh-MatteoCati/add_williamson_contruction_hadamard_matrices

@MatteoCati
Copy link
Contributor

Author: Matteo Cati

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 29, 2022

Commit: 30ae555

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 29, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

57a2d1dAdd test failing when matrix can be generated by paleyI
822b99aTry recursive method in hadamard_matrix only if it will be successful
c1a371eAdd tests for matrices created by skew_hadamard_matrix and regular_symmetric_hadamard_matrix_with_constant_diagonal
a411049Add skew_hadamard_matrix and regular_symmetric_hadamard_matrix_with_constant_diagonal to hadamard_matrix function
86506ceFix failed test returning Unknown in hadamard_matrix
ec34204docstring fixes for Payley constructions
ab88569Add williamson type hadamard matrix construction
2b8d298Add contruction of williamson type hadamard matrix for n=116 and n=172
06f3cf2Always check williamson necessary conditions
30ae555Add williamson method to general hadamard matrix contruction

@MatteoCati
Copy link
Contributor

comment:5

Added Williamson construction, together with data for creating hadamard matrices of order 116 and 172 using this construction.

@MatteoCati
Copy link
Contributor

Dependencies: #32267

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 29, 2022

Changed commit from 30ae555 to 1519681

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 29, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

1519681Fix documentation for williamson contruction

@dimpase
Copy link
Member Author

dimpase commented Oct 29, 2022

comment:8

OK, good.

The 1st and 2nd smallest value for which we don't have an implementation.
are now 156 and 188.

156 was first constructed in https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-71/issue-1/A-new-construction-for-Hadamard-matrices/bams/1183526410.full

236 is the 3rd.
Here seems to be the reference on the 1st construction of Hadamard matrices of order 236: https://www.sciencedirect.com/science/article/pii/0097316574900569

For 188 there is https://arxiv.org/pdf/0704.0640.pdf - but most probably it's not the 1st such a construction.

@dimpase
Copy link
Member Author

dimpase commented Oct 31, 2022

comment:9

Do we always mean return a normalised Hadamard matrix?

Note that hadamard_matrix(116) fails, as there is a default check

    if check:
        assert is_hadamard_matrix(M, normalized=True)

which is done with normalized=True - which is not the case here.

@dimpase
Copy link
Member Author

dimpase commented Oct 31, 2022

comment:11

Please also check whether new matrices at #32267 work with hadamard_matrix(), i.e. we had this regression already...

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 31, 2022

Changed commit from 1519681 to 0e639f4

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 31, 2022

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1f2bd70Do not check for normalized matrix in hadmard_matrix
ea6ee67Add williamson type hadamard matrix construction
a028891Add contruction of williamson type hadamard matrix for n=116 and n=172
a20dc70Always check williamson necessary conditions
e69d10bAdd williamson method to general hadamard matrix contruction
5f8b7a8Fix documentation for williamson contruction
581e556Add construction for order 156
b5319f0Add documentation for hadamard_matrix_156
0e639f4Add matrix of order 156 to general hadamard matrix construction

@MatteoCati
Copy link
Contributor

comment:13

Replying to Dima Pasechnik:

Please also check whether new matrices at #32267 work with hadamard_matrix(), i.e. we had this regression already...

This error was already present in #32267, so I fixed it in that ticket and then rebased this one.

@dimpase
Copy link
Member Author

dimpase commented Oct 31, 2022

comment:14

rebased over latest beta, slight reference fix

Last 10 new commits:

74b71f5docstring fixes for Payley constructions
17c5755Do not check for normalized matrix in hadmard_matrix
b8132e7Add williamson type hadamard matrix construction
7ae0d78Add contruction of williamson type hadamard matrix for n=116 and n=172
07c7803Always check williamson necessary conditions
d4f4290Add williamson method to general hadamard matrix contruction
0bfcbd9Fix documentation for williamson contruction
644f926Add construction for order 156
2e3b397Add documentation for hadamard_matrix_156
9bac7b5Add matrix of order 156 to general hadamard matrix construction

@dimpase
Copy link
Member Author

dimpase commented Oct 31, 2022

Reviewer: Dima Pasechnik

@dimpase
Copy link
Member Author

dimpase commented Oct 31, 2022

Changed branch from u/gh-MatteoCati/add_williamson_contruction_hadamard_matrices to u/dimpase/combinat/add_williamson_contruction_hadamard_matrices

@dimpase
Copy link
Member Author

dimpase commented Oct 31, 2022

Changed commit from 0e639f4 to 9bac7b5

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 31, 2022

Changed commit from 9bac7b5 to 7a9910f

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 31, 2022

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

7a9910fslight fix of the reference format

@dimpase
Copy link
Member Author

dimpase commented Nov 23, 2022

comment:31

In docstrings, please keep Hadamard capitalised.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 23, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

163d780Fix typos in docstrings

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 23, 2022

Changed commit from 53c98c8 to 163d780

@MatteoCati
Copy link
Contributor

comment:33

The next construction that can be implemented is the one described in https://core.ac.uk/download/pdf/82189436.pdf, which will give new Hadamard matrices for many different orders (including 292, which is the smallest value currently missing).

@dimpase
Copy link
Member Author

dimpase commented Nov 27, 2022

comment:34

OK, great. For comment:33 constructions, please open a follow-up ticket.

How far will we be from 668 (the 1st 4k for which existence of a matrix is unknown) then?

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 28, 2022

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

ef50ecdAdd note for typo in reference for T-sequences construction

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 28, 2022

Changed commit from 163d780 to ef50ecd

@MatteoCati
Copy link
Contributor

comment:36

Replying to Dima Pasechnik:

How far will we be from 668 (the 1st 4k for which existence of a matrix is unknown) then?

After implementing the construction in comment:33 the missing orders will be 412, 428, 452, 476, 508, 532, 604, 612, 652 but it should be possible to implement all of them just by adding more data (T-sequence and williamson type matrices) to the constructions that are already present.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 28, 2022

Changed commit from ef50ecd to 3b5f11c

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 28, 2022

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3b5f11cAdd note for typo in reference for T-sequences construction

@MatteoCati
Copy link
Contributor

comment:38

I've created the next ticket: #34807

@dimpase
Copy link
Member Author

dimpase commented Nov 29, 2022

comment:39

Could you replace sets in ...-sequences are sets of four (-1, 0, 1) sequences (2 times) in combinat/t_sequences.py with tuples ? (At least in the 2nd case it's obvious that each of the 4 -1,0,1-sequences plays a distinct role, so they can't be just be swapped arbitrarily.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 29, 2022

Changed commit from 3b5f11c to b936e18

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 29, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

b936e18Fix documentation of T sequences

@dimpase
Copy link
Member Author

dimpase commented Nov 29, 2022

Changed branch from u/gh-MatteoCati/add_hadamard_matrices_constructions to u/dimpase/add_hadamard_matrices_constructions

@dimpase
Copy link
Member Author

dimpase commented Nov 29, 2022

New commits:

021fbe5adding ref to the typo in old paper, and cosmetic changes
bd025a2refs to biblio file, trimmed trailing whitespaces, docstring fix

@dimpase
Copy link
Member Author

dimpase commented Nov 29, 2022

Changed commit from b936e18 to bd025a2

@dimpase
Copy link
Member Author

dimpase commented Nov 29, 2022

comment:42

looks good.

@vbraun
Copy link
Member

vbraun commented Dec 11, 2022

Changed branch from u/dimpase/add_hadamard_matrices_constructions to bd025a2

@vbraun vbraun closed this as completed in fb4c96a Dec 11, 2022
@MatteoCati MatteoCati mentioned this issue Jan 5, 2023
Closed
kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023
Trac sagemath#34807: Add Construction of Hadamard matrices up to orde…
bb63c58 
…r 664

With sagemath#34690, all the Hadamard matrices of order <=288 have been added.
The next task is to implement matrices of order up to 664 (668 is the
first order for which no construction is known). This will require
implementing https://core.ac.uk/download/pdf/82189436.pdf, as well as
adding some more data for the constructions that are already present.

URL: https://trac.sagemath.org/34807
Reported by: gh-MatteoCati
Ticket author(s): Matteo Cati
Reviewer(s): Dima Pasechnik
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: combinatorics p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-9.8
Development

No branches or pull requests
3 participants
@vbraun @dimpase @MatteoCati