Opened 7 years ago

Closed 7 years ago

#16237 closed defect (fixed)

IncidenceStructureFromMatrix bug

Reported by: knsam Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords:
Cc: ncohen Merged in:
Authors: Kannappan Sampath Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: e2eab09 (Commits) Commit: e2eab093653fabc375d5055aa98ec2869ff363ab
Dependencies: Stopgaps:

Description

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.

Change History (30)

comment:1 Changed 7 years ago by ncohen

Are you working on fixing it ?

Nathann

comment:2 Changed 7 years ago by knsam

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. :-)

Last edited 7 years ago by knsam (previous) (diff)

comment:3 Changed 7 years ago by ncohen

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

comment:4 Changed 7 years ago by knsam

  • Branch set to u/knsam/16327
  • Commit set to c30180a63e36bdac91bc2e6dccab33cb9cc75d3d

New commits:

c30180atrac #16327: Indexing in IncidenceStructureFromMatrix method fixed.

comment:5 Changed 7 years ago by git

  • Commit changed from c30180a63e36bdac91bc2e6dccab33cb9cc75d3d to bfba495df27bacef7a0bc2632b5000e9f09ebd87

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

bfba495trac #16237: Indexing in IncidenceStructureFromMatrix method fixed.

comment:6 Changed 7 years ago by knsam

  • Type changed from PLEASE CHANGE to defect

comment:7 follow-up: Changed 7 years ago by knsam

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.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by ncohen

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

comment:9 in reply to: ↑ 8 Changed 7 years ago by knsam

Replying to ncohen:

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?

comment:10 Changed 7 years ago by ncohen

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

comment:11 Changed 7 years ago by knsam

  • Authors set to Kannappan Sampath
  • Branch changed from u/knsam/16327 to u/knsam/16237
  • Commit changed from bfba495df27bacef7a0bc2632b5000e9f09ebd87 to 44b777a634ee082e1e6f1970d89eac4a2ee67e89
  • Component changed from PLEASE CHANGE to combinatorics
  • Status changed from new to needs_review

New commits:

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

comment:12 Changed 7 years ago by knsam

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]

comment:13 follow-up: Changed 7 years ago by ncohen

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

comment:14 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:15 in reply to: ↑ 13 Changed 7 years ago by knsam

Replying to ncohen:

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.

Last edited 7 years ago by knsam (previous) (diff)

comment:16 Changed 7 years ago by git

  • Commit changed from 44b777a634ee082e1e6f1970d89eac4a2ee67e89 to c496ba610a37e545466746a1177bd95c16f6c069

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

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

comment:17 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen

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.

comment:18 Changed 7 years ago by git

  • Commit changed from c496ba610a37e545466746a1177bd95c16f6c069 to 5602e14187bf45504a59c9aa9906a02c9bc84202

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

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

comment:19 Changed 7 years ago by knsam

  • Status changed from needs_info to positive_review

comment:20 Changed 7 years ago by knsam

Hi Nathann,

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

Kannappan.

comment:21 Changed 7 years ago by ncohen

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

comment:22 Changed 7 years ago by knsam

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

Kannappan.

comment:23 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:24 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

Documentation does not build

comment:25 Changed 7 years ago by ncohen

  • Branch changed from u/knsam/16237 to public/16237
  • Commit changed from 5602e14187bf45504a59c9aa9906a02c9bc84202 to dd2623089c83761a2e6b5a57bfb221031fae467c
  • Status changed from needs_work to positive_review

Fixed.


New commits:

82ec7cftrac #16237: Merged with 6.2
dd26230trac #16237: Useless ::

comment:26 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work
  • Work issues set to make doc-pdf

docbuild fails

comment:27 Changed 7 years ago by git

  • Commit changed from dd2623089c83761a2e6b5a57bfb221031fae467c to e2eab093653fabc375d5055aa98ec2869ff363ab

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

5f92753trac #16237: Merged with 6.3.beta0
e2eab09trac #16237: Typos

comment:28 Changed 7 years ago by ncohen

  • Status changed from needs_work to positive_review

Fixed.

comment:29 Changed 7 years ago by vbraun

  • Work issues make doc-pdf deleted

comment:30 Changed 7 years ago by vbraun

  • Branch changed from public/16237 to e2eab093653fabc375d5055aa98ec2869ff363ab
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.