Πίνακας GCD

Στα μαθηματικά, ο πίνακας του μέγιστου κοινού διαιρέτη (μερικές φορές συντομογραφείται ως πίνακας GCD) είναι ένας πίνακας που μπορεί επίσης να αναφέρεται ως πίνακας του Σμιθ. Η μελέτη του ξεκίνησε από τον H.J.S. Σμιθ (1875). Μια νέα έμπνευση ξεκίνησε από την εργασία των Μπουρκ & Λιχ (1992). Αυτό οδήγησε σε εντατικές έρευνες σχετικά με την ιδιομορφία και τη διαιρετότητα των πινάκων τύπου GCD. Μια σύντομη ανασκόπηση των εργασιών σχετικά με τους πίνακες τύπου GCD πριν από εκείνη την εποχή παρουσιάζεται στο Χαουκκάνεν, Γουάνγκ & Σιλάνπα (Πρότυπο:Harvtxt.

Ορισμός

Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color	Πρότυπο:Color
Πίνακας GCD του (1,2,3,...,10)

Έστω $S=(x_1,x_2,\dots ,x_n)$ ένας κατάλογος θετικών ακεραίων αριθμών. Τότε ο $n\times n$ πίνακας $(S)$ που έχει τον μέγιστο κοινό διαιρέτη $\gcd (x_i,x_j)$ ως την $ij$ είσοδό του, αναφέρεται ως πίνακας GCD στο $S$.Ο πίνακας LCM $[S]$ ορίζεται αναλογικά.Πρότυπο:R

Η μελέτη των πινάκων τύπου GCD προέρχεται από τον Πρότυπο:Harvtxt, ο οποίος αξιολόγησε τον προσδιοριστή ορισμένων πινάκων τύπου GCD και LCM. Ο Σμιθ έδειξε μεταξύ άλλων ότι η ορίζουσα του $n\times n$ πίνακα $(\gcd (i,j))$ is $\varphi (1)\varphi (2)\cdots \varphi (n)$, όπου $\varphi$ είναι η συνάρτηση ολικού συντελεστή του Όιλερ.Πρότυπο:R

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

Οι Μπουρκ & Λάι (1992) υπέθεσαν ότι ο LCM πίνακας σε ένα GCD-κλειστό σύνολο $S$ είναι μη-συνεκτικόςΠρότυπο:R. Η εικασία αυτή αποδείχθηκε λανθασμένη από τους Χαουκκάνεν, Γουάνγκ & Σιλάνπα (Πρότυπο:Harvtxt και στη συνέχεια από τον Χονγκ (Πρότυπο:Harvtxt.Πρότυπο:R Μια θεωρητική προσέγγιση με βάση το πλέγμα παρέχεται από τους Κόρκε, Ματίλα & Χαουκκάνεν (Πρότυπο:Harvtxt.Πρότυπο:R

Το αντιπαράδειγμα που παρουσιάζεται στο Χαουκκάνεν, Γουάνγκ & Σιλάνπα (Πρότυπο:Harvtxt είναι $S=\{1,2,3,4,5,6,10,45,180\}$ και αυτό στον Χονγκ (Πρότυπο:Harvtxt είναι $S=\{1,2,3,5,36,230,825,227700\}.$ Ένα αντιπαράδειγμα που αποτελείται από περιττούς αριθμούς είναι $S=\{1,3,5,7,195,291,1407,4025,1020180525\}$. Το διάγραμμα Χάσε του παρουσιάζεται στα δεξιά παρακάτω.

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

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

Διαιρετότητα

Έστω $S=(x_1,x_2,\dots ,x_n)$ ένα παραγοντικό κλειστό σύνολο. Τότε ο GCD πίνακας $(S)$ διαιρεί τον LCM πίνακα $[S]$ στο δακτύλιο των $n\times n$ πινάκων πάνω στους ακεραίους, δηλαδή υπάρχει ένας ολοκληρωτικός πίνακας $B$ τέτοιος ώστε $[S]=B(S)$, βλέπε Πρότυπο:Harvtxt. Δεδομένου ότι οι πίνακες $(S)$ και $[S]$ είναι συμμετρικοί, έχουμε $[S]=(S)B^T$. Έτσι, η διαιρετότητα από τα δεξιά συμπίπτει με εκείνη από τα αριστερά. Μπορούμε επομένως να χρησιμοποιήσουμε τον όρο διαιρετότητα.

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

Κανόνες πίνακα

Στη βιβλιογραφία παρουσιάζονται ορισμένα αποτελέσματα σχετικά με τις νόρμες πινάκων πινάκων τύπου GCD. Δύο βασικά αποτελέσματα αφορούν την ασυμπτωτική συμπεριφορά της νόρμας ${\ell }_p$ του του πίνακα GCD και του πίνακα LCM σε $S=\{1,2,\dots ,n\}$. Πρότυπο:R

Δεδομένου του $p\in {\mathbb{N}}^{+}$, η νόρμα ${\ell }_p$ ενός $n\times n$ πίνακα $A$ ορίζεται ως εξής

$\Vert A{\Vert }_p={(\sum _{i=1}^n\sum _{j=1}^n|a_{ij}{|}^p)}^{1/p}.$

Έστω $S=\{1,2,\dots ,n\}$. If $p\ge 2$, τότε

$\Vert (S){\Vert }_p=C_p^{1/p}{n}^{1+(1/p)}+O((n^{(1/p)-p}{E}_p(n)),$

όπου

$C_p:=\frac{2\zeta (p)-\zeta (p+1)}{(p+1)\zeta (p+1)}$

κσι $E_p(x)=x^p$ for $p>2$ and $E_2(x)=x^2\log x$. Επιπλέον, εάν $p\ge 1$, τότε

$\Vert [S]{\Vert }_p=D_p^{1/p}{n}^{2+(2/p)}+O((n^{(2/p)+1}(\log n{)}^{2/3}(\log \log n{)}^{4/3}),$

όπου

$D_p:=\frac{\zeta (p+2)}{(p+1{)}^2\zeta (p)}.$

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

Έστω $f$ μια αριθμητική συνάρτηση, και έστω $S=(x_1,x_2,\dots ,x_n)$ ένα σύνολο διαφορετικών θετικών ακεραίων αριθμών. Τότε ο πίνακας $(S{)}_f=(f(\gcd (x_i,x_j))$ αναφέρεται ως ο πίνακας GCD στο $S$ που σχετίζεται με την $f$. Ο LCM πίνακας $[S{]}_f$ στο $S$ που σχετίζεται με το $f$ ορίζεται αναλογικά. Μπορούμε επίσης να χρησιμοποιήσουμε τους συμβολισμούς $(S{)}_f=f(S)$ και $[S{]}_f=f[S]$.

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

$(S{)}_f=E\mathrm{\Delta }{E}^T,$

όπου $E$ είναι ο πίνακας $n\times n$ που ορίζεται από τη σχέση

$e_{ij}=\{\begin{array}{cc}1& \text{if }{x}_j\mid x_i,\\ 0& \text{otherwise}\end{array}$

και $\mathrm{\Delta }$ είναι ο $n\times n$ διαγώνιος πίνακας, του οποίου τα διαγώνια στοιχεία είναι

${\delta }_i=\sum _{\genfrac{}{}{0ex}{}{d\mid x_i}{\genfrac{}{}{0ex}{}{d\nmid x_t}{x_t<x_i}}}(f\star \mu )(d).$

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

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

$[S{]}_f=\mathrm{\Lambda }E{\mathrm{\Delta }}^{\prime }{E}^T\mathrm{\Lambda },$

όπου $\mathrm{\Lambda }$ και ${\mathrm{\Delta }}^{\prime }$ είναι οι $n\times n$ διαγώνιοι πίνακες, των οποίων τα διαγώνια στοιχεία είναι ${\lambda }_i=f(x_i)$ και

${\delta }_i^{\prime }=\sum _{\genfrac{}{}{0ex}{}{d|x_i}{\genfrac{}{}{0ex}{}{d\nmid x_t}{x_t<x_i}}}(\frac{1}{f}\star \mu )(d).$

Αν το $S$ είναι παραγοντικά κλειστό, τότε ${\delta }_i=(f\star \mu )(x_i)$ και ${\delta }_i^{\prime }=(\frac{1}{f}\star \mu )(x_i)$. Πρότυπο:R

Δημοσιεύσεις

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite book
• Πρότυπο:Cite book
• Πρότυπο:Cite book
• Πρότυπο:Cite book
• Πρότυπο:Cite book

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Πραγματικός αριθμός
• Αντιερμιτιανός πίνακας
• Μέγιστος κοινός διαιρέτης
• Ταυτοτικός πίνακας
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Μετασχηματισμός Λαπλάς
• Αντιμεταθέσιμοι πίνακες
• Πολλαπλασιασμός πινάκων
• Πέτερ Γκούσταφ Λεζέν Ντίριχλετ
• Διακριτός μετασχηματισμός Φουριέ
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

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

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Exercises of Matrices and Linear Algebra
• Fourier Transforms: Approach to Scientific Principles
• Information Security and Privacy: 13th Australasian Conference, ACISP 2008 ...
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Matrix Theory: From Generalized Inverses to Jordan Form
• Multimedia Content Representation, Classification and Security ...
• Structured Matrix Based Methods for Approximate Polynomial GCD