Μετάβαση στο περιεχόμενο

Πίνακας GCD

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Στα μαθηματικά, ο πίνακας του μέγιστου κοινού διαιρέτη[1] (μερικές φορές συντομογραφείται ως πίνακας GCD)[2] είναι ένας πίνακας που μπορεί επίσης να αναφέρεται ως πίνακας του Σμιθ. Η μελέτη του ξεκίνησε από τον H.J.S. Σμιθ (1875). Μια νέα έμπνευση ξεκίνησε από την εργασία των Μπουρκ & Λιχ (1992). Αυτό οδήγησε σε εντατικές έρευνες σχετικά με την ιδιομορφία και τη διαιρετότητα των πινάκων τύπου GCD. Μια σύντομη ανασκόπηση των εργασιών σχετικά με τους πίνακες τύπου GCD πριν από εκείνη την εποχή παρουσιάζεται στο Χαουκκάνεν, Γουάνγκ & Σιλάνπα (Haukkanen, Wang & Sillanpää (1997)[3].

1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 1 3 1 1 3 1 1 3 1
1 2 1 4 1 2 1 4 1 2
1 1 1 1 5 1 1 1 1 5
1 2 3 2 1 6 1 2 3 2
1 1 1 1 1 1 7 1 1 1
1 2 1 4 1 2 1 8 1 2
1 1 3 1 1 3 1 1 9 1
1 2 1 2 5 2 1 2 1 10
Πίνακας GCD του (1,2,3,...,10)

Έστω ένας κατάλογος θετικών ακεραίων αριθμών. Τότε ο πίνακας που έχει τον μέγιστο κοινό διαιρέτη ως την είσοδό του, αναφέρεται ως πίνακας GCD στο .Ο πίνακας LCM ορίζεται αναλογικά.[4][5]

Η μελέτη των πινάκων τύπου GCD προέρχεται από τον Smith (1875), ο οποίος αξιολόγησε τον προσδιοριστή ορισμένων πινάκων τύπου GCD και LCM. Ο Σμιθ έδειξε μεταξύ άλλων ότι η ορίζουσα του πίνακα is , όπου είναι η συνάρτηση ολικού συντελεστή του Όιλερ.[6]

Εικασία Μπουρκ - Λάι

[Επεξεργασία | επεξεργασία κώδικα]

Οι Μπουρκ & Λάι (1992) υπέθεσαν ότι ο LCM πίνακας σε ένα GCD-κλειστό σύνολο είναι μη-συνεκτικός[4]. Η εικασία αυτή αποδείχθηκε λανθασμένη από τους Χαουκκάνεν, Γουάνγκ & Σιλάνπα (Haukkanen, Wang & Sillanpää (1997) και στη συνέχεια από τον Χονγκ (Hong (1999).[7][5] Μια θεωρητική προσέγγιση με βάση το πλέγμα παρέχεται από τους Κόρκε, Ματίλα & Χαουκκάνεν (Korkee, Mattila & Haukkanen (2019).[8]

Το αντιπαράδειγμα που παρουσιάζεται στο Χαουκκάνεν, Γουάνγκ & Σιλάνπα (Haukkanen, Wang & Sillanpää (1997) είναι και αυτό στον Χονγκ (Hong (1999) είναι Ένα αντιπαράδειγμα που αποτελείται από περιττούς αριθμούς είναι . Το διάγραμμα Χάσε του παρουσιάζεται στα δεξιά παρακάτω.

Οι δομές τύπου κύβου αυτών των συνόλων σε σχέση με τη σχέση διαιρετότητας εξηγούνται στο Χαουκκάνεν, Γουάνγκ & Σιλάνπα (Korkee, Mattila & Haukkanen (2019).

Το διάγραμμα Χάσε ενός περιττού κλειστού συνόλου GCD του οποίου ο πίνακας LCM είναι ιδιάζων

Έστω ένα παραγοντικό κλειστό σύνολο. Τότε ο GCD πίνακας διαιρεί τον LCM πίνακα στο δακτύλιο των πινάκων πάνω στους ακεραίους, δηλαδή υπάρχει ένας ολοκληρωτικός πίνακας τέτοιος ώστε , βλέπε Bourque & Ligh (1992). Δεδομένου ότι οι πίνακες και είναι συμμετρικοί, έχουμε . Έτσι, η διαιρετότητα από τα δεξιά συμπίπτει με εκείνη από τα αριστερά. Μπορούμε επομένως να χρησιμοποιήσουμε τον όρο διαιρετότητα.

Υπάρχει στη βιβλιογραφία ένας μεγάλος αριθμός γενικεύσεων και αναλογιών αυτού του βασικού αποτελέσματος διαιρετότητας.

Στη βιβλιογραφία παρουσιάζονται ορισμένα αποτελέσματα σχετικά με τις νόρμες πινάκων πινάκων τύπου GCD. Δύο βασικά αποτελέσματα αφορούν την ασυμπτωτική συμπεριφορά της νόρμας του του πίνακα GCD και του πίνακα LCM σε . [9]

Δεδομένου του , η νόρμα ενός πίνακα ορίζεται ως εξής

Έστω . If , τότε

όπου

κσι for and . Επιπλέον, εάν , τότε

όπου

Παραγοντοποιήσεις

[Επεξεργασία | επεξεργασία κώδικα]

Έστω μια αριθμητική συνάρτηση, και έστω ένα σύνολο διαφορετικών θετικών ακεραίων αριθμών. Τότε ο πίνακας αναφέρεται ως ο πίνακας GCD στο που σχετίζεται με την . Ο LCM πίνακας στο που σχετίζεται με το ορίζεται αναλογικά. Μπορούμε επίσης να χρησιμοποιήσουμε τους συμβολισμούς και .

Έστω ένα κλειστό σύνολο GCD. Τότε

όπου είναι ο πίνακας που ορίζεται από τη σχέση

και είναι ο διαγώνιος πίνακας, του οποίου τα διαγώνια στοιχεία είναι

Εδώ είναι η συνέλιξη Ντίριχλετ και είναι η συνάρτηση Μπέμπιος (Möbius).

Επιπλέον, αν είναι πολλαπλασιαστική συνάρτηση και πάντα μη μηδενική, τότε

όπου και είναι οι διαγώνιοι πίνακες, των οποίων τα διαγώνια στοιχεία είναι και

Αν το είναι παραγοντικά κλειστό, τότε και . [9]

Εξωτερικοί σύνδεσμοι

[Επεξεργασία | επεξεργασία κώδικα]
  1. Bhat, B. V. Rajarama (1991-11-15). «On greatest common divisor matrices and their applications». Linear Algebra and its Applications 158: 77–97. doi:10.1016/0024-3795(91)90051-W. ISSN 0024-3795. https://www.sciencedirect.com/science/article/pii/002437959190051W. 
  2. «Generalized GCD matrices - Acta Univ. Sapientiae, Mathematica, 2, 2 (2010) 160–1» (PDF). 
  3. Haukkanen, Pentti; Wang, Jun; Sillanpää, Juha (1997-06-01). «On Smith's determinant». Linear Algebra and its Applications 258: 251–269. doi:10.1016/S0024-3795(96)00192-9. ISSN 0024-3795. https://www.sciencedirect.com/science/article/pii/S0024379596001929?via=ihub. 
  4. 4,0 4,1 Bourque, K.; Ligh, S. (1992). «On GCD and LCM matrices». Linear Algebra and Its Applications 174: 65–74. doi:10.1016/0024-3795(92)90042-9. https://archive.org/details/sim_linear-algebra-and-its-applications_1992-09_174/page/65. 
  5. 5,0 5,1 Hong, S. (1999). «On the Bourque–Ligh conjecture of least common multiple matrices». Journal of Algebra 218: 216–228. doi:10.1006/jabr.1998.7844. 
  6. Smith, H. J. S. (1875). «On the value of a certain arithmetical determinant». Proceedings of the London Mathematical Society 1: 208–213. doi:10.1112/plms/s1-7.1.208. https://zenodo.org/record/1709912. 
  7. Haukkanen, P.; Wang, J.; Sillanpää, J. (1997). «On Smith's determinant». Linear Algebra and Its Applications 258: 251–269. doi:10.1016/S0024-3795(96)00192-9. https://archive.org/details/sim_linear-algebra-and-its-applications_1997-06_258/page/251. 
  8. Korkee, I.; Mattila, M.; Haukkanen, P. (2019). «A lattice-theoretic approach to the Bourque–Ligh conjecture». Linear and Multilinear Algebra 67 (12): 2471–2487. doi:10.1080/03081087.2018.1494695. https://trepo.tuni.fi/handle/10024/117430. 
  9. 9,0 9,1 Haukkanen, P.; Toth, L. (2018). «Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs». Linear Algebra and Its Applications 558: 1–24. doi:10.1016/j.laa.2018.08.022.