положительная полуопределенность

[maxal]

Пусть есть квадратная матрица $A=(a_{ij})$ с целыми элементами.
Как быстрее всего (алгоритмически) определить, является ли эта матрица положительно полуопределенной? Есть ли тут какой-нибудь аналог критерия Сильвестра?

А также верно ли, что:

1) матрица A является положительно полуопределенной тогда и только тогда, когда таковой является симметричная матрица $A+A^T$ ?

2) если симметричная матрица A положительно полуопределена, то

$$\max_{i\ne j} |a_{ij}| < \max_{i} a_{ii}$$

?

[Руст]

maxal писал(а):

Пусть есть квадратная матрица $A=(a_{ij})$ с целыми элементами.
Как быстрее всего (алгоритмически) определить, является ли эта матрица положительно полуопределенной? Есть ли тут какой-нибудь аналог критерия Сильвестра?

А также верно ли, что:

1) матрица A является положительно полуопределенной тогда и только тогда, когда таковой является симметричная матрица $A+A^T$ ?

2) если A положительно полуопределена, то

$$\max_{i\ne j} |a_{ij}| < \max_{i} a_{ii}$$

?

Думаю критерий есть, надо смотреть книги типа Гантмахера.
1) Не сложно показать, что из полуопределённости А следует полуопределённость симметричной части. Обратное неверно.
2) Не верно. Возмите пример матрицы второго порядка, на диагонали которой нули.

[maxal]

Руст писал(а):

1) Не сложно показать, что из полуопределённости А следует полуопределённость симметричной части. Обратное неверно.
2) Не верно. Возмите пример матрицы второго порядка, на диагонали которой нули.

1) Можно увидеть пример, для которого обратное неверно?

2) Забыл указать в пункте 2, что рассматривается симметричная матрица. Для нее пример с нулями на диагонале не работает. Если на диагонали нули, то вся матрица нулевая. Дело в том, что справедливо равенство

$$\max_{i,j} |a_{ij}| = \max_i a_{ii}$$

(см. например), у меня есть подозрение, что это можно усилить до

$$\max_{i\ne j} |a_{ij}| < \max_i a_{ii}$$

(по крайней мере для симметричных положительно определенных матриц это так).

[Руст]

Что понимаете под полуопределённостью? Я понимаю, что действительные части собственных значений неотрицательны. Например матрица a11=0,a12=1,a21=-1,a22=0 имеет собственные значения +-i, соответственно полуопределена (по моему определению). Максимум диагональных элементов 0, максимум недиагональных 1.

[maxal]

Руст писал(а):

Например матрица a11=0,a12=1,a21=-1,a22=0 имеет собственные значения +-i, соответственно полуопределена (по моему определению).

В п.2 речь идет про симметричные полуопределенные матрицы. Матрица a11=0,a12=1,a21=-1,a22=0 таковой не является.

Добавлено спустя 7 минут 35 секунд:

Кстати, 1) верно для матриц с действительными элементами. Если матрица $A+A^T$ положительно полуопределена, то для любого вектора $x$ выполняется $x^T(A+A^T)x=x^T A x + x^T A^T x\geq 0.$ Как нетрудно видеть, $x^T A x = x^T A^T x$, поэтому $x^T A x \geq 0,$ что означает положительную полуопределенность матрицы $A.$

[Руст]

Для симметричных (что не было сказано раньше ) по моему это известный факт.

[maxal]

Руст писал(а):

Для симметричных (что не было сказано раньше ) по моему это известный факт.

Можно ссылочку? Я знаю, это известный факт для симметричных положительно определенных матриц.

Добавлено спустя 1 час 14 минут 38 секунд:

Нет, 2) неверно. Простейший контрпример $\left(\begin{matrix} 1&1\\1&1\end{matrix}\right)$ (или даже нулевая матрица).

[Руст]

Контпример к 1) пусть a11=a22=2, a12=1+5i+y,a21=1+5i-y. Тогда для симметрисованной матрицы собственные значения 3+5i и 1-5i. Взяв y так, чтобы y^2=-32+4i получим, что корни исходного 5+i и -1-i. Т.е. исходная матрица не полуопределена.

[Егор]

Руст писал(а):

Что понимаете под полуопределённостью?

Матрицу $A$ называем положительно полуопределённой, если она порождает неотрицательную квадратичную форму, т. е. $x^T Ax\ge0$ для любого вектора $x$.

maxal писал(а):

Как быстрее всего (алгоритмически) определить, является ли эта матрица положительно полуопределенной? Есть ли тут какой-нибудь аналог критерия Сильвестра?

Здесь удобна такая терминология (не является общепринятой): угловые миноры - стоящие на первых строках и столбцах; главные миноры - стоящие на строках и столбцах с одинаковыми номерами. Симметрическая матрица положительно полуопределена $\Leftrightarrow$ все её главные миноры неотрицательны. Но главных миноров $2^n-1$ штук.

Быстрее привести к диагональному виду, делая одинаковые строчные и столбцовые преобразования (получим матрицу той же квадратичной формы в другом базисе), и посмотреть на диагональные элементы. Если исходные элементы были целыми, то можно все вычисления делать в дробных или даже в целых числах.

maxal писал(а):

1) матрица A является положительно полуопределенной тогда и только тогда, когда таковой является симметричная матрица $A+A^T$ ?

Да. Матрица $A$ порождает ту же квадратичную форму, что и $(A+A^T)/2$, так как антисимметричная матрица $(A-A^T)/2$ порождает нулевую квадратичную форму.

[maxal]

Егор писал(а):

Быстрее привести к диагональному виду, делая одинаковые строчные и столбцовые преобразования (получим матрицу той же квадратичной формы в другом базисе), и посмотреть на диагональные элементы. Если исходные элементы были целыми, то можно все вычисления делать в дробных или даже в целых числах.

Я пока избрал такой путь: вычисляю характеристрический многочлен матрицы, а далее использую систему Штурма для нахождения числа его корней в полуинтервале [0,+oo). Если это число совпадает с размерностью матрицы, то она положительно полуопределена.

[Руст]

maxal писал(а):

Я пока избрал такой путь: вычисляю характеристрический многочлен матрицы, а далее использую систему Штурма для нахождения числа его корней в полуинтервале [0,+oo). Если это число совпадает с размерностью матрицы, то она положительно полуопределена.

Система Штурма дает только количество вещественных корней. Могут быть комплексные корни как с положительной, так и с отрицательной действительной частью.

Вообще все контпримеры приведённые ранее относятся к комплексным матрицам, где транспонирование надо заменить с истинным Эрмитовым сопряжением, для избежания таких нехороших ситуаций.

[maxal]

Руст писал(а):

maxal писал(а):

Я пока избрал такой путь: вычисляю характеристрический многочлен матрицы, а далее использую систему Штурма для нахождения числа его корней в полуинтервале [0,+oo). Если это число совпадает с размерностью матрицы, то она положительно полуопределена.

Система Штурма дает только количество вещественных корней. Могут быть комплексные корни как с положительной, так и с отрицательной действительной частью.

Для симметричных матриц (а имею дело с ними) все корни вещественные.