Latroids and their representation by codes over modules

Author:
Dirk Vertigan

Journal:
Trans. Amer. Math. Soc. **356** (2004), 3841-3868

MSC (2000):
Primary 05B35; Secondary 94B05, 16D90

Published electronically:
July 24, 2003

MathSciNet review:
2058508

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**1.**Frank W. Anderson and Kent R. Fuller,*Rings and categories of modules*, Springer-Verlag, New York-Heidelberg, 1974. Graduate Texts in Mathematics, Vol. 13. MR**0417223****2.**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****3.**Thomas H. Brylawski,*A decomposition for combinatorial geometries*, Trans. Amer. Math. Soc.**171**(1972), 235–282. MR**0309764**, 10.1090/S0002-9947-1972-0309764-6**4.**Jilyana Cazaran, Keisuke Shiromoto, Thomas Britz, and Carrie Rutherford, 1999-2002, Independent Private Communication.**5.**Henry H. Crapo,*The Tutte polynomial*, Aequationes Math.**3**(1969), 211–229. MR**0262095****6.**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****7.**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****8.**Curtis Greene,*Weight enumeration and the geometry of linear codes*, Studies in Appl. Math.**55**(1976), no. 2, 119–128. MR**0447020****9.**A. Roger Hammons Jr., P. Vijay Kumar, A. R. Calderbank, N. J. A. Sloane, and Patrick Solé,*The 𝑍₄-linearity of Kerdock, Preparata, Goethals, and related codes*, IEEE Trans. Inform. Theory**40**(1994), no. 2, 301–319. MR**1294046**, 10.1109/18.312154**10.**Thomas Honold,*Characterization of finite Frobenius rings*, Arch. Math. (Basel)**76**(2001), no. 6, 406–415. MR**1831096**, 10.1007/PL00000451**11.**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****12.**F. J. MacWilliams,*A theorem on the distribution of weights in a systematic code*, Bell System Tech. J.**42**(1963), 79-94.**13.**F. J. MacWilliams and N. J. A. Sloane,*The theory of error-correcting codes. I*, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. North-Holland Mathematical Library, Vol. 16. MR**0465509****14.**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**, 10.1515/dma.1991.1.4.365**15.**L. Pontrjagin,*Topological Groups*, Princeton Mathematical Series, v. 2, Princeton University Press, Princeton, 1939. Translated from the Russian by Emma Lehmer. MR**0000265****16.**Charles Semple and Geoff Whittle,*Partial fields and matroid representation*, Adv. in Appl. Math.**17**(1996), no. 2, 184–208. MR**1390574**, 10.1006/aama.1996.0010**17.**Anne Penfold Street and W. D. Wallis,*Combinatorial theory: an introduction*, Charles Babbage Research Centre, Winnipeg, Man., 1977. MR**0444480****18.**W. T. Tutte,*A ring in graph theory*, Proc. Cambridge Philos. Soc.**43**(1947), 26–40. MR**0018406****19.**D. J. A. Welsh,*Matroid theory*, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. MR**0427112****20.**Geoff Whittle,*A characterisation of the matroids representable over 𝐺𝐹(3) and the rationals*, J. Combin. Theory Ser. B**65**(1995), no. 2, 222–261. MR**1358987**, 10.1006/jctb.1995.1052**21.**Geoff Whittle,*On matroids representable over 𝐺𝐹(3) and other fields*, Trans. Amer. Math. Soc.**349**(1997), no. 2, 579–603. MR**1407504**, 10.1090/S0002-9947-97-01893-X**22.**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**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
05B35,
94B05,
16D90

Retrieve articles in all journals with MSC (2000): 05B35, 94B05, 16D90

Additional Information

**Dirk Vertigan**

Affiliation:
Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803-4918

Email:
vertigan@math.lsu.edu

DOI:
http://dx.doi.org/10.1090/S0002-9947-03-03367-1

Keywords:
Linear code,
ring,
Artinian ring,
finite ring,
module,
matroid,
polymatroid,
latroid,
minor,
minor class,
duality,
Morita duality,
weight enumerator,
Tutte polynomial,
generating function,
MacWilliams identity

Received by editor(s):
July 15, 2002

Received by editor(s) in revised form:
April 3, 2003

Published electronically:
July 24, 2003

Additional Notes:
The author’s research was partially supported by the National Security Agency, grant number MDA904-01-0014

Dedicated:
Dedicated in memory of William T. Tutte, 1917-2002

Article copyright:
© Copyright 2003
American Mathematical Society