Latroids and their representation by codes over modules

Vertigan, Dirk

doi:10.1090/S0002-9947-03-03367-1

Latroids and their representation by codes over modules
HTML articles powered by AMS MathViewer

by Dirk Vertigan PDF

Trans. Amer. Math. Soc. 356 (2004), 3841-3868 Request permission

Abstract:

It has been known for some time that there is a connection between linear codes over fields and matroids represented over fields. In fact a generator matrix for a linear code over a field is also a representation of a matroid over that field. There are intimately related operations of deletion, contraction, minors and duality on both the code and the matroid. The weight enumerator of the code is an evaluation of the Tutte polynomial of the matroid, and a standard identity relating the Tutte polynomials of dual matroids gives rise to a MacWilliams identity relating the weight enumerators of dual codes. More recently, codes over rings and modules have been considered, and MacWilliams type identities have been found in certain cases. In this paper we consider codes over rings and modules with code duality based on a Morita duality of categories of modules. To these we associate latroids, defined here. We generalize notions of deletion, contraction, minors and duality, on both codes and latroids, and examine all natural relations among these. We define generating functions associated with codes and latroids, and prove identities relating them, generalizing above-mentioned generating functions and identities.

References

Frank W. Anderson and Kent R. Fuller, Rings and categories of modules, Graduate Texts in Mathematics, Vol. 13, Springer-Verlag, New York-Heidelberg, 1974. MR 0417223, DOI 10.1007/978-1-4684-9913-1
T. S. Blyth, Module theory, 2nd ed., Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1990. An approach to linear algebra. MR 1070710
Thomas H. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235–282. MR 309764, DOI 10.1090/S0002-9947-1972-0309764-6
Jilyana Cazaran, Keisuke Shiromoto, Thomas Britz, and Carrie Rutherford, 1999–2002, Independent Private Communication.
Henry H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969), 211–229. MR 262095, DOI 10.1007/BF01817442
Henry H. Crapo and Gian-Carlo Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR 0290980
T. A. Dowling, Codes, packings and the critical problem, Atti del Convegno di Geometria Combinatoria e sue Applicazioni (Univ. Perugia, Perugia, 1970) Ist. Mat., Univ. Perugia, Perugia, 1971, pp. 209–224. MR 0337669
Curtis Greene, Weight enumeration and the geometry of linear codes, Studies in Appl. Math. 55 (1976), no. 2, 119–128. MR 447020, DOI 10.1002/sapm1976552119
A. Roger Hammons Jr., P. Vijay Kumar, A. R. Calderbank, N. J. A. Sloane, and Patrick Solé, The $\textbf {Z}_4$-linearity of Kerdock, Preparata, Goethals, and related codes, IEEE Trans. Inform. Theory 40 (1994), no. 2, 301–319. MR 1294046, DOI 10.1109/18.312154
Thomas Honold, Characterization of finite Frobenius rings, Arch. Math. (Basel) 76 (2001), no. 6, 406–415. MR 1831096, DOI 10.1007/PL00000451
A. S. Kuz′min, V. L. Kurakin, V. T. Markov, A. V. Mikhalev, and A. A. Nechaev, Codes and recurrences over finite rings and modules, Vestnik Moskov. Univ. Ser. I Mat. Mekh. 5 (1999), 18–31, 80 (Russian, with Russian summary); English transl., Moscow Univ. Math. Bull. 54 (1999), no. 5, 15–28 (2000). MR 1735214
F. J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Tech. J. 42 (1963), 79–94.
F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Mathematical Library, Vol. 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR 0465509
A. A. Nechaev, Kerdock’s code in cyclic form, Diskret. Mat. 1 (1989), no. 4, 123–139 (Russian); English transl., Discrete Math. Appl. 1 (1991), no. 4, 365–384. MR 1041691, DOI 10.1515/dma.1991.1.4.365
T. Venkatarayudu, The $7$-$15$ problem, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 531. MR 0000001, DOI 10.1090/gsm/058
Charles Semple and Geoff Whittle, Partial fields and matroid representation, Adv. in Appl. Math. 17 (1996), no. 2, 184–208. MR 1390574, DOI 10.1006/aama.1996.0010
Anne Penfold Street and W. D. Wallis, Combinatorial theory: an introduction, Charles Babbage Research Centre, Winnipeg, Man., 1977. MR 0444480
A. R. Collar, On the reciprocation of certain matrices, Proc. Roy. Soc. Edinburgh 59 (1939), 195–206. MR 8, DOI 10.1017/S0370164600012281
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
Geoff Whittle, A characterisation of the matroids representable over $\textrm {GF}(3)$ and the rationals, J. Combin. Theory Ser. B 65 (1995), no. 2, 222–261. MR 1358987, DOI 10.1006/jctb.1995.1052
Geoff Whittle, On matroids representable over $\textrm {GF}(3)$ and other fields, Trans. Amer. Math. Soc. 349 (1997), no. 2, 579–603. MR 1407504, DOI 10.1090/S0002-9947-97-01893-X
Jay A. Wood, Duality for modules over finite rings and applications to coding theory, Amer. J. Math. 121 (1999), no. 3, 555–575. MR 1738408, DOI 10.1353/ajm.1999.0024