×

GCD matrices, posets, and nonintersecting paths. (English) Zbl 1119.11022

Summary: We show that with any finite partially ordered set \(P\) (which need not be a lattice) one can associate a matrix whose determinant factors nicely. This was also noted by D. A. Smith [J. Reine Angew. Math. 251, 100–109 (1971; Zbl 0224.06002)], although his proof uses manipulations in the incidence algebra of \(P\) while ours is combinatorial, using nonintersecting paths in a digraph. As corollaries, we obtain new proofs for and generalizations of a number of results in the literature about GCD matrices and their relatives.

MSC:

11C20 Matrices, determinants in number theory
05A15 Exact enumeration problems, generating functions
06A07 Combinatorics of partially ordered sets
15B36 Matrices of integers

Citations:

Zbl 0224.06002
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Apostol TM, Pacific Journal of Mathematics 41 pp 281– (1972) · Zbl 0226.10045 · doi:10.2140/pjm.1972.41.281
[2] DOI: 10.1017/S0004972700017457 · Zbl 0675.10002 · doi:10.1017/S0004972700017457
[3] DOI: 10.1016/0024-3795(89)90572-7 · Zbl 0672.15005 · doi:10.1016/0024-3795(89)90572-7
[4] DOI: 10.1016/0024-3795(91)90051-W · Zbl 0754.15012 · doi:10.1016/0024-3795(91)90051-W
[5] Birkhoff GD, Transactions of the American Mathematical Society 60 pp 355– (1946) · doi:10.1090/S0002-9947-1946-0018401-4
[6] Chartrand G, Graphs and Digraphs (1986)
[7] Copeland A, Discrete Mathematics 256 pp 449– (2002) · Zbl 1009.15004 · doi:10.1016/S0012-365X(01)00208-4
[8] Dahab R, University of Waterloo (1993)
[9] Daniloff G, Sbornik na Bulgarska Akademia na Naukite 35 pp 479– (1942)
[10] DOI: 10.1016/0001-8708(85)90121-5 · Zbl 0579.05004 · doi:10.1016/0001-8708(85)90121-5
[11] Gessel I Viennot G Determinants, paths, and plane partitions (preprint, available at,http://www.cs.brandeis.edu/ĩra, )
[12] Harary F, Graph Theory, Addison-Wesley (1971)
[13] DOI: 10.1016/0024-3795(95)00349-5 · Zbl 0870.15016 · doi:10.1016/0024-3795(95)00349-5
[14] DOI: 10.1016/S0024-3795(96)00192-9 · Zbl 0883.15002 · doi:10.1016/S0024-3795(96)00192-9
[15] Jager H, Koninklijke Nederlandse Akademie van Wetenschappen Proceedings Series A 64 pp 508– (1961)
[16] Karlin S, Pacific Journal of Mathematics 9 pp 1141– (1959) · Zbl 0092.34503 · doi:10.2140/pjm.1959.9.1141
[17] DOI: 10.1016/S0024-3795(03)00497-X · Zbl 1036.06005 · doi:10.1016/S0024-3795(03)00497-X
[18] Krattenthaler C Watermelon configurations with wall interaction: Exact and asymptotic results preprint, available at,http://igd.univ-lyon1.fr/ webwuler/home/kratt/papers.html
[19] DOI: 10.1016/0024-3795(90)90012-2 · Zbl 0703.15012 · doi:10.1016/0024-3795(90)90012-2
[20] DOI: 10.2307/2035991 · Zbl 0165.02902 · doi:10.2307/2035991
[21] DOI: 10.1112/blms/5.1.85 · Zbl 0262.05018 · doi:10.1112/blms/5.1.85
[22] DOI: 10.1016/S0012-365X(99)00273-3 · Zbl 0959.05009 · doi:10.1016/S0012-365X(99)00273-3
[23] DOI: 10.1103/PhysRev.34.1293 · JFM 55.0535.04 · doi:10.1103/PhysRev.34.1293
[24] Smith DA, Journal fur die Reine und Angewandte Mathematik 251 pp 100– (1971) · Zbl 0224.06002 · doi:10.1515/crll.1971.251.100
[25] DOI: 10.1112/plms/s1-7.1.208 · JFM 08.0074.03 · doi:10.1112/plms/s1-7.1.208
[26] Stanley RP, Enumerative Combinatorics 1 (1997) · doi:10.1017/CBO9780511805967
[27] Tutte WT, Journal of Combinatorial Theory Series B 57 pp 269– (1993) · Zbl 0793.05030 · doi:10.1006/jctb.1993.1021
[28] Tutte WT, Discrete Mathematics 92 pp 417– (1991) · Zbl 0756.05059 · doi:10.1016/0012-365X(91)90296-E
[29] Wilf HS, American Mathematical Society. Bulletin 74 pp 960– (1968) · Zbl 0172.01602 · doi:10.1090/S0002-9904-1968-12104-4
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.