Self-orthogonal codes from orbit matrices of Seidel and Laplacian matrices of strongly regular graphs

Dean Crnković; Ronan Egan; Andrea Švob

doi:10.3934/amc.2020032

Article Contents

2020, Volume 14, Issue 4: 591-602. Doi: 10.3934/amc.2020032

This issue Previous Article New classes of strictly optimal low hit zone frequency hopping sequence sets Next Article Designs from maximal subgroups and conjugacy classes of Ree groups

Self-orthogonal codes from orbit matrices of Seidel and Laplacian matrices of strongly regular graphs

1.
Department of Mathematics, University of Rijeka, Croatia
2.
De Brún Centre for Mathematics, School of Mathematics, Statistics and Applied Mathematics, National University of Ireland, Galway

^* Corresponding author: A. Švob
^* Corresponding author: A. Švob

Received: April 2018

Revised: April 2019

Early access: November 2019

Published: November 2020

D. Crnković and A. Švob were supported by Croatian Science Foundation under the project 6732. R. Egan was supported by the Irish Research Council (Government of Ireland Postdoctoral Fellowship, GOIPD/2018/304)

Abstract / Introduction Full Text(HTML) Figure(0) / Table(9) Related Papers Cited by

Abstract

In this paper we introduce the notion of orbit matrices of integer matrices such as Seidel and Laplacian matrices of some strongly regular graphs with respect to their permutation automorphism groups. We further show that under certain conditions these orbit matrices yield self-orthogonal codes over finite fields $ \mathbb{F}_q $, where $ q $ is a prime power and over finite rings $ \mathbb{Z}_m $. As a case study, we construct codes from orbit matrices of Seidel, Laplacian and signless Laplacian matrices of strongly regular graphs. In particular, we construct self-orthogonal codes from orbit matrices of Seidel and Laplacian matrices of the Higman-Sims and McLaughlin graphs.

Keywords:

Mathematics Subject Classification: Primary: 05E30, 94B05; Secondary: 05E18.

Citation:

Full Text(HTML)

Table 1. Self-orthogonal codes constructed from Seidel matrices of SRGs

Graph	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ \mathcal{G}_1^1 $	$ [10,4,6]_3* $	$ [10,6,4]_3* $	2880
$ \mathcal{G}_2^1 $	$ [26,11,8]_5 $	$ [26,15,6]_5 $	576
$ \mathcal{G}_2^3 $	$ [26,12,8]_5 $	$ [26,14,6]_5 $	48
$ \mathcal{G}_2^6 $	$ [26,12,8]_5 $	$ [26,14,6]_5 $	312
$ \mathcal{G}_2^8 $	$ [26,9,14]_5* $	$ [28,17,6]_5 $	124800
$ \mathcal{G}_3^1 $	$ [28,7,12]_3 $	$ [28,21,4]_3* $	$ 2^{10}\cdot 3^4\cdot 5^1 \cdot 7^1 $

| Show Table

DownLoad: CSV

Table 2. Self-orthogonal codes constructed from orbit matrices of the Seidel matrix of $ \mathcal{G}_1 $

$ G \leq \mathrm{Aut}({\mathcal{G}_{1}}) $	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ Z_3 $	$ [69,21,15]_3 $	$ [69,48,5]_3 $	80
$ Z_{13} $	$ [16,4,9]_3* $	$ [16,12,1]_3 $	2880

| Show Table

DownLoad: CSV

Table 3. Self-orthogonal codes constructed from orbit matrices of the Seidel matrix of $ \mathcal{G}_2 $

$ G \leq \mathrm{Aut}({\mathcal{G}_{2}}) $	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ Z_3 $	$ [10,4,6]_3* $	$ [10,6,4]_3* $	2880
$ Z_3 $	$ [36,14,12]_3 $	$ [36,22,6]_3 $	2903040
$ Z_3 $	$ [28,7,12]_3 $	$ [28,21,4]_3* $	2903040
$ Z_3 $	$ [42,15,12]_3 $	$ [42,27,4]_3 $	17280
$ Z_3 $	$ [45,15,12]_3 $	$ [45,30,4]_3 $	5184
$ Z_{17} $	$ [8,2,6]_3* $	$ [8,6,2]_3* $	768

| Show Table

DownLoad: CSV

Table 4. Self-orthogonal codes constructed from orbit matrices of the Laplacian matrix of $ \mathcal{G}_3 $

$ G \leq \mathrm{Aut}({\mathcal{G}_{3}}) $	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ Z_3 $	$ [12,2,3]_3 $	$ [12,10,2]_3* $	$ 2^{10}\cdot 3^5\cdot 5\cdot 7 $
$ Z_3 $	$ [15,5,6]_3 $	$ [15,10,3]_3 $	10
$ Z_3 $	$ [40,10,18]_3 $	$ [40,30,4]_3 $	$ 2^9\cdot 3^6\cdot 5\cdot 13 $
$ Z_3 $	$ [45,15,12]_3 $	$ [45,30,6]_3 $	103680
$ Z_3 $	$ [51,13,12]_3 $	$ [51,38,4]_3 $	10368
$ Z_3 $	$ [52,13,12]_3 $	$ [52,39,3]_3 $	5184
$ Z_3 $	$ [53,14,12]_3 $	$ [53,39,4]_3 $	864
$ Z_5 $	$ [33,9,12]_3 $	$ [33,24,2]_3 $	96

| Show Table

DownLoad: CSV

Table 5. Self-orthogonal codes constructed from orbit matrices of Laplace matrix of $ \mathcal{G}_4 $

$ G \leq \mathrm{Aut}({\mathcal{G}_{4}}) $	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ Z_2 $	$ [12,2,6]_2 $	$ [12,10,2]_2* $	1036800
$ Z_2 $	$ [14,7,4]_2* $	$ [14,7,4]_2* $	56448
$ Z_2 $	$ [40,14,8]_2 $	$ [40,26,4]_2 $	3932160
$ Z_2 $	$ [120,24,24]_2 $	$ [120,96,5]_2 $	1920
$ Z_2 $	$ [133,27,24]_2 $	$ [133,106,6]_2 $	336
$ Z_2 $	$ [134,30,24]_2 $	$ [134,104,5]_2 $	240
$ Z_4 $	$ [16,6,6]_2* $	$ [16,10,4]_2* $	11520
$ Z_4 $	$ [18,3,6]_2 $	$ [18,15,2]_2* $	$ 2^{13}\cdot 3^{7}\cdot 5^3 $
$ Z_4 $	$ [18,4,8]_2* $	$ [18,14,2]_2* $	36864
$ Z_4 $	$ [36,6,8]_2 $	$ [36,30,2]_2 $	$ 2^{31}\cdot 3^{13} $
$ Z_4 $	$ [48,8,16_2 $	$ [48,40,4]_2* $	69120
$ Z_4 $	$ [60,12,12]_2 $	$ [60,48,4]_2 $	49152
$ Z_4 $	$ [61,13,16]_2 $	$ [61,48,4]_2 $	17280
$ Z_5 $	$ [56,10,16]_2 $	$ [56,46,2]_2 $	1440
$ Z_7 $	$ [40,8,8]_2 $	$ [40,32,2]_2 $	393216
$ Z_7 $	$ [40,6,14]_5 $	$ [40,34,2]_5 $	3072
$ Z_5 $	$ [56,8,20]_5 $	$ [56,48,2]_5 $	115200
$ Z_5 $	$ [54,8,20]_5 $	$ [56,48,2]_5 $	91729428480

| Show Table

DownLoad: CSV

Table 6. Self-orthogonal codes constructed from orbit matrices of the signless Laplacian matrix of $ \mathcal{G}_5 $

$ G \leq \mathrm{Aut}({\mathcal{G}_{5}}) $	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ Z_2 $	$ [16,3,8]_2* $	$ [16,13,2]_2* $	$ 2^{15}\cdot 3^5 $
$ Z_2 $	$ [32,5,16]_2* $	$ [32,27,2]_2* $	$ 2^{26}\cdot 3^2\cdot 5^1\cdot 7^1 $
$ Z_2 $	$ [40,5,16]_2 $	$ [40,35,2]_2* $	$ 2^{34}\cdot 3^{12}\cdot 5^1 $
$ Z_2 $	$ [60,3,32]_2 $	$ [60,57,2]_2 $	$ 2^{55}\cdot 3^{18}\cdot 5^8\cdot 7^7\cdot 11^1 $
$ Z_2 $	$ [64,4,32]_2* $	$ [64,60,2]_2* $	$ 2^{55}\cdot 3^{17}\cdot 5^1\cdot 7^2 $
$ Z_2 $	$ [64,7,32]_2* $	$ [64,57,4]_2* $	$ 2^{21}\cdot 3^4\cdot 5^1\cdot 7^2\cdot 31^1 $

| Show Table

DownLoad: CSV

Table 7. Self-orthogonal codes constructed from orbit matrices of the Seidel matrix of $ \mathcal{G}_6 $

$ G \leq \mathrm{Aut}({\mathcal{G}_{6}}) $	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ Z_5 $	$ [19,4,10]_5 $	$ [19,15,2]_5 $	1920
$ Z_5 $	$ [20,3,10]_5 $	$ [20,17,2]_5 $	$ 2^{17}\cdot 3^5\cdot 5^4 $
$ Z_5 $	$ [20,4,14]_5* $	$ [20,16,4]_5* $	960

| Show Table

DownLoad: CSV

Table 8. Self-orthogonal codes constructed from orbit matrices of the Laplacian matrix of $ \mathcal{G}_7 $

$ G \leq \mathrm{Aut}({\mathcal{G}_{7}}) $	$ C $	$ \mathrm{Dual}(C) $	$ \|\mathrm{Aut}(C)\| $
$ Z_5 $	$ [54,4,20]_5 $	$ [54,50,2]_5 $	$ 2^{24}\cdot 3^{7}\cdot 5^{1} $
$ Z_5 $	$ [55,3,20]_5 $	$ [55,52,2]_5* $	$ 2^{44}\cdot 3^{17}\cdot 5^{12}\cdot 7^3\cdot 11^2 \cdot 13\cdot 17\cdot 19\cdot 23 $

| Show Table

DownLoad: CSV

Table 9. Self-dual codes over $ \mathbb{Z}_4 $ constructed from orbit matrices of signless Laplacian matrices of SRGs $ \mathcal{G}_5 $ and $ \mathcal{G}_8 $

Graph	$ C $	$ d_H(C) $, $ d_E(C) $, $ d_L(C) $	Type
$ \mathcal{G}_5 $	$ ((8,4^1 2^{6})) $	2, 8, 4	Ⅱ
$ \mathcal{G}_5 $	$ ((16,4^3 2^{10})) $	2, 8, 4	Ⅱ
$ \mathcal{G}_5 $	$ ((32,4^5 2^{22})) $	2, 8, 4	Ⅱ
$ \mathcal{G}_5 $	$ ((36,4^1 2^{34})) $	2, 8, 4	Ⅰ
$ \mathcal{G}_5 $	$ ((40,4^5 2^{30})) $	2, 8, 4	Ⅱ
$ \mathcal{G}_8 $	$ ((24,4^1 2^{22})) $	2, 8, 4	Ⅱ
$ \mathcal{G}_8 $	$ ((24,4^5 2^{14})) $	2, 8, 4	Ⅱ
$ \mathcal{G}_8 $	$ ((28,4^1 2^{26})) $	2, 8, 4	Ⅰ
$ \mathcal{G}_8 $	$ ((30,4^0 2^{30})) $	1, 4, 2	Ⅰ

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Behbahani and C. Lam, Strongly regular graphs with non-trivial automorphisms, Discrete Math., 311 (2011), 132-144. doi: 10.1016/j.disc.2010.10.005.
[2]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system Ⅰ: The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[3]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Results in Mathematics and Related Areas, 18, Springer-Verlag, Berlin, 1989. doi: 10.1007/978-3-642-74341-2.
[4]	A. E. Brouwer, Strongly regular graphs, in Handbook of Combinatorial Designs, Chapman & Hall/CRC, Boca Raton, FL, 2007,852-868.
[5]	A. E. Brouwer, Parameters of strongly regular graphs, Available from: http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html.
[6]	A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012. doi: 10.1007/978-1-4614-1939-6.
[7]	D. Crnković, R. Egan and A. Švob, Orbit matrices of Hadamard matrices and related codes, Discrete Math., 341 (2018), 1199-1209. doi: 10.1016/j.disc.2018.01.018.
[8]	D. Crnković, M. Maksimović, B. G. Rodrigues and S. Rukavina, Self-orthogonal codes from the strongly regular graphs on up to 40 vertices, Adv. Math. Commun., 10 (2016), 555-582. doi: 10.3934/amc.2016026.
[9]	D. Crnković, B. G. Rodrigues, S. Rukavina and L. Simčić, Self-orthogonal codes from orbit matrices of 2-designs, Adv. Math. Commun., 7 (2013), 161-174. doi: 10.3934/amc.2013.7.161.
[10]	S. T. Dougherty, Algebraic Coding Theory Over Finite Commutative Rings, SpringerBriefs in Mathematics, Springer, Cham, 2017. doi: 10.1007/978-3-319-59806-2.
[11]	M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Available from: http://www.codetables.de.
[12]	W. H. Haemers, R. Peeters and J. M. van Rijckevorsel, Binary codes of strongly regular graphs, Des. Codes Cryptogr., 17 (1999), 187-209. doi: 10.1023/A:1026479210284.
[13]	W. H. Haemers and E. Spence, Enumeration of cospectral graphs, European J. Combin., 25 (2004), 199-211. doi: 10.1016/S0195-6698(03)00100-8.
[14]	M. Harada, Note on the residue codes of self-dual $\mathbb{Z}_4$-codes having large minimum Lee weights, Adv. Math. Commun., 10 (2016), 695-706. doi: 10.3934/amc.2016035.
[15]	M. Harada and V. Tonchev, Self-orthogonal codes from symmetric designs with fixed-point-free automorphisms, Discrete Math., 264 (2003), 81-90. doi: 10.1016/S0012-365X(02)00553-8.
[16]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003. doi: 10.1017/CBO9780511807077.
[17]	J. D. Key, T. P. McDonough and V. C. Mavron, Improved partial permutation decoding for Reed-Muller codes, Discrete Math., 340 (2017), 722-728. doi: 10.1016/j.disc.2016.11.031.
[18]	F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505. doi: 10.1002/j.1538-7305.1964.tb04075.x.
[19]	E. Spence, Strongly regular graphs on at most 64 vertices, Available from: http://www.maths.gla.ac.uk/~es/srgraphs.php.
[20]	F. Szöllősi and P. R. J. Östergård, Enumeration of Seidel matrices, European J. Combin., 69 (2018), 169-184. doi: 10.1016/j.ejc.2017.10.009.
[21]	V. D. Tonchev, Combinatorial Configurations: Designs, Codes, Graphs, Pitman Monographs and Surveys in Pure and Applied Mathematics, 40, John Wiley & Sons, Inc., New York, 1988.