http://www.pdmi.ras.ru/~lowdimma/topics_nth/Resultants.pdf

두 다항식의 교점이 존재하는지를 알아보는 방법에 관한 내용입니다.

Lecture 10 The Sylvester Resultant

선형 공간에서의 커브 $F = f(x, y) $와 $G = g(x, y)$의 교차 지점을 계산하고 싶다고 합시다. 다시 말하면 bivariate polynomial $f$와 $g$의 common zero를 찾고자 합니다. 만약 $x=\alpha$에 대해서는 F와 G과 교차한다고 하였을 때, $f(\alpha, y)$와 $g(\alpha, y)$가 common zero를 가지는지 여부를 생각해볼 수 있습니다. 여기서는 이를 resultant calculus를 이용하여 대답해볼 것입니다.

10.1 Common Zeros of Univariate Polynomials

$f(x) \in R[x] $, $g(x) \in R[x]$는 실수를 계수로 갖는 univariate polynomial이라고 하여봅시다. 이제 이 둘이 common zero를 갖는지를 알고 싶습니다. 가장 간단한 방법은 f와 g의 gcd(최대공약수)를 구하는 것입니다. 하지만 여기서는 다른 방법을 생각해볼 것입니다. 바로 resultant calculus입니다. 이것은 f와 g간의 common root가 있는지 여부만을 알 수 있고, common root가 어떻게 생겼는지 얼마나 많은지는 알 수가 없습니다. 따라서 resultant는 gcd보다 약한 개념이라 할 수 있습니다. 하지만 multivariate polynomial에서도 사용할 수 있기에 강력합니다.

$f$와 $g$의 common factor가 $h$라고 한다면, $f = (f/h) h $, $g = (g/h)h$로 쓸 수 있습니다. 따라서 아래와 같이 쓸 수 있습니다.

$$f \cdot g/h - f/h \cdot g = 0$$

그리고 $s = g/h$, $t = -f/h$ 라고 놓을 수 있습니다. $s$와 $t$가 0이 아닐 때,

$$0 \leq \deg s \lt \deg g , 0 \leq \deg t \lt \deg f, fs + gt = 0$$

을 만족합니다.

$n= \deg , m = \deg g$라고 한다면, 다음과 같이 쓸 수 있습니다.

$$s = \sum_{0 \leq i \lt m} s_i x^i, t = \sum_{0 \leq i \lt n} t_i x^i$$

이제 새로운 항을 이용하여 표현하여봅시다.

$$P(x) = f(x) s(x) + g(x) t(x)$$

우리는 여기서 $P(x)=0$인 지점을 찾고자 하는 것입니다. 식을 모두 풀어서 각 항을 정리하면 다음을 얻습니다.

$$f_n s_{m-1} + g_m t_{n-1} = 0 \\
f_n s_{m-2} + f_{n-1} s_{m-1} + g_m t_{n-m-2} + g_{m-2} t_{n-m-1} = 0 \\
\vdots \\
f_0 s_0 + g_0 t_0 = 0$$

이를 행렬 식으로 나타낼 수 있습니다.

$$( s_{m-1}, \dots, s_0, t_{n-1}, \dots, t_0 ) Syl(f, g) = 0$$

$$
Syl(f, g) = \begin{bmatrix}
f_n &\ &\ \cdots &\ &\ f_0 &\ &\ \\
&\ \ddots &\ &\ &\ &\ \ddots &\ \\
&\ &\ f_n &\ \cdots &\ &\ &\ f_0 \\
g_m &\ &\ \cdots &\ &\ g_0 &\ &\ \\
&\ \ddots &\ &\ &\ &\ \ddots &\ \\
&\ &\ g_m &\ \cdots &\ &\ &\ g_0
\end{bmatrix}$$

이를 f와 g의 Sylvester 행렬이라고 합니다. n+m개의 행과 열을 갖습니다.

이 행렬이 nontrivial solution을 가지려면 이 행렬의 determinant는 0이 되어야 합니다. 이를 특별히 f와 g의 resultant $ res(f, g)$로 표시합니다.

$$res(f, g) := \det Syl(f, g)$$

이제 우리는 f와 g가 common zero를 가질 조건을 얻었습니다.

10.2 Common Zeros of Bivariate Polynomials

이제 다음 질문으로 넘어가서 bivariate polynomials $ f\in R[x,y], g \in R[x, y]$의 common zero는 어떻게 되는지 생각해봅시다. 식이 단순하다면 치환을 이용해서 간단히 구할 수 있겠지만 대부분 그렇지 않을 것입니다.

먼저 다항식을 y의 계수 형태로 정리하여 봅시다.

$$f(x, y) = \sum_{0 \leq i \lt n} f_i(x) y^i \\
g(x, y) = \sum_{0 \leq i \lt m} g_i(x) y^i$$

여기서 x를 $\alpha$로 치환하여 식을 정리하면 univariate polynomials로 생각할 수 있습니다.

$$f(\alpha, y) = \sum_{0 \leq i \lt n} f_i(\alpha) y^i \\
g(\alpha, y) = \sum_{0 \leq i \lt m} g_i(\alpha) y^i$$

따라서 이 식의 resultant $res_y (f, g)$는 $\alpha$에 대한 polynomial로 정리가 될 것입니다. 이 것에 대해서 다음을 만족합니다.

1. f와 g는 $r(x) = res_y(f, g) = 0$일 때 nontrivial common factor를 갖습니다.
2. $\alpha \in C$가 r의 한 해이고,
3. $f_n(\alpha = g_m(\alpha) = 0$ 이거나 $f(\alpha, \beta) = g(\alpha, \beta) = 0 $인 $\alpha \beta \in C$가 존재하면 common factor를 갖지 않습니다.
4. 모든 $(\alpha, \beta) \in C \times C$가 $f(\alpha, \beta) = g(\alpha, \beta) = 0$ 이면 $r(\alpha) = 0 $입니다.