[math-fun] Golay code question
On wikipedia, it's claimed that this generator matrix for the Golay code is given by the identity matrix and the complement of the vertex adjacency graph of the icosahedron. https://commons.wikimedia.org/wiki/File:BinaryGolayCode.svg However, I haven't been able to figure out a labeling of vertices that actually makes it work. In fact, it looks as though this construction starts with a cyclic 10x10 matrix and then adds two parity bits (which isn't to say it can't be done). I can label the vertices however I want and get an adjacency matrix for that labeling; is there a way to figure out the permutation given the two matrices? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
If you look at MacWilliams and Sloane Theory of Error-Correcting Codes 1977 you will find several generator matrices for G_24 One of the simplest is to take an identity matrix of size 12 next to a 12X12 circulant matrix with first row 110111101000 Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Dec 17, 2015 at 10:03 AM, Mike Stay <metaweta@gmail.com> wrote:
On wikipedia, it's claimed that this generator matrix for the Golay code is given by the identity matrix and the complement of the vertex adjacency graph of the icosahedron. https://commons.wikimedia.org/wiki/File:BinaryGolayCode.svg
However, I haven't been able to figure out a labeling of vertices that actually makes it work. In fact, it looks as though this construction starts with a cyclic 10x10 matrix and then adds two parity bits (which isn't to say it can't be done).
I can label the vertices however I want and get an adjacency matrix for that labeling; is there a way to figure out the permutation given the two matrices? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks. As far as I know, every construction gives the unique 24-bit Golay code up to permutation; my question is how to derive the permutation that relates any two constructions. On Thu, Dec 17, 2015 at 7:22 AM, Neil Sloane <njasloane@gmail.com> wrote:
If you look at MacWilliams and Sloane Theory of Error-Correcting Codes 1977 you will find several generator matrices for G_24
One of the simplest is to take an identity matrix of size 12 next to a 12X12 circulant matrix with first row 110111101000
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Dec 17, 2015 at 10:03 AM, Mike Stay <metaweta@gmail.com> wrote:
On wikipedia, it's claimed that this generator matrix for the Golay code is given by the identity matrix and the complement of the vertex adjacency graph of the icosahedron. https://commons.wikimedia.org/wiki/File:BinaryGolayCode.svg
However, I haven't been able to figure out a labeling of vertices that actually makes it work. In fact, it looks as though this construction starts with a cyclic 10x10 matrix and then adds two parity bits (which isn't to say it can't be done).
I can label the vertices however I want and get an adjacency matrix for that labeling; is there a way to figure out the permutation given the two matrices? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Mike,
However, I haven't been able to figure out a labeling of vertices that actually makes it work. In fact, it looks as though this construction starts with a cyclic 10x10 matrix and then adds two parity bits (which isn't to say it can't be done).
Take a look at this diagram: https://upload.wikimedia.org/wikipedia/commons/7/77/Icosahedron_petrie.png Label the vertices of the decagon from 1 to 10 (in cyclic order), and the remaining vertices 11 and 12 (there are only two ways to do so, and precisely one of them will give the generator matrix in my* illustration). * Sorry about not responding to your comment on my talk page; I wasn't logged into Wikipedia at the time and subsequently forgot about it.
I can label the vertices however I want and get an adjacency matrix for that labeling; is there a way to figure out the permutation given the two matrices?
Yes! https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ Best wishes, Adam P. Goucher
Thank you very much! On Thu, Dec 17, 2015 at 2:49 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Mike,
However, I haven't been able to figure out a labeling of vertices that actually makes it work. In fact, it looks as though this construction starts with a cyclic 10x10 matrix and then adds two parity bits (which isn't to say it can't be done).
Take a look at this diagram:
https://upload.wikimedia.org/wikipedia/commons/7/77/Icosahedron_petrie.png
Label the vertices of the decagon from 1 to 10 (in cyclic order), and the remaining vertices 11 and 12 (there are only two ways to do so, and precisely one of them will give the generator matrix in my* illustration).
* Sorry about not responding to your comment on my talk page; I wasn't logged into Wikipedia at the time and subsequently forgot about it.
I can label the vertices however I want and get an adjacency matrix for that labeling; is there a way to figure out the permutation given the two matrices?
Yes!
https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/
Best wishes,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (3)
-
Adam P. Goucher -
Mike Stay -
Neil Sloane