阿達馬的最大行列式問題

本文的閱讀等級:中級

公元1893年,法國數學家阿達馬 (Jacques Hadamard) 提出下面的最大行列式問題:若 A=[a_{ij}] 為一 n\times n 階矩陣且 \vert a_{ij}\vert\le 1i,j=1,\ldots,n\vert \det A\vert 的最大值是多少?表面上,要找到解決這個約束最大化問題的切入點似乎相當困難。阿達馬想出了一個簡單的辦法:他先推導行列式 (絕對值) 的上界,接著求出滿足此上界的矩陣所具備的條件,最後設法尋找擁有該條件的矩陣。出乎意料的是,複矩陣問題比實矩陣問題容易解決得多。下面我們追隨阿達馬的腳步探索約束矩陣的最大行列式問題。

 
第一個問題:所有元的絕對值不大於 1 的行列式 (絕對值) 的上界為何?給定一 n\times n 階矩陣 A\vert\det A\vert 等於 A 的行向量 (或列向量) 於 \mathbb{C}^n 空間所張開的高維「平行多面體體積」(見“行列式的幾何意義”)。從幾何直觀,行向量構成平行多面體的邊,當所有的行向量彼此正交時,平行多面體具有最大體積,該體積即為各方向邊長的乘積。這個幾何性質可以用代數不等式來描述。若 A=[a_{ij}] 為一 n\times n 階矩陣,\mathbf{a}_1,\ldots,\mathbf{a}_n 表示 A 的行向量,阿達馬寫出

\displaystyle  \vert\det A\vert\le\prod_{j=1}^n\Vert\mathbf{a}_j\Vert

其中 \Vert\mathbf{a}_j\Vert^2=\sum_{i=1}^n\vert a_{ij}\vert^2。後人稱此不等式為 Hadamard 不等式 (見“Hadamard 不等式”)。若 A 是可逆矩陣,僅當 A 的行向量 (或列向量) 彼此正交時,即對於 i\neq j\mathbf{a}_i^{\ast}\mathbf{a}_j=0,也就是說,A^\ast A 為一對角矩陣,Hadamard 不等式的等號才成立。如果 A 的每一元滿足 \vert a_{ij}\vert\le 1,則 \Vert\mathbf{a}_j\Vert^2\le nj=1,\ldots,n。套用 Hadamard 不等式,可得行列式 (絕對值) 的上界:

\displaystyle  \vert \det A\vert\le \prod_{j=1}^nn^{1/2}=n^{n/2}

 
第二個問題:矩陣 A 必須具備甚麼條件方使 \vert\det A\vert=n^{n/2}?矩陣 A 具有最大行列式 (絕對值) 的條件是 \vert a_{ij}\vert=11\le i,j\le n,且 A^{\ast}A=nI_n,證明於下:

\displaystyle\begin{aligned}  (\det A)^2&=\overline{\det A}\det A=(\det A^\ast)(\det A)=\det(A^\ast A)\\  &=\det(nI_n)=n^n\det I_n=n^n.\end{aligned}

注意,A^\ast A=nI_n 等同 AA^\ast=nI_n。若 A^\ast A=nI_n,則 (AA^\ast)^2=AA^\ast AA^\ast=n(AA^\ast)。因為 A 是可逆矩陣 (\vert\det A\vert=n^{n/2}\neq 0),AA^\ast 亦為可逆矩陣,故 AA^\ast=nI_n

 
第三個問題:是否存在滿足 \vert a_{ij}\vert=11\le i,j\le n,且 A^{\ast}A=nI_n 的矩陣 A?最著名的一個例子是傅立葉矩陣

\displaystyle  F=\begin{bmatrix}  1&1&1&\cdots&1\\  1&w&w^2&\cdots&w^{n-1}\\  1&w^2&w^4&\cdots&w^{2(n-1)}\\  \vdots&\vdots&\vdots&\ddots&\vdots\\  1&w^{n-1}&w^{2(n-1)}&\cdots&w^{(n-1)^2}  \end{bmatrix}

其中 w=e^{2\pi i/n}i=\sqrt{-1}。傅立葉矩陣 F 的每一元皆可表示為 w^p,其中 p 是一整數,顯然 \vert w^p\vert=1。因為 F^{-1}=\frac{1}{n}\overline{F}=\frac{1}{n}F^\ast (證明見“離散傅立葉轉換”),可知 F^{\ast}F=nI_n

 
傅立葉矩陣是一個複矩陣,是否存在實矩陣滿足最大行列式 (絕對值) 條件?為方便討論,若一 n\times n 階實矩陣 A=[a_{ij}] 的每一元 a_{ij} 等於 1-1,且 A^TA=nI_n,我們稱它為 Hadamard 矩陣。下面是三個尺寸不同的 Hadamard 矩陣:

\displaystyle  \begin{bmatrix}  1  \end{bmatrix},~~~\left[\!\!\begin{array}{cr}  1&1\\  1&-1  \end{array}\!\!\right],~~~\left[\!\!\begin{array}{crrr}  1&1&1&1\\  1&-1&1&-1\\  1&1&-1&-1\\  1&-1&-1&1  \end{array}\!\!\right]

Hadamard 矩陣成立的必要條件是矩陣階數 n 等於 1, 24 的倍數。下面我們證明:若 A 為一 n\times n 階 Hadamard 矩陣,n>2,則 n 必定被 4 整除。考慮 A 的兩個行向量 \mathbf{a}_j\mathbf{a}_kj\neq k。因為 \mathbf{a}_j 正交於 \mathbf{a}_K

\displaystyle  0=\mathbf{a}_j^T\mathbf{a}_k=\sum_{i=1}^na_{ij}a_{ik}=\underbrace{\pm 1\pm 1\cdots\pm 1}_{n}

明顯地,n 是一偶數,且 \mathbf{a}_j\mathbf{a}_kn/2 個相同元。再考慮 A 的三個相異行 \mathbf{a}_j,\mathbf{a}_k,\mathbf{a}_l,即有

\displaystyle\begin{aligned}  (\mathbf{a}_j+\mathbf{a}_k)^T(\mathbf{a}_j+\mathbf{a}_l)&=\sum_{i=1}^n(a_{ij}+a_{ik})(a_{ij}+a_{il})\\  &=\sum_{i=1}^na_{ij}^2+\sum_{i=1}^na_{ij}a_{il}+\sum_{i=1}^na_{ik}a_{ij}+\sum_{i=1}^na_{ik}a_{il}\\  &=n+0+0+0=n.\end{aligned}

a_{ij}=a_{ik}=a_{il},則 (a_{ij}+a_{ik})(a_{ij}+a_{il})=4,否則 (a_{ij}+a_{ik})(a_{ij}+a_{il})=0。令 p 表示滿足 a_{ij}=a_{ik}=a_{il} 的列指標 (即 i) 總數。合併以上結果,證得 n=4p

 
阿達馬確認了 Hadamard 矩陣存在的必要條件後,他猜想每一 n=4kk\ge 1,都存在一 Hadamard 矩陣。這個問題吸引了不少學者投入研究,但仍懸而未決,至今人們還沒有找到 668\times 668 (k=167) 階 Hadamard 矩陣。另外,我們可以考慮更廣義的問題:對於 n\times n\{1,-1\} 矩陣,最大的行列式 (絕對值) 是多少?今天,n=22 是尺寸最小的未解問題[1]。讀者或許納悶,既然 \{1,-1\} 矩陣的每一元為 1-1,我們只要計算有限數量的行列式即可。不過,事情沒有這麼簡單。對於 n\times n 階矩陣,待檢查的行列式數量是 2^{n^2}。若 n=222^{22^2}=2^{484} 大約為 10^{144},這不啻是一個天文數字。

 
參考來源:
[1] 維基百科:Hadamard’s maximal determinant problem

Advertisements
本篇發表於 線性代數專欄, 行列式 並標籤為 , , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s