Κατασκευή Πάλεϊ

Στα μαθηματικά, η κατασκευή Πάλεϊ είναι μια μέθοδος για την κατασκευή πινάκων Ανταμάρ χρησιμοποιώντας πεπερασμένα σώματα. Η κατασκευή περιγράφηκε το 1933 από τον Άγγλο μαθηματικό Ρέιμοντ Πάλεϊ .

Η κατασκευή Πάλεϊ χρησιμοποιεί τετραγωνικά κατάλοιπα σε ένα πεπερασμένο σώμα GF(q) όπου q είναι δύναμη ενός περιττού πρώτου αριθμού. Υπάρχουν δύο εκδοχές της κατασκευής ανάλογα με το αν το q είναι ισότιμο με το 1 ή το 3 modulo 4.

Τετραγωνικός χαρακτήρας και πίνακας Ιακωμπστάλ

Έστω q μια δύναμη ενός περιττού πρώτου αριθμού. Στο πεπερασμένο σώμα GF(q) ο τετραγωνικός χαρακτήρας χ(a) δείχνει αν το στοιχείο a είναι μηδέν, ένα μη μηδενικό τετράγωνο ή ένα μη τετράγωνο:

$\chi (a)=\{\begin{array}{cc}0& \text{Αν }a=0\\ 1& \text{Αν }a=b^2\text{ για κάποιο μη μηδενικό }b\in \mathrm{G}\mathrm{F}(q)\\ -1& \text{Αν }a\text{ δεν είναι το τετράγωνο οποιουδήποτε στοιχείου του }\mathrm{G}\mathrm{F}(q).\end{array}$

Παραδείγματος χάριν, στο GF(7) τα μη μηδενικά τετράγωνα είναι 1 = 1² = 6², 4 = 2² = 5², και 2 = 3² = 4². Ως εκ τούτου χ(0) = 0, χ(1) = χ(2) = χ(4) = 1, και χ(3) = χ(5) = χ(6) = −1.

Ο πίνακας Ιακωμπστάλ Q για GF(q) είναι ο q × q πίνακας με γραμμές και στήλες δεικτοδοτημένες από στοιχεία του GF(q') έτσι ώστε η εγγραφή στη γραμμή a και στη στήλη b να είναι χ(a - b). Παραδείγματος χάριν, στο GF(7), εάν οι γραμμές και οι στήλες του πίνακα Ιακωμπστάλ δεικτοδοτούνται από τα σώματα στοιχεία 0, 1, 2, 3, 4, 5, 6, τότε

$Q=\left[\begin{array}{ccccccc}0& -1& -1& 1& -1& 1& 1\\ 1& 0& -1& -1& 1& -1& 1\\ 1& 1& 0& -1& -1& 1& -1\\ -1& 1& 1& 0& -1& -1& 1\\ 1& -1& 1& 1& 0& -1& -1\\ -1& 1& -1& 1& 1& 0& -1\\ -1& -1& 1& -1& 1& 1& 0\end{array}\right].$

Ο πίνακας Ιακωμπστάλ έχει τις ιδιότητες QQ^T = qI - J και QJ = JQ = 0 όπου I είναι το q × q. ταυτοτικός πίνακας και J είναι ο q × q πίνακας όλων των 1. Αν ο q είναι σύμφωνος με το 1 mod 4 τότε το -1 είναι τετράγωνο στο GF(q) το οποίο συνεπάγεται ότι το Q είναι ένας συμμετρικός πίνακας. Αν q είναι ισοτιμό με το 3 mod 4 τότε το -1 δεν είναι τετράγωνο και το Q είναι αντισυμμετρικός πίνακας . Όταν το q είναι πρώτος αριθμός και οι γραμμές και οι στήλες δεικτοδοτούνται από στοιχεία του πεδίου με τη συνήθη σειρά 0, 1, 2, ..., ο Q είναι ένας κυκλοτερής πίνακας. Δηλαδή, κάθε γραμμή προκύπτει από την παραπάνω γραμμή με κυκλική μετάθεση.

Kατασκευή Πάλεϊ A'

Αν το q είναι ισοδύναμο με το 3 mod 4 τότε

$H=I+\left[\begin{array}{cc}0& j^T\\ -j& Q\end{array}\right]$

είναι ένας πίνακας Ανταμάρ μεγέθους q + 1. Εδώ j είναι το διάνυσμα στήλης all-1 μήκους q και I είναι ο πίνακας ταυτότητας (q+1)×(q+1). Ο πίνακας H είναι ένας αντισυμμετρικός πίνακας Ανταμάρ, που σημαίνει ότι ικανοποιεί τη συνθήκη H + H^T = 2I.

Kατασκευή Πάλεϊ B'

Εάν το q είναι ισοδύναμο με το 1 mod 4, τότε ο πίνακας που προκύπτει με την αντικατάσταση όλων των καταχωρήσεων 0 στο

$\left[\begin{array}{cc}0& j^T\\ j& Q\end{array}\right]$

με τον πίνακα

$\left[\begin{array}{cc}1& -1\\ -1& -1\end{array}\right]$

και όλες οι καταχωρήσεις ±1 με τον πίνακα

$\pm \left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$

είναι ένας πίνακας Ανταμάρ μεγέθους 2(q + 1). Είναι συμμετρικός πίνακας Ανταμάρ.

Παραδείγματα

Εφαρμόζοντας την κατασκευή Πάλεϊ A' στον πίνακα Ιακωμπστάλ για GF(7), προκύπτει ο πίνακας Ανταμάρ 8 × 8,

$\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ -1& 1& -1& -1& 1& -1& 1& 1\\ -1& 1& 1& -1& -1& 1& -1& 1\\ -1& 1& 1& 1& -1& -1& 1& -1\\ -1& -1& 1& 1& 1& -1& -1& 1\\ -1& 1& -1& 1& 1& 1& -1& -1\\ -1& -1& 1& -1& 1& 1& 1& -1\\ -1& -1& -1& 1& -1& 1& 1& 1\end{array}\right].$

Ως παράδειγμα της κατασκευής Πάλεϊ B' όταν το q είναι μια πρώτη δύναμη και όχι ένας πρώτος αριθμός, ας δούμε τον GF(9). Αυτό είναι ένα σώμα επέκτασης του GF(3) που προκύπτει από την προσάρτηση μιας ρίζας ενός μη αναγώγιμου τετραγωνικού. Διαφορετικοί μη αναγώγιμοι τετραγωνικοί παράγουν ισοδύναμα πεδία. Επιλέγοντας x2+x-1 και αφήνοντας μια ρίζα αυτού του πολυωνύμου, τα εννέα στοιχεία του GF(9) μπορούν να γραφούν 0, 1, −1, a, a+1, a−1, −a, −a+1, −a−1. Τα μη μηδενικά τετράγωνα είναι 1 = (±1)², −a+1 = (±a)², a−1 = (±(a+1))², και −1 = (±(a−1))². Ο πίνακας Ιακωμπστάλ είναι

$Q=\left[\begin{array}{ccccccccc}0& 1& 1& -1& -1& 1& -1& 1& -1\\ 1& 0& 1& 1& -1& -1& -1& -1& 1\\ 1& 1& 0& -1& 1& -1& 1& -1& -1\\ -1& 1& -1& 0& 1& 1& -1& -1& 1\\ -1& -1& 1& 1& 0& 1& 1& -1& -1\\ 1& -1& -1& 1& 1& 0& -1& 1& -1\\ -1& -1& 1& -1& 1& -1& 0& 1& 1\\ 1& -1& -1& -1& -1& 1& 1& 0& 1\\ -1& 1& -1& 1& -1& -1& 1& 1& 0\end{array}\right].$

Είναι ένας συμμετρικός πίνακας που αποτελείται από εννέα κυκλικά μπλοκ 3 × 3. Η κατασκευή Πάλεϊ B' παράγει τον συμμετρικό πίνακα Ανταμάρ 20 × 20,

1- 111111 111111 111111
-- 1-1-1- 1-1-1- 1-1-1-

11 1-1111 ----11 --11--
1- --1-1- -1-11- -11--1
11 111-11 11---- ----11
1- 1---1- 1--1-1 -1-11-
11 11111- --11-- 11----
1- 1-1--- -11--1 1--1-1

11 --11-- 1-1111 ----11
1- -11--1 --1-1- -1-11-
11 ----11 111-11 11----
1- -1-11- 1---1- 1--1-1
11 11---- 11111- --11--
1- 1--1-1 1-1--- -11--1

11 ----11 --11-- 1-1111
1- -1-11- -11--1 --1-1-
11 11---- ----11 111-11
1- 1--1-1 -1-11- 1---1-
11 --11-- 11---- 11111-
1- -11--1 1--1-1 1-1---.

Η εικασία Ανταμάρ

Το μέγεθος ενός πίνακα Ανταμάρ πρέπει να είναι 1, 2 ή πολλαπλάσιο του 4. Το γινόμενο Κρόνεκερ δύο πινάκων Ανταμάρ μεγέθους m και n είναι ένας πίνακας Ανταμάρ μεγέθους mn. Σχηματίζοντας γινόμενα Κρόνεκερ των πινάκων από την κατασκευή Πάλεϊ και τον πίνακα 2 × 2,

$H_2=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right],$

Παράγονται πίνακες Ανταμάρ κάθε επιτρεπόμενου μεγέθους έως 100 εκτός από 92. Στην εργασία του το 1933, ο Πάλεϊ αναφέρει: «Φαίνεται πιθανό ότι, όποτε το m διαιρείται με το 4, είναι δυνατόν να κατασκευαστεί ένας ορθογώνιος πίνακας τάξης m που αποτελείται από ±1, αλλά το γενικό θεώρημα έχει κάθε ένδειξη δυσκολίας». Αυτή φαίνεται να είναι η πρώτη δημοσιευμένη δήλωση της εικασίας Ανταμάρ. Ένας πίνακας μεγέθους 92 κατασκευάστηκε τελικά από τους Μπαούμερτ, Γκόλομπ και Χαλ, χρησιμοποιώντας μια κατασκευή που οφείλεται στον Ουίλιαμσον σε συνδυασμό με μια αναζήτηση στον υπολογιστή. Επί του παρόντος, έχει αποδειχθεί ότι υπάρχουν πίνακες Ανταμάρ για όλα τα $m\equiv 0mod4$ για m < 668.

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

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Bressoud, David M., Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.Πρότυπο:ISBN
• Bressoud, David M. and Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society, 46 (1999), 637–646.
• Mills, William H., Robbins, David P., and Rumsey, Howard Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae, 66 (1982), 73–87.
• Mills, William H., Robbins, David P., and Rumsey, Howard Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A, 34 (1983), 340–359.
• Propp, James, The many faces of alternating-sign matrices, Discrete Mathematics and Theoretical Computer Science, Special issue on Discrete Models: Combinatorics, Computation, and Geometry (July 2001).
• Razumov, A. V., Stroganov Yu. G., Combinatorial nature of ground state vector of O(1) loop model, Theor. Math. Phys., 138 (2004), 333–337.
• Razumov, A. V., Stroganov Yu. G., O(1) loop model with different boundary conditions and symmetry classes of alternating-sign matrices], Theor. Math. Phys., 142 (2005), 237–243, Πρότυπο:Arxiv
• Πρότυπο:Citation

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Πραγματικός αριθμός
• Αντιερμιτιανός πίνακας
• Ενελικτικός πίνακας
• Ταυτοτικός πίνακας
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Πεπερασμένο σώμα
• Αντιμεταθέσιμοι πίνακες
• Πολλαπλασιασμός πινάκων
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
• Algorithm overview

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

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Integral Matrices
• Basic Matrix Algebra with Algorithms and Applications
• An Introduction to Optimization: With Applications to Machine Learning
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Designs and Their Codes
• Random Matrices and the Six-Vertex Model
• Symmetry and Combinatorics

Παραπομπές

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