IncidenceStructureFromMatrix bug

[KPanComputes]

The method IncidenceStructureFromMatrix has a serious bug, and it leads to serious errors in computations. We should fix it ASAP. For example, one may test with HadamardDesign (which uses the buggy implementation of IncidenceStructureFromMatrix). Consider the following output:

sage: D = designs.HadamardDesign(11); N = D.incidence_matrix()
sage: J = matrix(ZZ, 11, 11, [1]*11*11); N*J
[6 6 6 6 6 6 6 6 6 6 6]
[6 6 6 6 6 6 6 6 6 6 6]
[6 6 6 6 6 6 6 6 6 6 6]
[6 6 6 6 6 6 6 6 6 6 6]
[6 6 6 6 6 6 6 6 6 6 6]
[5 5 5 5 5 5 5 5 5 5 5]
[4 4 4 4 4 4 4 4 4 4 4]
[4 4 4 4 4 4 4 4 4 4 4]
[4 4 4 4 4 4 4 4 4 4 4]
[4 4 4 4 4 4 4 4 4 4 4]
[4 4 4 4 4 4 4 4 4 4 4]

The bug is the indexing used in the if-testing in the method.

CC: @nathanncohen

Component: combinatorics

Author: Kannappan Sampath

Branch/Commit: e2eab09

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/16237

[nathanncohen]

comment:1

Are you working on fixing it ?

Nathann

[KPanComputes]

comment:2

I have a fix but my GIT foo is not sufficient to upload it! :-( There is only one line of change to make: the if testing condition should be

if M[j, i] != 0

as opposed to the if M[i, j] != 0. :-) Similarly, I also have code for the HadamardThreeDesign too. :-)

[nathanncohen]

comment:3

You can ask on sage-devel if you have problems with GIT. They are writing a tutorial right now, it may give them ideas...

[KPanComputes]

Branch: u/knsam/16327

[KPanComputes]

New commits:

c30180a

trac #16327: Indexing in IncidenceStructureFromMatrix method fixed.

[KPanComputes]

Commit: c30180a

[sagetrac-git]

Changed commit from c30180a to bfba495

[sagetrac-git]

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

bfba495

trac #16237: Indexing in IncidenceStructureFromMatrix method fixed.

[KPanComputes]

comment:7

Firstly, the bug described is mathematical. And, that it is a bug is evident from following the code. This ticket fixes it and ALL doctests pass. However, the reason I have discovered this bug is itself another bug. So, I think, this ticket can double itself to fix this bug too.

So, the new bug is HadamardDesign method assumes that hadamard_matrix returns a Hadamard matrix whose first row and first column is the all-1 vector while hadamard_matrix method does not. This is why the example given in the method works but the example I describe does not:

sage: hadamard_matrix(8)
[ 1  1  1  1  1  1  1  1]
[ 1 -1  1 -1  1 -1  1 -1]
[ 1  1 -1 -1  1  1 -1 -1]
[ 1 -1 -1  1  1 -1 -1  1]
[ 1  1  1  1 -1 -1 -1 -1]
[ 1 -1  1 -1 -1  1 -1  1]
[ 1  1 -1 -1 -1 -1  1  1]
[ 1 -1 -1  1 -1  1  1 -1]
sage: hadamard_matrix(12)
[ 1  1  1  1  1  1|-1  1  1  1  1  1]
[ 1  1  1 -1 -1  1| 1 -1  1 -1 -1  1]
[ 1  1  1  1 -1 -1| 1  1 -1  1 -1 -1]
[ 1 -1  1  1  1 -1| 1 -1  1 -1  1 -1]
[ 1 -1 -1  1  1  1| 1 -1 -1  1 -1  1]
[ 1  1 -1 -1  1  1| 1  1 -1 -1  1 -1]
[-----------------+-----------------]
[-1  1  1  1  1  1|-1 -1 -1 -1 -1 -1]
[ 1 -1  1 -1 -1  1|-1 -1 -1  1  1 -1]
[ 1  1 -1  1 -1 -1|-1 -1 -1 -1  1  1]
[ 1 -1  1 -1  1 -1|-1  1 -1 -1 -1  1]
[ 1 -1 -1  1 -1  1|-1  1  1 -1 -1 -1]
[ 1  1 -1 -1  1 -1|-1 -1  1  1 -1 -1]

So, to get the ball rolling, should there be a new method called normalised_hadamard_matrix or should we let the method hadamard_matrix take an optional argument like normalised=True or sth like that?

Any suggestions would be welcome.

[nathanncohen]

comment:8

Yooooooooo !!

So, to get the ball rolling, should there be a new method called normalised_hadamard_matrix or should we let the method hadamard_matrix take an optional argument like normalised=True or sth like that?

Your idea is cool ! I would vote for the optional argument. Though it does not make a lot of sense to set it to "True" by default... So perhaps we can also normalize them automatically before returning them ?

Nathann

[KPanComputes]

comment:9

Replying to @nathanncohen:

Your idea is cool ! I would vote for the optional argument. Though it does not make a lot of sense to set it to "True" by default... So perhaps we can also normalize them automatically before returning them ?

May be not, because, this is going to take 2n steps for a Hadamard Matrix of order n. And, for many purposes, this is not necessary. So, may be we can have an optional argument and set it to False instead.

Do you agree?

[nathanncohen]

comment:10

Ahahahah. Okay, as you want. But I do not think these 2n steps will make a difference in any code. Are you sure that creating the matrix takes a linear time ? Or may Python reallocate a partial matrix several times ? Either way is fine !

Nathann

[KPanComputes]

Changed commit from bfba495 to 44b777a

[KPanComputes]

Changed branch from u/knsam/16327 to u/knsam/16237

[KPanComputes]

Author: Kannappan Sampath

[KPanComputes]

New commits:

44b777a

trac #16237: Indexing in IncidenceStructureFromMatrix method fixed. minor clean-up of Hadamard matrices; they are now normalised.

[KPanComputes]

comment:12

Indeed, the bug that motivated my search is now fixed; with the patch, we have:

sage: D = designs.HadamardDesign(11); N = D.incidence_matrix()
sage: J = matrix(ZZ, 11, 11, [1]*11*11); N*J
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]

[nathanncohen]

comment:13

Hello !

Several remarks:

1. I do not think you should change the definition of the Paley matrices... I believe they are well-defined, and if you want a normalized version of them you should not change their definition but rather normalize them when you need them. At the very least, you could have an optional argument "normalize" set to False by default in these functions.

2. You seem to use twice the code to normalize a matrix. I guess the best would be to write a function that does that, as it can be useful later, and also useful to the users.

3. There may be a smart way to test if a element of a field is a quadratic residue, but if you need to enumerate all of them anyway you could begin by computing the square of all elements of the field, then decide if each element is a square by testing if it belongs to that list ?...

Nathann

[KPanComputes]

comment:15

Replying to @nathanncohen:

Hello !

Several remarks:

1. I do not think you should change the definition of the Paley matrices... I believe they are well-defined, and if you want a normalized version of them you should not change their definition but rather normalize them when you need them. At the very least, you could have an optional argument "normalize" set to False by default in these functions.

No, I have modified only so much as to remove the edge cases that do not arise. I am not really changing the definition of Paley matrices. There are several floating around in the Literature. I have chosen Horadam's Paley Type I, Type II (I think!). But, this is not standard at all! We could probably have this put explicitly in the documentation. And, this document is not included in the combinat docs! Should we try to add it ? :-)

2. You seem to use twice the code to normalize a matrix. I guess the best would be to write a function that does that, as it can be useful later, and also useful to the users.

Good suggestion, I will implement it!

3. There may be a smart way to test if a element of a field is a quadratic residue, but if you need to enumerate all of them anyway you could begin by computing the square of all elements of the field, then decide if each element is a square by testing if it belongs to that list ?...

There are several faster ways to do this! I am planning on implementing this in a later ticket! But, for now, it shall be a TODO notice!

Kannappan.

[sagetrac-git]

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

c496ba6

trac #16237: Indexing in IncidenceStructureFromMatrix method fixed. minor clean-up of Hadamard matrices; they are now normalised.

[sagetrac-git]

Changed commit from 44b777a to c496ba6

[nathanncohen]

comment:17

Hello Kannappan !!!

Okayokayokayokay, so you implement more or less Horadam's construction with a couple of changes of signs. Okay. It would be nice to clean this file a bit in the future, because right now there is a "return 0" in functions who claim to return entries of Hadamard matrices :-P

Anyway. I agree with what your branch does, and I added a reviewer's commit in public/16237 to fix a couple of typoes.

1. The first line of the documentation of a function should be a one-line description of what it does

2. Some people complain where a line ends with spaces ("trailing whitespaces")

3. Some people complain (the same) when the lines are longer than 80 characters.

4. Some people fight over american/english spelling (but as I never remember which ones, I did nothing about that :-P

Sooooooooo well.

If you agree with my changes, you can either :

1. Add my commit to your branch

2. Change the branch to public/16237 (remember that you are the only one with writing access to u/knsam/* branches and that everybody can write to public/* branches

About the doc : it seems to be included already http://www.sagemath.org/doc/reference/combinat/sage/combinat/matrices/hadamard_matrix.html

HMmmmmmm... Okay, nothing else to say. Good work !

Nathann

P.S. : The custom is the following : usually, the reviewer sets the ticket to positive_review, but in this case I added a commit with small modifications. So if you agree with what it does, you can set the ticket to positive_review yourself, as you reviewed my changes and I reviewed yours. And if you do not like something in my commits, the custom is to discuss it and fight to the death.

[nathanncohen]

Reviewer: Nathann Cohen

[KPanComputes]

comment:20

Hi Nathann,

I have set this ticket to positive review, as we discussed!

Kannappan.

[nathanncohen]

comment:21

Okayyyyyyyyyy... Well, in this context it is better to add a commit rather than rewrite the last one. Because this way the reviewer can easily see what exactly you changed since the previous commit. If I want to do it now, I have to re-read the whole branch again and try to find out if everything is there :-P

Nathann

[KPanComputes]

comment:22

Sorry about it, I will do it from the next time!

Kannappan.

[vbraun]

comment:24

Documentation does not build

[nathanncohen]

Changed branch from u/knsam/16237 to public/16237

[nathanncohen]

Changed commit from 5602e14 to dd26230

[nathanncohen]

comment:25

Fixed.

---

New commits:

82ec7cf	trac #16237: Merged with 6.2
dd26230	trac #16237: Useless ::

[vbraun]

Work Issues: make doc-pdf

[vbraun]

comment:26

docbuild fails

[sagetrac-git]

Changed commit from dd26230 to e2eab09

[sagetrac-git]

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

5f92753	trac #16237: Merged with 6.3.beta0
e2eab09	trac #16237: Typos

[nathanncohen]

comment:28

Fixed.

[vbraun]

Changed work issues from make doc-pdf to none

[vbraun]

Changed branch from public/16237 to e2eab09