Opened 7 years ago
Closed 7 years ago
#16237 closed defect (fixed)
IncidenceStructureFromMatrix bug
Reported by:  knsam  Owned by:  

Priority:  major  Milestone:  sage6.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 iftesting in the method.
Change History (30)
comment:1 Changed 7 years ago by
comment:2 Changed 7 years ago by
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. :)
comment:3 Changed 7 years ago by
You can ask on sagedevel 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
 Branch set to u/knsam/16327
 Commit set to c30180a63e36bdac91bc2e6dccab33cb9cc75d3d
New commits:
c30180a  trac #16327: Indexing in IncidenceStructureFromMatrix method fixed.

comment:5 Changed 7 years ago by
 Commit changed from c30180a63e36bdac91bc2e6dccab33cb9cc75d3d to bfba495df27bacef7a0bc2632b5000e9f09ebd87
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
bfba495  trac #16237: Indexing in IncidenceStructureFromMatrix method fixed.

comment:6 Changed 7 years ago by
 Type changed from PLEASE CHANGE to defect
comment:7 followup: ↓ 8 Changed 7 years ago by
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 all1 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 11 1 1 1 1 1] [ 1 1 1 1 1 1 1 1 1 1 1 1] [ 1 1 1 1 1 1 1 1 1 1 1 1] [ 1 1 1 1 1 1 1 1 1 1 1 1] [ 1 1 1 1 1 1 1 1 1 1 1 1] [ 1 1 1 1 1 1 1 1 1 1 1 1] [+] [1 1 1 1 1 11 1 1 1 1 1] [ 1 1 1 1 1 11 1 1 1 1 1] [ 1 1 1 1 1 11 1 1 1 1 1] [ 1 1 1 1 1 11 1 1 1 1 1] [ 1 1 1 1 1 11 1 1 1 1 1] [ 1 1 1 1 1 11 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 ; followup: ↓ 9 Changed 7 years ago by
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
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
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
 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:
44b777a  trac #16237: Indexing in IncidenceStructureFromMatrix method fixed. minor cleanup of Hadamard matrices; they are now normalised.

comment:12 Changed 7 years ago by
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 followup: ↓ 15 Changed 7 years ago by
Hello !
Several remarks:
1) I do not think you should change the definition of the Paley matrices... I believe they are welldefined, 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
 Status changed from needs_review to needs_info
comment:15 in reply to: ↑ 13 Changed 7 years ago by
Replying to ncohen:
Hello !
Several remarks:
1) I do not think you should change the definition of the Paley matrices... I believe they are welldefined, 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.
comment:16 Changed 7 years ago by
 Commit changed from 44b777a634ee082e1e6f1970d89eac4a2ee67e89 to c496ba610a37e545466746a1177bd95c16f6c069
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 cleanup of Hadamard matrices; they are now normalised.

comment:17 Changed 7 years ago by
 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 oneline 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
 Commit changed from c496ba610a37e545466746a1177bd95c16f6c069 to 5602e14187bf45504a59c9aa9906a02c9bc84202
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
5602e14  trac #16237: Indexing in IncidenceStructureFromMatrix method fixed. minor cleanup of Hadamard matrices; they are now normalised.

comment:19 Changed 7 years ago by
 Status changed from needs_info to positive_review
comment:20 Changed 7 years ago by
Hi Nathann,
I have set this ticket to positive review, as we discussed!
Kannappan.
comment:21 Changed 7 years ago by
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 reread the whole branch again and try to find out if everything is there :P
Nathann
comment:22 Changed 7 years ago by
Sorry about it, I will do it from the next time!
Kannappan.
comment:23 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:24 Changed 7 years ago by
 Status changed from positive_review to needs_work
Documentation does not build
comment:25 Changed 7 years ago by
 Branch changed from u/knsam/16237 to public/16237
 Commit changed from 5602e14187bf45504a59c9aa9906a02c9bc84202 to dd2623089c83761a2e6b5a57bfb221031fae467c
 Status changed from needs_work to positive_review
comment:26 Changed 7 years ago by
 Status changed from positive_review to needs_work
 Work issues set to make docpdf
docbuild fails
comment:27 Changed 7 years ago by
 Commit changed from dd2623089c83761a2e6b5a57bfb221031fae467c to e2eab093653fabc375d5055aa98ec2869ff363ab
comment:29 Changed 7 years ago by
 Work issues make docpdf deleted
comment:30 Changed 7 years ago by
 Branch changed from public/16237 to e2eab093653fabc375d5055aa98ec2869ff363ab
 Resolution set to fixed
 Status changed from positive_review to closed
Are you working on fixing it ?
Nathann