18 мая 2022 в 21:07

Почему у 2 окружностей 4 точки пересечения?

Математика * Профессиональная литература *

Ожидает приглашения

К сожалению, линейная алгебра не пользуется той популярностью, которую она заслужила. Многие из моих знакомых не уделяют ей должного внимания на первых курсах полагая, что больше она им не пригодиться, и на самом деле очень зря. Многие алгоритмы заимствуют линейно-алгебраические идеи, и я надеюсь, что когда-нибудь я сделаю такую подборку, но в этот раз я расскажу о теме, с информатикой никак не связанной - теореме Безу.

Начнем мы издалека, с определения матрицы Сильвестра и результанта. Пусть есть два многочлена P(x) и Q(x).

$P(x) = a_nx^n + a_{n-1}x^{n-1}+\cdots+a_0\\Q(x) =b_mx^m+b_{m-1}x^{m-1}+\cdots+b_0$

Тогда их матрицей Сильвестра называется матрица размера nm

$S_{P,Q} = \begin{bmatrix} a_n & a_{n-1} & a_{n-2} & \cdots & \cdots & a_0 & 0 & \cdots & 0\\ 0 & a_n & a_{n-1} & a_{n-2} & \cdots & a_1 & a_0 & \cdots & 0\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots\\ 0 & \cdots & 0 & a_n & a_{n-1} & a_{n-2} & \cdots & a_1 & a_0\\ b_m & b_{m-1} & \cdots & \cdots & b_0 & 0 & \cdots & \cdots & 0\\ 0 & b_m & \cdots & \cdots & b_1 & b_0 & 0 & \cdots & 0\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots\\ 0 & \cdots & \cdots & \cdots & 0 & b_m & \cdots & b_1 & b_0 \end{bmatrix}$

То-есть в ее верхней строчке стоят коэфициенты P, а на следующих m-1 строках они сдвигаются на одну позицию вправо. На m+1-й строке записаны коэфициенты Q, которые тоже сдвигаются вправо на следующих n-1-й строках.

Матрица Сильвестра замечательна тем, что она позволяет найти, есть ли у P и Q общий множитель. Несложно показать, что

$\exists H\in\mathbb{F}[x]:H|P, H|Q \Leftrightarrow\exists S,T\in\mathbb{F}[x]: (deg\: S<deg\:Q) \wedge (PS+QT = 0)$

Докажем следствие влево. Пусть НОД P и Q равен 1. Тогда

$PS+QT=0\implies Q|PS.\\Если\; (P,Q)= 1, то \; Q|S, но\ deg\:S < deg\:Q$

И в другую сторону

$P=HP_1,\ Q=HQ_1.\\ Тогда\ возьмем \ S:=Q_1, T:=-P_1\\PS+QT=HP_1Q_1+HQ_1(-P_1)=0$

Попробуем найти эти S и T методом неопределенных коэфициентов:

$S=b'_{m-1}x^{m-1}+b'_{m-2}x^{m-2}+\cdots+b'_0\\ P = a'_{n-1}x^{n-1}+a'_{n-2}x^{n-2}+\cdots+a'_0$

Тогда посчитаем, чему равны коэфициенты PS

$c_{m+n-1}=a_nb_{m-1}\\ c_{m+n-2}=a_nb_{m-2} + a_{n-1}b_{m-1}\\ c_{m+n-3}=a_nb_{m-3}+a_{n-1}b_{m-2}+a_{n-2}b_{m-1}\\\cdots\\c_n = a_nb_0 + a_{n-1}b_1+\cdots+a_{n-m+1}b_{m-1}\\c_{n-1}=a_{n-1}b_0 + a_{n-2}b_1+\cdots+a_{n-m}b_{m-1}\\\cdots$

Если присмотреться к этим выражениям, можно заметить, что их можно записать в матричном виде

$\begin{bmatrix}c_{m+n-1} &\cdots & c_0\end{bmatrix}=\begin{bmatrix}b'_{m-1}&b'_{m-2}&\cdots&b'_0\end{bmatrix}\begin{bmatrix}a_n & a_{n-1} & \cdots & a_0 & \cdots & 0\\0 & a_n & a_{n-1} & \cdots & a_0 & \cdots\\\cdots & \cdots & \cdots & \cdots & \cdots & \cdots\end{bmatrix}$

То-есть строка коэфициентов S умножается на верхнюю часть матрицы Сильвестра. Значит строку коэфициентов PS+QT можно выразить как

$\begin{bmatrix}b'_{m-1}&b'_{m-2}&\cdots & b'_{0}& a'_{n-1} & a'_{n-2}&\cdots&a'_0\end{bmatrix}S_{P,Q}$

Значит матрицу Сильвестра можно рассматривать как транспонированную матрицу линейного уравнения. Так как мы хотим, чтобы PS+QT=0, уравнение это однородно, а значит имеет ненулевое решение если и только если матрица вырождена, т.е. ее определитель не равен 0.

Определитель матрицы Сильвестра называется результантом двух многочленов. Теперь мы можем перейти к самой теореме Безу.

Пусть на плоскости даны две кривые, которые задаются многочленами P и Q степеней m и n. Тогда либо у этих двух многочленов есть общий множитель, и кривые пересекаются по бесконечному числу точек, либо у них не больше nm точек перечечения.

Рассмотрим наши кривые на проективной плоскости. Тогда пусть P', Q' - однородные многочлены от 3 переменных, которые задают наши кривые. Вынесем z за скобки

$P'(x,y,z) = P_0(x,y)z^n + P_{1}(x,y)z^{n-1}+\cdots+P_n(x,y)\\Q'(x,y,z) = Q_0(x,y)z^m+Q_1(x,y)z^{m-1}+\cdots+Q_m(x,y)$

Теперь мы можем записать матрицу Сильвестра над полем рациональных функций от 2 переменных. Не сложно показать, что ее определитель - тоже однородный многочлен от x и y, причем его степень - в точности mn или 0. Но если результант P' и Q' - нулевой многочлен, то у них есть общий множитель. В противном случае, у их результанта ровно nm решений с учетом кратности над полем комплексных чисел, с точностью до пропорциональности. (Нетрудно доказать, что над алгебраически замкнутым полем однородный многочлен степени n от двух переменных имеет ровно n пар решений, с учетом пропорциональности).

Вот так, получается, что любые 2 окружности действительно пересекаются по 4 точкам, правда на комплексной проективной плоскости.

P.S. Это доказательство - всего лишь несколько более подробно расписанное доказательство из Википедии, но моей целью было продемонстрировать два красивых метода - рассмотрение определителя матрицы из рациональных функций и переход от афинного пространства к проективному. На самом деле эта тема неразрывно связана с конечными проективными плоскостями, и в следующий раз я расскажу о том, как считать число направлений, задаваемых на них набором точек.

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

Хабы: