×

Representations of torsion-free arithmetic matroids. (English) Zbl 1458.05040

Summary: We study the representability problem for torsion-free arithmetic matroids. After introducing a “strong gcd property” and a new operation called “reduction”, we describe and implement an algorithm to compute all essential representations, up to equivalence. As a consequence, we obtain an upper bound to the number of equivalence classes of representations. In order to rule out equivalent representations, we describe an efficient way to compute a normal form of integer matrices, up to left-multiplication by invertible matrices and change of sign of the columns (we call it the “signed Hermite normal form”). Finally, as an application of our algorithms, we disprove two conjectures about the poset of layers and the independence poset of a toric arrangement.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brändén, P.; Moci, L., The multivariate arithmetic Tutte polynomial, Trans. Amer. Math. Soc., 366, 10, 5523-5540 (2014), MR 3240933 · Zbl 1300.05133
[2] Callegaro, F.; Delucchi, E., The integer cohomology algebra of toric arrangements, Adv. Math., 313, 746-802 (2017), MR 3649237 · Zbl 1401.32022
[3] Callegaro, F.; Delucchi, E., Erratum to “the integer cohomology algebra of toric arrangements” (2019), arXiv preprint 1910.13836
[4] Cohen, H., (A Course in Computational Algebraic Number Theory. A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138 (1993), Springer) · Zbl 0786.11071
[5] D’Adderio, M.; Moci, L., Arithmetic matroids, the Tutte polynomial and toric arrangements, Adv. Math., 232, 335-367 (2013) · Zbl 1256.05039
[6] D’Alì, A.; Delucchi, E., Stanley-Reisner rings for symmetric simplicial complexes, \(G\)-semimatroids and abelian arrangements (2018), arXiv preprint 1804.07366
[7] De Concini, C.; Procesi, C., Topics in Hyperplane Arrangements, Polytopes and Box-Splines (2010), Springer · Zbl 1217.14001
[8] Delucchi, E.; Girard, N.; Paolini, G., Shellability of posets of labeled partitions and arrangements defined by root systems, Electron. J. Combin., 26, 4 (2019), Paper No. 4.14, 22, MR 4025418 · Zbl 1422.05108
[9] Fink, A.; Moci, L., Polyhedra and parameter spaces for matroids over valuation rings, Adv. Math., 343, 448-494 (2019), MR 3883211 · Zbl 1439.52014
[10] Le Gall, F., Powers of tensors and fast matrix multiplication, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (2014), ACM), 296-303 · Zbl 1325.65061
[11] Lenz, M., Computing the poset of layers of a toric arrangement (2017), arXiv preprint 1708.06646
[12] Lenz, M., Stanley-Reisner rings for quasi-arithmetic matroids (2017), arXiv preprint 1709.03834
[13] Lenz, M., Representations of weakly multiplicative arithmetic matroids are unique, Ann. Comb., 23, 335-346 (2019) · Zbl 1504.05053
[14] Martino, I., Face module for realizable \(\mathbb{Z} \)-matroids, Contrib. Discrete Math., 13, 2, 74-87 (2018) · Zbl 1435.05044
[15] Newman, M., (Integral Matrices. Integral Matrices, Pure and Applied Mathematics, vol. 45 (1972), Academic Press) · Zbl 0254.15009
[16] Oxley, J., (Matroid Theory. Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 21 (2011), Oxford University Press, Oxford), xiv+684, MR 2849819 · Zbl 1254.05002
[17] Pagaria, R., Combinatorics of toric arrangements, Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur., 30, 2, 317-349 (2019) · Zbl 1423.52040
[18] Pagaria, R., Two examples of toric arrangements, J. Combin. Theory Ser. A, 167, 389-402 (2019) · Zbl 1429.32044
[19] Pagaria, R., Orientable arithmetic matroids, Discrete Math., 343, 6, 111872, 8 (2020), MR 4067961 · Zbl 1437.05041
[20] Pagaria, R.; Paolini, G., Arithmat: SageMath implementation of arithmetic matroids and toric arrangements (2019)
[21] Paolini, G., Shellability of generalized Dowling posets, J. Combin. Theory Ser. A, 171, Article 105159 pp. (2020), 19. MR 4019110 · Zbl 1477.06011
[22] Storjohann, A.; Labahn, G., Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices, ISSAC 1996 (1996), ACM Press · Zbl 0915.65033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.