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

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

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

## Τετραγωνικός χαρακτήρας και πίνακας Ιακωμπστάλ
Έστω *q* μια δύναμη ενός περιττού πρώτου αριθμού. Στο πεπερασμένο σώμα GF(*q*) ο τετραγωνικός χαρακτήρας χ(*a*) δείχνει αν το στοιχείο *a* είναι μηδέν, ένα μη μηδενικό τετράγωνο ή ένα μη τετράγωνο:
:\chi(a) = \begin{cases} 0 & \text{Αν }a = 0\\
1 & \text{Αν } a = b^2\text{ για κάποιο μη μηδενικό }b \in \mathrm{GF}(q)\\
-1 & \text{Αν }a\text{ δεν είναι το τετράγωνο οποιουδήποτε στοιχείου του }\mathrm{GF}(q).\end{cases}

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

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

:Q = \begin{bmatrix}
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{bmatrix}.

Ο πίνακας Ιακωμπστάλ έχει τις ιδιότητες *QQ*T = *qI*&nbsp;-&nbsp;*J* και *QJ* = *JQ* = 0 όπου *I* είναι το *q*&thinsp;×&thinsp;*q*. ταυτοτικός πίνακας και *J* είναι ο *q*&thinsp;×&thinsp;*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 + \begin{bmatrix}
0 & j^T \\
-j & Q \end{bmatrix}

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

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

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

:\begin{bmatrix}
0 & j^T \\
j & Q \end{bmatrix}

με τον πίνακα

:\begin{bmatrix}
1 & -1 \\
-1 & -1 \end{bmatrix}

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

:\pm\begin{bmatrix}
1 & 1 \\
1 & -1 \end{bmatrix}

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

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

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

:\begin{bmatrix}
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{bmatrix}.

Ως παράδειγμα της κατασκευής Πάλεϊ 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)2, −*a*+1 = (±*a*)2, *a*−1 = (±(*a*+1))2, και −1 = (±(*a*−1))2. Ο πίνακας Ιακωμπστάλ είναι 

:Q = \begin{bmatrix}
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{bmatrix}.

Είναι ένας συμμετρικός πίνακας που αποτελείται από εννέα κυκλικά μπλοκ 3&thinsp;×&thinsp;3.  Η κατασκευή Πάλεϊ B' παράγει τον συμμετρικό πίνακα Ανταμάρ 20&thinsp;×&thinsp;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&thinsp;×&thinsp;2,

:H_2 = \begin{bmatrix}
1 &  1 \\
1 & -1 \end{bmatrix},

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

* 
* 
* 

 

Κατηγορία:Αριθμητική γραμμική άλγεβρα
Κατηγορία:Γραμμική άλγεβρα
Κατηγορία:Πίνακες (μαθηματικά)
Κατηγορία:Θεωρία πινάκων
Κατηγορία:Συνδυαστική