Нерівність Адамара

Нерівність Адамара (також теорема Адамара про визначники), визначає верхню межу об'єму паралелепіпеда в $n$-вимірному евклідовому просторі, заданого $n$ векторами. Названа на честь Жака Адамара.

Формулювання

Нехай $M$ — матриця стовпцями якої є вектори $v_i\in {ℂ}^n,i=1,2,\dots ,n$. Тоді

$|\det (M)|⩽\prod _{i=1}^n{||v_i||}_2,$

де ${||\cdot ||}_2$ — евклідова норма вектора, тобто для вектора $a=(a_1,a_2,\dots ,a_n)$ норма рівна $||a|{|}_2:=\sqrt{|a_1{|}^2+|a_2{|}^2+\cdots +|a_n{|}^2}={(\sum _{i=1}^n|a_i{|}^2)}^{1/2}$

У випадку матриці з дійсними елементами, з точки зору геометрії нерівність стверджує, що об'єм $n$-вимірного паралелепіпеда є максимальним, коли його задають взаємно перпендикулярні вектори.

Для матриці $M$ її матриця Грама $A=M^{*}M$ є додатноозначеною. Окрім того $\det A=(\det M{)}^2$ і $a_{ii}={||v_i||}_2^2.$ Тому достатньо довести твердження:

Якщо матриця $A$ розмірності $n\times n$ є додатноозначеною, то

$|A|⩽a_{11}{a}_{22}\dots a_{nn}.$

Доведення

Визначник $|A|$ можна представити у вигляді

$|A|=a_{11}\left|\begin{array}{ccc}{a}_{22}& \dots & a_{2n}\\ a_{32}& \dots & a_{3n}\\ \dots & \dots & \dots \\ a_{n2}& \dots & a_{nn}\end{array}\right|+\left|\begin{array}{cccc}0& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ \dots & \dots & \dots & \dots \\ a_{n1}& a_{n2}& \dots & a_{nn}\end{array}\right|.$

Так як $A$ додатноозначена, то і матриця, яка є першим доданком в сумі, теж додатноозначена. Позначимо $A^{\prime }$ матрицю, що одержується з $A$ вилученням першого рядка і стовпця. Оскільки вона є додатноозначеною то додатноозначеною є і її союзна матриця (оскільки її власними значеннями будуть $\det A^{\prime }/\lambda$ , де $\lambda$ — власні значення матриці $A^{\prime }$). Проіндексуємо рядки і стовпці A' від 2 до $n$ (тобто кожен елемент буде мати той же індекс, що і в $A$). Якщо позначити $M^{ij}$ — мінор матриці $A^{\prime }$ при вилученні $i$-го рядка і $j$-го стовпця, то елемент $A_{ij}$ союзної матриці буде рівним $(-1{)}^{i+j}{M}^{ij}$. Натомість у другому визначнику вище множник біля $a_{1j}{a}_{i1}$ буде рівний $(-1{)}^{1+j}(-1{)}^{1+i-1}{M}^{ij}$ тобто $-A_{ij}$.

Отже, квадратична форма по змінним $a_{12},a_{13},\dots ,a_{1n}$, якою є другий доданок, є відємноозначеною. Тому

$|A|⩽a_{11}\left|\begin{array}{ccc}{a}_{22}& \dots & a_{2n}\\ a_{32}& \dots & a_{3n}\\ \dots & \dots & \dots \\ a_{n2}& \dots & a_{nn}\end{array}\right|$ і рівність є можливою тоді і лише тоді коли всі $a_{12},a_{13},\dots ,a_{1n}$ є рівними нулю.

Звідси, застосовуючи індукцію, отримуємо необхідний результат.

Геометричне доведення

Виділимо в першому векторі дві складові $v_1=v_S+v_N$, перша належить підпростору векторів $v_2,\dots ,v_n$, а друга— ортогональна до нього. Тоді ${||v_1||}_2^2={||v_N||}_2^2+{||v_S||}_2^2⩾{||v_N||}_2^2$.

Позначимо $G(v_1,v_2,\dots ,v_n)=|M^{*}M|$ — визначник Грама векторів $v_1,v_2,\dots ,v_n$. Розкладемо його в суму за лівим верхнім елементом і використаємо властивості ортогональності:

$\begin{array}{cc}G(v_1,v_2,\dots ,v_n)& =G(v_N+v_S,v_2,\dots ,v_n)=G(v_N,v_2,\dots ,v_n)+G(v_S,v_2,\dots ,v_n)=\\ & =G(v_N)G(v_2,\dots ,v_n)={||v_N||}_2^2\cdot G(v_2,\dots ,v_n)⩽{||v_1||}_2^2\cdot G(v_2,\dots ,v_n).\end{array}$

Другий доданок є нульовим, бо вектори $v_S,v_2,\dots ,v_n$ лінійно залежні. А перший доданок розкладеться в добуток за правилом Лапласа.

Звідси, застосовуючи індукцію, отримуємо необхідний результат.

Матриці Адамара

В комбінаториці матриці з елементами з $\{+1,-1\}$, для яких у нерівності Адамара виконується рівність, називаються матрицями Адамара. Таким чином, визначник таких матриць по модулю дорівнює $n^{\frac{n}{2}}$. З таких матриць отримують коди Адамара.

Джерела

• Шаблон:Гантмахер.Теорія матриць
• R. Bellman, Introduction to Matrix Analysis, SIAM, Philadelphia, PA, USA, Ch. 8, § 7, 1997.
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam, Netherlands, North-Holland, § 2.3, 1977.
• E. F. Beckenbach and R. Bellman, Inequalities, Berlin-Gottingen-Heidelberg, Germany, Ch. 2, § 11, 1961.