[현대대수학] Sylvester 행렬과 Resultant

다항식의 공통 근

두 다항식 $f, g$가 주어질 때 공통 근이 존재하는지 판단하려면 어떻게 해야 할까? 가장 쉬운 방법은 각각의 근을 모두 구하고 겹치는게 있는지 확인하는 것이다. 하지만 이는 2차 다항식까지는 근의 공식으로 편리하게 확인할 수 있지만 3차 이상으로 올라가게 되면 자명한 근 아니면 찾기 힘들어진다. 한 번 알 방법이 있는지 알아보자.

 

다항식이 공통 근을 가지려면..

$r$차 다항식 $f(x) = a_r x^r + a_{r-1} x^{r-1} + ... + a_1 x + a_0$과 $s$차 다항식 $g(x) = b_s x^s + b_{s-1} x^{s-1} + ... + b_1x^1 + b_0$이 있다. 다항식이 어떤 근 $\alpha$를 가진다는 것은 $x-\alpha$를 인수로 가진다는 뜻이다. 즉, $f(\alpha) = 0$과 $f(x) = (x - \alpha) (...)$은 같은 뜻이다.

그렇다면 공통 근을 가지려면 $f(\alpha) = 0, g(\alpha) = 0$이므로 두 다항식 모두 $x-\alpha$를 인수로 가져야 한다.

$f(x) = (x-\alpha)u(x), g(x) = (x-\alpha)v(x)$라고 정의하고 다음과 같은 항등식을 생각해보자. $f(x)g(x) = g(x)f(x)$

위 항등식은 다음과 같이 쓸 수 있다. $(x-\alpha)u(x)g(x) = (x-\alpha)v(x)f(x)$

$x \neq \alpha$라면 양 변을 나누어 $u(x)g(x) = v(x)f(x)$라고 쓸 수 있다. 다항식 $u, v$가 모든 공통근을 제거한 서로소 다항식이라고 하자. $\deg(u) < r, \deg(v) < s$인 다항식 $u, v$가 존재한다면 $f, g$는 공통 근을 가진다고 말할 수 있을 것이다. ($\deg(f)$는 $f$의 차수)

 

$u$는 아직 뭔진 모르지만 $\deg(u) < \deg(f) = r$이라는 정보만 가지고 있다. 그렇다면 $u$의 최대 차수는 $r-1$일 것이므로 $u(x) = c_{r-1} x^{r-1} + ... + c_1x^1 + c_0$으로 둘 수 있다. 이제 위에서 본 좌변 $u(x)g(x)$를 계산해보자.

$u(x)g(x) = \textcolor{red}{c_{r-1}} \textcolor{blue}{b_s} x^{r-1 + s} + \textcolor{red}{c_{r-1}}\textcolor{blue}{b_{s-1}}x^{r+s-2} + ... + \textcolor{red}{c_{r-1}}\textcolor{blue}{b_{1}}x^{r-1+1} + \textcolor{red}{c_{r-1}}\textcolor{blue}{b_0}x^{r-1}$

$+\textcolor{red}{c_{r-2}} \textcolor{blue}{b_s} x^{r-2 + s} + \textcolor{red}{c_{r-2}}\textcolor{blue}{b_{s-1}}x^{r+s-3} + ... + \textcolor{red}{c_{r-2}}\textcolor{blue}{b_{1}}x^{r-2+1} + \textcolor{red}{c_{r-2}}\textcolor{blue}{b_0}x^{r-2}$

$+...$

$+\textcolor{red}{c_0} \textcolor{blue}{b_s} x^{s} + \textcolor{red}{c_0}\textcolor{blue}{b_{s-1}}x^{s-1} + ... + \textcolor{red}{c_0}\textcolor{blue}{b_{1}}x + \textcolor{red}{c_0}\textcolor{blue}{b_0}$

보기 힘드니 행렬 표현식으로 바꿔보자.

$\begin{pmatrix} c_{r-1} & c_{r-2} & ... & c_1 & c_0 \end{pmatrix} \begin{pmatrix} b_s & b_{s-1} & ... & b_1 & b_0 & 0 & ... & 0 \\ 0 & b_s & b_{s-1} & ... & b_1 & b_0 & ... & 0 \\ ... \\ 0& ... & 0 & b_s & b_{s-1} & ... & b_1 & b_0 \end{pmatrix} \begin{pmatrix} x^{r+s - 1} \\ x^{r + s - 2} \\ ... \\ x \\ 1 \end{pmatrix}$

각 행렬을 $u(x)g(x) = CBX$라고 나타내자.

마찬가지로 $v(x)f(x)$도 위와 같이 나타낼 수 있다. 

$\begin{pmatrix} d_{s-1} & d_{s-2} & ... & d_1 & d_0 \end{pmatrix} \begin{pmatrix} a_r & a_{r-1} & ... & a_1 & a_0 & 0 & ... & 0 \\ 0 & a_r & a_{r-1} & ... & a_1 & a_0 & ... & 0 \\ ... \\ 0& ... & 0 & a_r & a_{r-1} & ... & a_1 & a_0 \end{pmatrix} \begin{pmatrix} x^{r+s - 1} \\ x^{r + s - 2} \\ ... \\ x \\ 1 \end{pmatrix}$

이 행렬들도 마찬가지로 $v(x)f(x) = DAX$라고 하자.

$B$는 $r \times (r+s)$차원, $A$는 $s \times (r+s)$차원을 가짐에 주목하자.

 

돌아와서 다항식의 근을 가지려면 $u(x)g(x) = v(x)f(x)$인 $u, v$가 존재해야 했다. 

우리는 행렬을 얻었으므로 $CBX = DAX$이고 $CBX - DAX = (CB-DA)X = 0$인 선형 연립방정식의 해를 구하면 된다. 여기서 $X$는 해에 영향을 주지 않으므로 $CB - DA  = 0$이면 된다.

 

Sylvester 행렬

이제 위 행렬방정식이 근을 가지려면 어떻게 해야 할까? 위 행렬방정식을 잘 정리하면 $\begin{pmatrix} C & -D \end{pmatrix} \begin{pmatrix} B \\ A \end{pmatrix}$로 나타낼 수 있다.

각 행렬을 또 다시 $U, V$라고 하자. 여기서 $U$의 차원은 $1 \times (r+s)$, $V$의 차원은 $(r+s) \times (r+s)$가 된다. 정사각행렬이 된 것이 흥미롭다.

다항식 $u, v$는 $0$이 아니므로 $U$의 원소가 모두 $0$이 될 수 없다. 즉, 최종 행렬방정식 $UV = 0$이 되기 위해서는 $V$에 의존하게 되는데 우리는 이미 $\det(V) = 0$일 때 해를 가진다는 것을 알고 있다. 그리고 $V$는 정사각행렬이므로 행렬식도 계산할 수 있다. 미지수행렬이 앞에 있어 헷갈린다면 $(UV)^T = V^TU^T = 0$, $\det(V^T) = \det(V) = 0$을 생각하면 된다.

 

결론은 우리의 다항식 $f, g$가 공통근을 가지는지 확인하려면 $\det(V) = 0$인지 확인하면 되고 행렬 $V$는 $f, g$의 계수들로만 이루어져 있어 쉽게 구할 수 있다. 여기에서 구한 행렬 $V$를 실베스터 행렬(Sylvester matrix) 이라고 한다.

 

Resultant

위에서 구한 실베스터 행렬의 행렬식 값을 두 다항식의 종결식(Resultant)라고 하고, $Res(f, g, x) = \det(V)$로 나타낸다. 즉, 두 다항식 $f, g$이 공통 근을 가지는지 확인하려면 $Res(f, g, x) = 0$인지 확인하는 것과 같다.

Resultant의 다양한 특성이 있지만 여기에서는 "Sylvester행렬의 행렬식이다."정도로만 정의하고 넘어가자.

 

예시

위에서 수식과 변수가 너무 많아서 보기 힘들다. 간단한 예시를 들어 Sylvester행렬이 어떻게 생겼는지 알아보자.

Q. $f(x) = x^2 + x - 2, g(x) = x^3 - 2x^2 + 4x - 3$이 공통 근을 가지는지 확인하시오.

공통근을 가진다면 $u(x)g(x) = v(x)f(x)$인 두 서로소인 다항식 $u, v$가 존재한다. 

$\deg(u) < \deg(f) = 2, \deg(v) < \deg(g) = 3$이므로 $u(x) = c_1x + c_0, v(x) = d_2x^2 + d_1x + d_0$

$u(x)g(x) = \begin{pmatrix} c_1 & c_0 \end{pmatrix} \begin{pmatrix} 1 & -2 & 4 & -3 & 0 \\ 0 & 1 & -2 & 4 & -3 \end{pmatrix} \begin{pmatrix} x^4 \\ x^3 \\ x^2 \\ x \\ 1 \end{pmatrix}$

$v(x)f(x) = \begin{pmatrix} d_2 & d_1 & d_0 \end{pmatrix} \begin{pmatrix} 1 & 1 & -2 & 0 & 0  \\ 0 & 1 & 1 & -2 & 0 \\ 0 & 0 & 1 & 1 & -2 \end{pmatrix} \begin{pmatrix} x^4 \\ x^3 \\ x^2 \\ x \\ 1 \end{pmatrix}$

이제 행렬을 한쪽으로 잘 모으고 위에서 본 기호로 나타내면 $UV = \begin{pmatrix} c_1 & c_0 & -d_2 & -d_1 & -d_0 \end{pmatrix} \begin{pmatrix} 1 & -2 & 4 & -3 & 0 \\ 0 & 1 & -2 & 4 & -3 \\ 1 & 1 & -2 & 0 & 0 \\ 0 & 1 & 1 & -2 & 0 \\ 0 & 0 & 1 & 1 & -2 \end{pmatrix}$가 된다. 

 

$UV = 0$일 조건은 $\det(V) = 0$인데 실제로 행렬식을 계산해보면 0이 나오고 $1$을 공통근으로 가지는 것을 확인할 수 있다.

 

References

https://www.youtube.com/watch?v=WBJEhVeA0hE 

https://www.youtube.com/watch?v=qIhq1K4FBqk