מטריצת אדמר

גילברט סטרנג מדגים את השערת אדמר ב- MIT ב-2005, באמצעות בניה של סילבסטר.

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

במתמטיקה, מטריצת אדמר, הנקראת על שם המתמטיקאי הצרפתי ז'אק אדמר, היא מטריצה ריבועית שערכיה הם או $+1$ או $-1$ ושורותיה אורתוגונליות זו לזו. במונחים גאומטריים, זה אומר שהשורות במטריצת אדמר מייצגות וקטורים מאונכים זה לזה. במונחים קומבינטוריים, זה אומר שלכל שתי שורות יש ערכים שווים בדיוק בחצי מהעמודות שלהם וערכים שונים בעמודות הנותרות. ניתן להראות כתוצאה, שהמאפיינים שתוארו לגבי השורות נכונים גם עבור עמודות המטריצה.

המקבילון ה-$n$-ממדי הנפרש על ידי השורות של מטריצת אדמר מסדר $n$ (באמצעות צירופים ליניאריים עם מקדמים לא שליליים קטנים או שווים ל-1), יש את הנפח ה-$n$-ממדי המקסימלי האפשרי עבור כל המקבילונים ה-$n$-ממדיים הנפרשים על ידי וקטורים אשר הערך המוחלט של כל רכיביהם קטן או שווה ל-$1$. באופן שקול ניתן לומר כי הערך המוחלט של הדטרמיננטה של מטריצת אדמר הוא המקסימלי האפשרי מבין המטריצות מאותו הסדר אשר הערך המוחלט של כל ערכיהן קטן או שווה ל-$1$. לכן מטריצת אדמר מהווה גם פתרון של בעיית הדטרמיננטה המקסימלית של אדמר.

ניתן להשתמש במטריצות אדמר מסוימות כקוד תיקון שגיאות באמצעות קוד אדמר (מקרה פרטי של קודי ריד-מולר ), וגם בסטטיסטיקה בניתוח מדגמים בשיטה של שכפול חוזר מאוזן ..

תכונות

נתונה $H$ מטריצת אדמר מסדר $n$. המטריצה המשוחלפת של $H$ קשורה קשר הדוק למטריצה ההופכית של $H$ באופן הבא:

$HH^{\textsf {T}}=nI_{n}$

כאשר $I_{n}$ היא מטריצת היחידה מסדר $n$ ו-$H^{T}$ הוא המטריצה המשוחלפת של $H$. כדי לראות שזה נכון, שימו לב שהשורות של $H$ הן וקטורים אורתוגונליים מעל שדה המספרים הממשיים ולכל אחד מהם יש אורך ${\sqrt {n}}$. מחלוקת $H$ באורך זה מתקבלת מטריצה אורתוגונלית שהמטריצה המשוחלפת שלה היא גם המטריצה ההופכית שלה. מכאן מתקבל השוויון למעלה. כתוצאה מכך נקבל,

$,\operatorname {det} (H)=\pm \,n^{n/2}$

כאשר ${\text{det}}(H)$ היא הדטרמיננטה של $H$.

נניח ש-$M$ היא מטריצה מסדר $n$ עם ערכים מרוכבים שערכם המוחלט קטן או שווה ל-$1$, כלומר $\left|M_{i,j}\right|\leq 1$ לכל $1\leq i,j\leq n$, אז מאי-שוויון אדמר נובע:

$.|\operatorname {det} (M)|\leq n^{n/2}$

שוויון מתקבל עבור מטריצה ממשית M אם ורק אם M היא מטריצת אדמר.

הסדר של מטריצת אדמר חייב להיות 1, 2 או כפולה של 4.

דוגמאות למטריצות אדמר נבנו לראשונה על ידי ג'יימס ג'וזף סילבסטר ב-1867. אם $H$ היא מטריצת אדמר מסדר $n$ אז המטריצה

${\begin{bmatrix}H&H\\H&-H\end{bmatrix}}$

היא מטריצת אדמר מסדר $2n$. ניתן ליישם זאת שוב ושוב ומתקבלת סדרת המטריצות הבאה, הנקראת גם מטריצות וולש .

${\begin{aligned}H_{1}&={\begin{bmatrix}1\end{bmatrix}}\\H_{2}&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\\H_{4}&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}\end{aligned}}$

ו-

$H_{2^{k}}={\begin{bmatrix}H_{2^{k-1}}&H_{2^{k-1}}\\H_{2^{k-1}}&-H_{2^{k-1}}\end{bmatrix}}=H_{2}\otimes H_{2^{k-1}}$

לכל $2\leq k\in N$, כאשר $\otimes$ מסמן את מכפלת קרונקר.

למעשה, בשיטה זו, סילבסטר הראה שניתן לקבל מטריצות אדמר מסדר $2^{k}$ עבור כל מספר שלם לא שלילי $k$.

למטריצות של סילבסטר יש את התכונות הבאות. הן סימטריות וכאשר $k>1$ למטריצה $H_{2^{k}}$ עקבה אפס. הערכים בעמודה הראשונה ובשורה הראשונה חיוביים ובכל השורות והעמודות האחרות יש מספר שווה של ערכים חיוביים ושליליים. מטריצות סילבסטר קשורות קשר הדוק עם פונקציות וולש.

בנייה חלופית

אם נמפה את הערכים של מטריצת אדמר באמצעות הומומורפיזם של חבורות $\{1,-1,\times \}\mapsto \{0,1,\oplus \}$, נוכל לתאר בנייה חלופית של מטריצות אדמר של סילבסטר. ראשית נגדיר את סדרת המטריצות $F_{n}$ מסדר $n\times 2^{n}$ באופן רקורסיבי:

${\begin{aligned}F_{1}&={\begin{bmatrix}0&1\end{bmatrix}}\\F_{n}&={\begin{bmatrix}0_{1\times 2^{n-1}}&1_{1\times 2^{n-1}}\\F_{n-1}&F_{n-1}\end{bmatrix}}\end{aligned}}$

ניתן להראות באמצעות אינדוקציה שהתמונה של מטריצת אדמר $H_{2^{n}}$ תחת ההומורפיזם הנ"ל ניתנת על ידי $F_{n}^{\textsf {T}}F_{n}$. בנייה זו מדגימה כי שורות מטריצת אדמר $H_{2^{n}}$ ניתן לראות כקוד תיקון שגיאות ליניארי באורך $2^{n}$, בדרגה $n$, מרחק מינימלי $2^{n-1}$ ועם מטריצה יוצרת $F_{n}$.

קוד זה מכונה גם קוד Walsh. לעומתו קוד אדמר, מסתמך על מטריצת אדמר $H_{2^{n}}$ באופן שונה.

השערת אדמר

  הבעיה הפתוחה החשובה ביותר בתורת המטריצות של אדמר היא שאלה של קיום. לפי השערת אדמר, מטריצת אדמר מסדר $4k$ קיימת עבור כל מספר שלם חיובי $k$. השערת אדמר יוחסה גם לפיילי, אם כי היא עלתה באופן עקיף גם בעבודות של אחרים שקדמו לפיילי.

הכללה של הבנייה של סילבסטר מוכיחה שאם $H_{n}$ ו-$H_{m}$ הם מטריצות אדמר מסדרים $n$ ו-$m$ בהתאמה, אז $H_{n}\otimes H_{m}$ היא מטריצת אדמר בסדר $nm$.

הבנייה של סילבסטר משנת 1867 מניבה מטריצות אדמר בסדר 1, 2, 4, 8, 16, 32 וכו'. אדמר בנה מטריצות אדמר מסדר 12 ו-20 בשנת 1893. בשנת 1933, ריימונד פיילי הראה כיצד לבנות מטריצת אדמר לכל $q$ שהוא חזקה טבעית של מספר ראשוני. אם $q$ מתחלק ל-4 עם שארית 3 אז למטריצת אדמר המתקבלת יש סדר $q+1$; אחרת, אם $q$ מתחלק ל-4 אם שארית 1 אז מטריצת אדמר המתקבלת היא מסדר $2(q+1)$. השיטה של פיילי מסתמכת על שדות סופיים.

הסדר הקטן ביותר שלא ניתן למצוא עבורו מטריצת אדמר בשילוב של השיטות של סילבסטר ופיילי הוא 92. מטריצת אדמר מסדר זה נמצאה באמצעות מחשב על ידי באומרט, גולומב והול בשנת 1962 ב-JPL. הם השתמשו בשיטה המיוחסת לוויליאמסון והניבה גם מטריצות אדמר מסדרים נוספים. כיום ידועות שיטות רבות אחרות לבניית מטריצות אדמר.

בשנת 2005 פרסמו האדי חראגאני ובהרוז טייפה-רזאי בנייה של מטריצת אדמר מסדר 428. כתוצאה מכך, הסדר הקטן ביותר שעבורו לא ידועה כיום מטריצת אדמר הוא 668.

נכון ל-2014 ישנם 12 סדרים (מתחלקים ב-4) שהם קטנים מ-2000 ולא ידועות מטריצות אדמר מסדרים אלו. הסדרים הם: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 ו-1964.

קישורים חיצוניים

מדיה וקבצים בנושא מטריצת אדמר בוויקישיתוף

• מטריצת אדמר, באתר MathWorld (באנגלית)