On meet and join matrices on A-sets and related sets

Ismo Korkee
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 10, 2004, Number 3, Pages 57–67
Full paper (PDF, 293 Kb)

Details

Authors and affiliations

Ismo Korkee
Department of Mathematics, Statistics and Philosophy, University of Tampere
FI-33014 University of Tampere, Finland

Abstract

Let (P, ∧) be a meet-semilattice and let S = {x₁, x₂, …, x_n} be a subset of P. We say that S is an A-set if A = {x_i ∧ x_j | x_i ≠ x_j} is a chain. For example, chains and a-sets (with A = {a}) are known trivial A-sets. The meet matrix (S)_f on S with respect to a function f : P → C is defined as ((S)_f)_ij = f(x_i ∧ x_j).We present a recursive structure theorem for meet matrices on A-sets and thus obtain a recursive formula for det(S)_f and for (S)_f⁻¹ on A-sets. The recursive formulae also yield explicit formulae, e.g. the known determinant and inverse formulae on chains and a-sets. We also present the dual forms of our results, i.e. the determinant formulae and the inverse formulae for join matrices on join-semilattices. Finally, we suggest how our results can be generalized to more complicated cases.

As special cases these results hold also for GCD and LCM matrices and for their unitary analogies GCUD and LCUM matrices.

Keywords

• Meet matrix
• Join matrix
• Determinant
• Inverse matrix
• Asets
• GCD matrix
• LCM matrix

AMS Classification

• 11C20
• 15A09
• 15A15

References

1. M. Aigner, Combinatorial Theory. Springer-Verlag, 1979.
2. S. Beslin and S. Ligh, GCD-closed sets and the determinants of GCD matrices, Fibonacci Quart., 30: 157-160 (1992).
3. G. Birkhoff, Lattice Theory. American Mathematical Society Colloquium Publications, 25, Rhode Island, (1984).
4. P. Haukkanen, On meet matrices on posets, Linear Algebra Appl. 249: 111-123 (1996).
5. P. Haukkanen and J. Sillanpää, Some analogues of Smith’s determinant, Linear and Multilinear Algebra 41: 233-244 (1996).
6. P. Haukkanen, J.Wang and J. Sillanpää, On Smith’s determinant, Linear Algebra Appl. 258: 251-269 (1997).
7. R. A. Horn, C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1985.
8. I. Korkee, A note on meet and join matrices and their special cases GCUD and LCUM matrices. Accepted to Int. J. Pure Appl. Math.
9. I. Korkee and P. Haukkanen, Bounds for determinants of meet matrices associated with incidence functions, Linear Algebra Appl. 329(1-3): 77-88 (2001).
10. I. Korkee and P. Haukkanen, On meet and join matrices associated with incidence functions. Linear Algebra Appl., 372: 127-153 (2003).
11. I. Korkee and P. Haukkanen, On meet matrices with respect to reduced, extended and exchanged sets. Accepted to JP J. Algebra Number Theory Appl.
12. B. V. Rajarama Bhat, On greatest common divisor matrices and their applications, Linear Algebra Appl. 158: 77-97 (1991).
13. B. Wang, Explicit Expressions of Smith’s Determinant on a Poset, Acta Math. Sin. (Engl. Ser.), 17(1): 161-168 (2001).
14. F. Zhang, Matrix theory. Basic results and techniques, Universitext, Springer-Verlag, New York, 1999.