Журнал вычислительной математики и математической физики, 2020, T. 60, № 1, стр. 109-115

1. ВВЕДЕНИЕ

Рассмотрены вещественные матрицы, элементами которых служат линейные функции нескольких переменных. Вообще говоря, эти функции неоднородные. Наиболее интересен случай, когда матрица симметричная, а число независимых переменных равно порядку матрицы. Такова, например, матрица вторых производных – матрица Гессе – многочлена третьей степени от нескольких переменных. В частности, она полезна при поиске минимума такого многочлена на компактном множестве [1]. Однако не любая симметричная $n \times n$ матрица, элементы которой зависят от $n$ переменных, получается указанным способом. Например, диагональная $2 \times 2$ матрица ${\text{diag}}({{x}_{2}},{{x}_{1}})$ с обратным порядком переменных не служит матрицей Гессе никакого многочлена от двух переменных ${{x}_{1}}$ и ${{x}_{2}}$.

Рассматриваемые матрицы тесно связаны с $3$-тензорами, координатами которых служат числовые коэффициенты в составе матричных элементов. Однако в этой работе рассматриваются такие свойства матриц, которые выполняются при подстановке числовых значений вместо переменных. В частности, будет ли матрица знакоопределенной в некоторой точке? Эти задачи сводятся к задаче о разрешимости системы нелинейных неравенств. Последняя рассматривается во многих работах (см., например, [2]–[4]). Но в типичном случае эта задача имеет высокую вычислительную сложность. С другой стороны, связь этих матриц с $3$-тензорами также полезна для оценки вычислительной сложности; многие такие задачи оказываются $NP$-трудными [5].

Если матрица Гессе многочлена от двух переменных знакоопределена в некоторой точке, то на графике этого многочлена есть эллиптическая точка, в частности, этот график не является линейчатой поверхностью. Это объясняет особый интерес к свойствам матриц Гессе многочленов при моделировании сложных поверхностей для компьютерной графики и систем автоматизированного проектирования [6].

Поиск точки, в которой матрица знакоопределена, тесно связан с задачами полуопределенного программирования – частного случая конического программирования [7]–[10]. С теорией графов связана близкая задача дополнения до симметричной положительно полуопределенной матрицы, у которой фиксированы элементы на главной диагонали и некоторые другие элементы [11]. Также возможно применение полуопределенного программирования для иных комбинаторных задач [12], хотя для алгоритмически трудных задач известна неаппроксимируемость задачей полуопределенного программирования малого размера [13].

Матрицы специального вида, элементами которых служат линейные функции над различными полями, изучались многими авторами. В работах [14]–[16] рассмотрены несимметричные матрицы, элементами которых служат переменные, среди которых могут быть совпадающие; там исследованы свойство нормальности и ранг таких матриц. В работах [17]–[19] рассмотрены матрицы с аффинно независимыми столбцами, элементами которых служат линейные функции, причем никакая переменная не встречается в двух разных столбцах, при условии выполнения данного ограничения на ранг при любых значениях переменных.

Свойства, выполнимые не всегда, но за исключением подмножества малой меры, например, равной нулю, играют важную роль для создания эвристических алгоритмов [20]–[22].

При обсуждении вычислительной сложности можно предполагать, что рассматриваемые линейные функции определены над конечным расширением поля рациональных чисел, вложенном в поле вещественных чисел. Тогда вычисления можно выполнить в пакетах программ для символьных вычислений [23]. Для проверки знакоопределенности симметричной числовой матрицы удобно использовать $LDU$-разложение, вычислимое соответствующей командой в пакете MathPartner. Иначе проверка может быть выполнена непосредственным вычислением угловых миноров. Согласно критерию Сильвестра, симметричная матрица $A$ положительно определена тогда и только тогда, когда все ее угловые миноры ${{\Delta }_{k}}$ положительные. Тогда матрица $ - \;A$ отрицательно определена, а знаки ее угловых миноров чередуются: угловые миноры ${{\Delta }_{{2k}}}$ четного порядка положительные, а угловые миноры ${{\Delta }_{{2k + 1}}}$ нечетного порядка – отрицательные. Определитель матрицы вычислим за полиномиальное время, верхняя оценка которого зависит от сложности матричного умножения. Верхние оценки сложности умножения рассмотрены, например, в недавно опубликованных работах [24]–[27]. С другой стороны, вычислительная сложность операций умножения и деления над конечным расширением основного поля связана со сложностью алгоритма вычисления наибольшего общего делителя многочленов [28].

Для данного множества матриц, элементы которых зависят от параметров ${{\xi }_{1}}$, …, ${{\xi }_{m}}$, некоторое свойство $\Phi ({{\xi }_{1}}, \ldots ,{{\xi }_{m}})$ выполнено для почти каждой матрицы этого множества, если существует такой многочлен $p({{\xi }_{1}}, \ldots ,{{\xi }_{m}})$, не равный тождественно нулю, что для каждого набора значений параметров ${{\xi }_{1}}$, …, ${{\xi }_{m}}$, если свойство $\Phi ({{\xi }_{1}}, \ldots ,{{\xi }_{m}})$ не выполнено, то многочлен обращается в нуль $p({{\xi }_{1}}, \ldots ,{{\xi }_{m}}) = 0$. Свойство, которое выполнено для почти каждого набора значений параметров, не выполняется лишь на нигде не плотном множестве меры нуль. Например, для симметричных $2 \times 2$ матриц

у которых тремя элементами служат независимые параметры ${{\xi }_{1}}$, ${{\xi }_{2}}$ и ${{\xi }_{3}}$, почти каждая матрица невырождена, поскольку на вырожденных матрицах обращается в нуль многочлен $p({{\xi }_{1}},{{\xi }_{2}},{{\xi }_{3}}) = {{\xi }_{1}}{{\xi }_{2}} - \xi _{3}^{2}$. Но в общем случае множество наборов значений, на которых свойство $\Phi $ не выполняется, может быть собственным подмножеством множества нулей многочлена $p$.

Для матриц, элементами которых служат линейные функции от $n$ переменных, набором параметров служит совокупность числовых коэффициентов всех этих функций. В общем случае такая $n \times n$ матрица зависит от ${{n}^{2}}(n + 1)$ независимых параметров. Если дополнительно требовать, что эта матрица симметричная, то она зависит лишь от $\tfrac{1}{2}n{{(n + 1)}^{2}}$ независимых параметров.

Через ${\text{diag}}({{\ell }_{1}}, \ldots ,{{\ell }_{n}})$ обозначается диагональная матрица, у которой элементами главной диагонали служат ${{\ell }_{1}}$, …, ${{\ell }_{n}}$ в указанном порядке. Например, почти каждая $2 \times 2$ матрица вида ${\text{diag}}({{\xi }_{1}}{{x}_{1}} + {{\xi }_{3}},{{\xi }_{2}}{{x}_{2}} + {{\xi }_{4}})$ не равна тождественно нулевой, поскольку это равносильно отличию от нуля значения многочлена $\xi _{1}^{2} + \xi _{2}^{2} + \xi _{3}^{2} + \xi _{4}^{2}$ от параметров ${{\xi }_{1}}$, ${{\xi }_{2}}$, ${{\xi }_{3}}$ и ${{\xi }_{4}}$. Однако почти каждая такая матрица равна нулевой матрице в некоторой точке, поскольку если значение многочлена $\xi _{1}^{2} + \xi _{2}^{2}$ не равно нулю, то координатами этой точки служат числа ${{x}_{1}} = - {{\xi }_{3}}{\text{/}}{{\xi }_{1}}$ и ${{x}_{2}} = - {{\xi }_{4}}{\text{/}}{{\xi }_{2}}$.

2. РЕЗУЛЬТАТЫ

Теорема 1. Для почти каждой $n \times n$ матрицы $A$, элементами которой служат линейные функции от $n$ переменных, существует точка, в которой определитель матрицы $A$ положителен, и существует другая точка, в которой определитель матрицы $A$ отрицателен. То же верно для почти каждой симметричной $n \times n$ матрицы рассматриваемого вида.

Доказательство. В общем случае определитель $det(A)$ не равен нулю тождественно, но обращается в нуль в некоторой точке. Чтобы найти такую точку, достаточно указать точку $P$, в которой все элементы первой строки одновременно обращаются в нуль. Точка $P$ служит решением системы $n$ неоднородных линейных алгебраических уравнений от $n$ неизвестных. В общем случае эта система не вырождена и имеет единственное решение. Действительно, для этого достаточно отличия от нуля определителя вспомогательной $n \times n$ матрицы, составленной из коэффициентов при линейных членах тех функций, которые служат элементами первой строки исходной матрицы $A$. Этот определитель равен многочлену от числовых параметров, определяющих матрицу $A$. Следовательно, для почти каждой матрицы $A$ он отличен от нуля. Поскольку здесь рассматривается лишь одна строка, это рассуждение не меняется при ограничении на симметричные матрицы.

Аналогичное рассуждение показывает, что для почти каждой матрицы $A$ существует такая прямая $L$, проходящая через точку $P$, что в каждой точке прямой $L$ элементы первой строки матрицы $A$ тождественно равны нулю, за исключением первого элемента первой строки. Обозначим через $y$ значение этого элемента. В общем случае, когда $y$ не равен нулю тождественно, значение $y$ определяет точку на прямой $L$. В частности, нулевое значение $y = 0$ соответствует точке $P$. Значение определителя матрицы $A$ в точках на прямой $L$ равно $ydet(B)$, где $(n - 1) \times (n - 1)$ матрица $B$ получается из матрицы $A$ вычеркиванием первой строки и первого столбца. Поскольку матрица $B$ не зависит от элементов первой строки матрицы $A$, то она не зависит от выбора точки $P$ и прямой $L$. Поэтому для почти каждой матрицы $A$ с фиксированной первой строкой подматрица $B$ невырождена в точке $P$. Следовательно, в достаточно малой окрестности точки $P$ на прямой $L$ определитель $det(B)$ отличен от нуля и не меняет знак. Но в этой окрестности определитель $det(A) = ydet(B)$ меняет знак в зависимости от знака $y$. Поэтому в окрестности точки $P$ определитель матрицы $A$ принимает как положительные, так и отрицательные значения. То же самое рассуждение справедливо при ограничении на симметричные матрицы.

Теорема 2. Для почти всех наборов линейных функций ${{\ell }_{0}}$, …, ${{\ell }_{n}}$ от $n$ переменных ${{x}_{1}}$, …, ${{x}_{n}}$ и для любой $n \times n$ матрицы $M$ матрица

знакоопределена в некоторой точке. В частности, почти каждая симметричная $2 \times 2$ матрица, элементами которой служат линейные функции двух переменных, знакоопределена в некоторой точке.

Доказательство. Без ограничения общности можно считать, что никакая из линейных функций ${{\ell }_{0}}$, …, ${{\ell }_{n}}$ не равна линейной комбинации остальных. В противном случае $(n + 1) \times (n + 1)$ матрица их коэффициентов вырождена, то есть равен нулю ее определитель – многочлен степени $n + 1$ от этих коэффициентов. Более того, можно считать, что эти линейные функции суть ${{\ell }_{1}} = {{x}_{1}}$, …, ${{\ell }_{n}} = {{x}_{n}}$ и некоторая ${{\ell }_{0}}({{x}_{1}}, \ldots ,{{x}_{n}})$, которая не обращается в нуль в начале координат. Поскольку гиперплоскость ${{\ell }_{0}} = 0$ не инцидентна началу координат, она содержит либо точку первого ортанта, все координаты которой положительные, либо точку противоположного ортанта, все координаты которой отрицательны. В этой точке матрица ${{\ell }_{0}}M + {\text{diag}}({{x}_{1}}, \ldots ,{{x}_{n}})$ диагональная и знакоопределенная.

Каждая симметричная $2 \times 2$ матрица может быть разложена в сумму ${{\ell }_{0}}{{J}_{2}} + {\text{diag}}({{\ell }_{1}},{{\ell }_{2}})$, где ${{J}_{2}}$ обозначает обменную матрицу

Следующий пример показывает, что распознавание существования точки, в которой матрица из теоремы 2 знакоопределена, не всегда тривиально.

Пример. Рассмотрим зависимую от числового параметра $\mu $ матрицу

Ее определитель равен многочлену $\mu x_{1}^{2} + \mu x_{2}^{2} + (1 + 2\mu ){{x}_{1}}{{x}_{2}}$. Если параметр $\mu > - 1/4$ и значения обеих переменных ${{x}_{1}}$ и ${{x}_{2}}$ равны положительному числу ${{x}_{1}} = {{x}_{2}} > 0$, то матрица положительно определена. Однако если $\mu = - 1$, то определитель равен $ - (x_{1}^{2} + {{x}_{1}}{{x}_{2}} + x_{2}^{2})\;\leqslant \;0$; в этом случае матрица не может быть знакоопределена ни в одной точке.

Замечание 1. В условиях теоремы 2, если линейные функции ${{\ell }_{0}}$, …, ${{\ell }_{n}}$ линейно независимые (то есть никакая из них не равна тождественно линейной комбинации остальных функций с числовыми коэффициентами), то явное вычисление точки, в которой матрица знакоопределена, сводится к решению задачи линейного программирования. Если функции ${{\ell }_{0}}$, …, ${{\ell }_{n}}$ заданы над конечным расширением поля рациональных чисел, то все необходимые вычисления, включая проверку линейной независимости функций, выполнимы за полиномиальное время. Теорема 2 справедлива и для матриц, элементами которых служат линейные функции большего числа переменных, чем порядок матриц.

Теорема 3. Для почти всех наборов линейных функций ${{\ell }_{1}}$, …, ${{\ell }_{n}}$ от $n$ переменных ${{x}_{1}}$, …, ${{x}_{n}}$ и для любой числовой $n \times n$ матрицы $M$ матрица $M + {\text{diag}}({{\ell }_{1}}, \ldots ,{{\ell }_{n}})$ положительно определена в некоторой точке и отрицательно определена в некоторой другой точке.

Доказательство. По аналогии с доказательством теоремы 2, в общем случае для любого числа $\alpha $ система линейных уравнений ${{\ell }_{1}} = \alpha $, …, ${{\ell }_{n}} = \alpha $ имеет решение. Для достаточно больших значений числа $\alpha $ в точке, соответствующей решению, получается матрица с диагональным преобладанием. Следовательно, она положительно определена. При отрицательных значениях числа $\alpha $ с достаточно большим абсолютным значением соответствующая числовая матрица отрицательно определена.

Теорема 4. Для всех троек линейных функций ${{\ell }_{0}}$, ${{\ell }_{1}}$ и ${{\ell }_{2}}$ от двух переменных ${{x}_{1}}$ и ${{x}_{2}}$, если ${{\ell }_{0}}(0,0) \ne 0$, то симметричная $3 \times 3$ матрица

знакоопределена в некоторой точке.

Доказательство. Покажем, что существуют значения переменных ${{x}_{1}}$ и ${{x}_{2}}$, при которых второй угловой минор ${{\Delta }_{2}} = {{x}_{1}}{{x}_{2}} - \ell _{0}^{2}$ положительный. Возможны два случая. Если ${{\ell }_{0}}$ не равна тождественно константе, то система двух уравнений ${{\ell }_{0}} = 0$, ${{x}_{1}} = {{x}_{2}}$ имеет ненулевое решение, поскольку $\ell (0,0) \ne 0$. При этих значениях переменных минор ${{\Delta }_{2}}$ положительный. Если ${{\ell }_{0}}$ тождественно равна константе, то ${{\Delta }_{2}}$ положительный при всех достаточно больших значениях переменных ${{x}_{1}}$ и ${{x}_{2}}$.

Если так выбранные значения обеих переменных ${{x}_{1}}$ и ${{x}_{2}}$ положительные, то при достаточно больших значениях ${{x}_{3}}$ определитель матрицы тоже положительный. Согласно критерию Сильвестра, матрица положительно определена. Аналогично, если значения обеих переменных ${{x}_{1}}$ и ${{x}_{2}}$ отрицательные, то при отрицательном значении ${{x}_{3}}$ (достаточно большом по абсолютной величине) определитель матрицы отрицательный; матрица отрицательно определена.

Замечание 2. В теореме 4 условие неоднородности линейной функции ${{\ell }_{0}}$ существенно.

Пример 1. Ни в какой точке симметричная $3 \times 3$ матрица

не является знакоопределенной, поскольку второй угловой минор, равный ${{\Delta }_{2}} = - (x_{1}^{2} + {{x}_{1}}{{x}_{2}} + x_{2}^{2})$, не бывает положительным. Но в точках прямой, заданной уравнениями ${{x}_{1}} = {{x}_{2}} = 0$, эта матрица полуопределена. Она положительно полуопределена при ${{x}_{3}} > 0$ и отрицательно полуопределена при ${{x}_{3}} < 0$. Для любой матрицы, элементами которой служат однородные линейные функции, все элементы обращаются в нуль в начале координат, то есть матрица полуопределена.

Линейная независимость элементов на главной диагонали матрицы также упрощает поиск точки, в которой матрица полуопределена. Иначе такой точки может не быть даже для диагональных матриц.

Пример 2. Диагональная $3 \times 3$ матрица ${\text{diag}}({{x}_{1}},{{x}_{1}} + 2, - {{x}_{1}} - 1)$, элементы которой зависят только от одной переменной ${{x}_{1}}$, не бывает полуопределена ни в какой точке. Поэтому для любых функций ${{\ell }_{0}}$, ${{\ell }_{1}}$ и ${{\ell }_{2}}$ от любого числа переменных симметричная $3 \times 3$ матрица

тоже не бывает полуопределена ни в какой точке.

С другой стороны, диагональная матрица ${\text{diag}}({{x}_{1}},{{x}_{1}} + 2, - {{x}_{1}} - 1)$ служит пределом при $k \to \infty $ последовательности диагональных матриц

каждая из которых положительно определена в точке $(1,0,3k)$ и отрицательно определена в точке $( - 1, - 2k,0)$.

Аналогично, любая постоянная матрица $M$ служит пределом при $k \to \infty $ последовательности матриц $M + \tfrac{1}{k}{\text{diag}}({{x}_{1}}, \ldots ,{{x}_{1}})$, элементы которых зависят от одной переменной, каждая из которых положительно определена в некоторой точке и отрицательно определена в некоторой другой точке.

3. ОБСУЖДЕНИЕ

Задача полуопределенного программирования заключается в оптимизации линейного функционала на пересечении аффинного пространства и выпуклого конуса положительно полуопределенных матриц. Метод внутренней точки часто оказывается эффективным для решения этой задачи, но предполагает знание начальной точки из допустимой области. Полученные результаты позволяют установить существование такой точки для некоторых случаев. Более того, доказательства теорем 2 и 3 конструктивные, то есть в предположении общности из условий этих теорем легко вычислить за полиномиальное число арифметических операций такую точку, в которой матрица знакоопределена. С другой стороны, в общем случае теорема 2 не гарантирует, что существует точка, в которой матрица положительно полуопределена.

Из теоремы 1 следует, что почти каждая матрица, элементами которой служат линейные функции от достаточно большого числа переменных, не может быть знакоопределена в каждой точке. В частности, если такая матрица положительно определена в некоторой точке, то найдется другая точка, в которой она положительно полуопределена, но не определена.

Рассмотрим матрицы Гессе многочленов третьей степени. Для многочленов от двух переменных это симметричные $2 \times 2$ матрицы, для которых применима теорема 2. То есть для почти каждого такого многочлена найдется точка, в которой его матрица Гессе знакоопределена. Следовательно, для почти каждого многочлена третьей степени от двух переменных его график содержит эллиптическую точку. В частности, почти никакие из этих поверхностей не являются линейчатыми. Хотя именно линейчатые поверхности играют важную роль для моделирования сложных поверхностей. Если графиком многочлена служит линейчатая поверхность, то матрица Гессе этого многочлена полуопределена в каждой точке. С другой стороны, обезьянье седло служит примером графика многочлена третьей степени, не имеющего эллиптической точки и не являющегося линейчатой поверхностью. В этом случае матрица Гессе соответствующего многочлена становится нулевой в некоторой точке.

В общем случае, для многочленов третьей степени от трех переменных линейная замена переменных приводит матрицу Гессе к виду

где ${{\ell }_{0}}({{y}_{1}},{{y}_{2}},{{y}_{3}})$ – линейная функция, а $M$ и $C$ – симметричные числовые $3 \times 3$ матрицы. Это следует из разложимости кубической формы от трех переменных в сумму не более четырех кубов линейных форм [29]. Если матрица $C$ диагональная, то для доказательства существования точки, в которой матрица знакоопределена, применима теорема 2. Если матрица $M$ диагональная, то применима теорема 3. Если функция ${{\ell }_{0}}$ зависит лишь от значений переменных ${{y}_{1}}$ и ${{y}_{2}}$, то применима теорема 4.

Для почти всех многочленов вида

где каждая из линейных функций ${{\ell }_{0}}$, …, ${{\ell }_{n}}$ зависит от $n$ переменных, а $\lambda $ и $\mu $ – это некоторые числа, в результате невырожденного линейного преобразования координат получается многочлен, у которого матрица Гессе удовлетворяет условиям одной из теорем 2 или 3. Однако если число переменных $n$ больше двух, то не любой многочлен третьей степени представим в таком виде [29].

Для упрощения обозначений рассмотрим многочлены вида

Существует линейная функция $m({{x}_{1}}, \ldots ,{{x}_{n}})$, для которой вторые частные производные многочлена $f$ равны где ${{\delta }_{{kk}}} = 1$ и если $j \ne k$, то ${{\delta }_{{jk}}} = 0$. Если $m$ – это ненулевая константа, применима теорема 3. Иначе, если $m(0, \ldots ,0) \ne 0$, то применима теорема 2. В этих случаях матрица Гессе знакоопределена в некоторой точке. И лишь в случае $m(0, \ldots ,0) = 0$ такой точки может не быть. Однако если $m(0, \ldots ,0) = 0$, то все элементы матрицы Гессе обращаются в нуль в начале координат. Следовательно, для любого многочлена рассматриваемого вида матрица Гессе полуопределена в некоторой точке.

Автор благодарит рецензента за сделанные замечания.