For integers $0 \le \ell \le k_{r} \le k_{c} \le n$, we give a description for the Smith group of the incidence matrix with rows (columns) indexed by the size $k_r$ ($k_c$, respectively) subsets of an $n$-element set, where incidence means intersection in a set of size $\ell $. This generalizes work of Wilson and Bier from the 1990s which dealt only with the case where incidence meant inclusion. Our approach also describes the Smith group of any matrix in the $\mathbb{Z}$-linear span of these matrices so includes all integer matrices in the Bose–Mesner algebra of the Johnson association scheme: for example, the association matrices themselves as well as the Laplacian, signless Laplacian, Seidel adjacency matrix, etc. of the associated graphs. In particular, we describe the critical (also known as sandpile) groups of these graphs. The complexity of our formula grows with the parameters $k_{r}$ and $k_{c}$, but is independent of $n$ and $\ell $, which often leads to an efficient algorithm for computing these groups. We illustrate our techniques to give diagonal forms of matrices attached to the Kneser and Johnson graphs for subsets of size $3$, whose invariants have never before been described, and recover results from a variety of papers in the literature in a unified way.
Revised:
Accepted:
Published online:
Ducey, Joshua E. 1; Engelthaler, Lauren 2; Gathje, Jacob 3; Jones, Brant 4; Pfaff, Isabel 5; Plute, Jenna 6
CC-BY 4.0
@article{ALCO_2025__8_1_29_0,
author = {Ducey, Joshua E. and Engelthaler, Lauren and Gathje, Jacob and Jones, Brant and Pfaff, Isabel and Plute, Jenna},
title = {Integer diagonal forms for subset intersection relations},
journal = {Algebraic Combinatorics},
pages = {29--57},
publisher = {The Combinatorics Consortium},
volume = {8},
number = {1},
year = {2025},
doi = {10.5802/alco.406},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.406/}
}
TY - JOUR AU - Ducey, Joshua E. AU - Engelthaler, Lauren AU - Gathje, Jacob AU - Jones, Brant AU - Pfaff, Isabel AU - Plute, Jenna TI - Integer diagonal forms for subset intersection relations JO - Algebraic Combinatorics PY - 2025 SP - 29 EP - 57 VL - 8 IS - 1 PB - The Combinatorics Consortium UR - https://alco.centre-mersenne.org/articles/10.5802/alco.406/ DO - 10.5802/alco.406 LA - en ID - ALCO_2025__8_1_29_0 ER -
%0 Journal Article %A Ducey, Joshua E. %A Engelthaler, Lauren %A Gathje, Jacob %A Jones, Brant %A Pfaff, Isabel %A Plute, Jenna %T Integer diagonal forms for subset intersection relations %J Algebraic Combinatorics %D 2025 %P 29-57 %V 8 %N 1 %I The Combinatorics Consortium %U https://alco.centre-mersenne.org/articles/10.5802/alco.406/ %R 10.5802/alco.406 %G en %F ALCO_2025__8_1_29_0
Ducey, Joshua E.; Engelthaler, Lauren; Gathje, Jacob; Jones, Brant; Pfaff, Isabel; Plute, Jenna. Integer diagonal forms for subset intersection relations. Algebraic Combinatorics, Volume 8 (2025) no. 1, pp. 29-57. doi : 10.5802/alco.406. https://alco.centre-mersenne.org/articles/10.5802/alco.406/
[1] The critical group of a line graph, Ann. Comb., Volume 16 (2012) no. 3, pp. 449-488 | DOI | MR | Zbl
[2] Remarks on recent formulas of Wilson and Frankl, European J. Combin., Volume 14 (1993) no. 1, pp. 1-8 | DOI | MR | Zbl
[3] On the -rank of the adjacency matrices of strongly regular graphs, J. Algebraic Combin., Volume 1 (1992) no. 4, pp. 329-346 | DOI | MR | Zbl
[4] Strongly regular graphs, Encyclopedia of Mathematics and its Applications, 182, Cambridge University Press, Cambridge, 2022, xvii+462 pages | DOI | MR
[5] The Smith group of the hypercube graph, Des. Codes Cryptogr., Volume 84 (2017) no. 1-2, pp. 283-294 | DOI | MR | Zbl
[6] The critical group of the Kneser graph on 2-subsets of an -element set, Linear Algebra Appl., Volume 546 (2018), pp. 154-168 | DOI | MR | Zbl
[7] A representation-theoretic computation of the rank of -intersection incidence matrices: -subsets vs. -subsets, 2023 | arXiv
[8] Intersection theorems and mod rank of inclusion matrices, J. Combin. Theory Ser. A, Volume 54 (1990) no. 1, pp. 85-94 | DOI | MR | Zbl
[9] A certain class of incidence matrices, Proc. Amer. Math. Soc., Volume 17 (1966), pp. 1233-1237 | DOI | MR | Zbl
[10] Resilience of ranks of higher inclusion matrices, J. Algebraic Combin., Volume 48 (2018) no. 1, pp. 31-50 | DOI | MR | Zbl
[11] SageMath, the Sage Mathematics Software System (Version 9.8) (2023) https://www.sagemath.org
[12] Smith normal forms of incidence matrices, Sci. China Math., Volume 56 (2013) no. 7, pp. 1359-1371 | DOI | MR | Zbl
[13] Tags on subsets, Discrete Math., Volume 306 (2006) no. 14, pp. 1610-1623 | DOI | MR | Zbl
[14] On Systems of Linear Indeterminate Equations and Congruences, Philos. T. R. Soc. Lond., Volume 151 (1861), pp. 293-326 | DOI
[15] What is an answer?, Amer. Math. Monthly, Volume 89 (1982) no. 5, pp. 289-292 | DOI | MR | Zbl
[16] A diagonal form for the incidence matrices of -subsets vs. -subsets, European J. Combin., Volume 11 (1990) no. 6, pp. 609-615 | DOI | MR | Zbl
[17] Diagonal forms of incidence matrices associated with -uniform hypergraphs, European J. Combin., Volume 35 (2014), pp. 490-508 | DOI | MR | Zbl
Cited by Sources: