맨위로가기

뉴턴 항등식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

뉴턴 항등식은 대칭 다항식의 일종인 멱합 다항식과 기본 대칭 다항식 사이의 관계를 나타내는 공식이다. 이 항등식은 다항식의 근과 계수와의 관계, 행렬의 특성 다항식, 갈루아 이론 등 다양한 분야에 응용되며, 기본 대칭 다항식을 거듭제곱 합 대칭 다항식으로 표현하거나 그 반대로 표현하는 데 사용된다. 뉴턴 항등식은 급수의 계수 비교, 조합론적 증명 등 다양한 방법으로 증명할 수 있으며, 행렬의 특성 다항식을 계산하는 파데예프-르베리에 알고리즘에 활용되기도 한다.

더 읽어볼만한 페이지

  • 대수적 조합론 - 유한환
    유한환은 유한 집합인 환, 유사환, 가환환, 가환 유사환을 통칭하는 용어이며, 모든 유한환은 뇌터 환이자 아르틴 환이고, 유한체 이론은 유한환 이론의 중요한 측면이다.
  • 대수적 조합론 - 근접 대수
    국소 유한 부분 순서 집합 위의 폐구간에서 정의된 함수들의 대수 구조인 근접 대수는 가환환 R에 대하여 P 속의 폐구간에서 R로 가는 함수들의 집합으로 정의되며, 뫼비우스 반전 공식은 근접 대수의 중요한 응용 중 하나이다.
  • 갈루아 이론 - 갈루아 군
    갈루아 군은 체의 확대에 대한 자기 동형군으로, 갈루아 이론의 기본 정리에 따라 체론과 군론을 연결하며, 사유한군 구조를 가지고 갈루아 코호몰로지와 관련된다.
  • 갈루아 이론 - 프로베니우스 사상
    표수가 소수 p인 가환환 R에서 프로베니우스 사상은 r을 r^p로 보내는 환 준동형으로, 환의 표수가 p인 환의 범주에 대한 항등 함자에서 자체로의 자연 변환을 나타내며, 체 K가 표수가 0이거나 양의 표수를 갖고 프로베니우스 사상이 자기 동형 사상인 경우 완전체라고 한다.
  • 아이작 뉴턴 - 만유인력의 법칙
    만유인력의 법칙은 모든 질량을 가진 물체들이 서로를 끌어당기는 힘에 대한 법칙으로, 뉴턴은 질량에 비례하고 거리의 제곱에 반비례한다는 것을 제시했으며, 케플러의 행성 운동 법칙을 설명하고 뉴턴 역학의 기초가 되었으나, 일반 상대성 이론이 등장하면서 저중력 한계로 여겨진다.
  • 아이작 뉴턴 - 뉴턴의 냉각 법칙
    뉴턴의 냉각 법칙은 물체의 열 손실률이 물체와 주변 환경 간의 온도 차이에 비례하며, 과도 냉각 분석에 활용된다.
뉴턴 항등식
개요
유형항등식
분야대수학
이름뉴턴 항등식
다른 이름뉴턴-지라르 공식
뉴턴-워링 공식
명명자아이작 뉴턴
알베르 지라르
관련 개념
관련 개념대칭 다항식
기본 대칭 다항식
멱합 대칭 다항식
공식
변수x₁, x₂, ..., xₙ
멱합pₖ = x₁ᵏ + x₂ᵏ + ... + xₙᵏ
기본 대칭 함수eₖ = Σᵢ₁<ᵢ₂<...<ᵢₖ xᵢ₁xᵢ₂...xᵢₖ
공식 (k ≥ 1)k ⋅ eₖ = Σᵢ=1ᵏ (-1)ⁱ⁻¹ eₖ₋ᵢ pᵢ
공식 (k ≥ n + 1)0 = Σᵢ=1ⁿ (-1)ⁱ⁻¹ eₖ₋ᵢ pᵢ

2. 대칭 다항식

임의의 대칭다항식이 기본 대칭다항식의 다항식으로 표현되듯이, 멱합 다항식도 그러하다. 뉴턴 항등식은 멱합을 기본대칭식으로 표현하는 재귀적인 방법을 제시한다.

:- s_k = - \sigma_1s_{k-1} + \sigma_2 s_{k-2} - \cdots + (-1)^{k-1}\sigma_{k-1}s_1 + (-1)^k k \sigma_k

우변은 마지막 항을 제외하면 규칙적이다. k > n이면, 뒤에 오는 몇 항이 소실되므로

:- s_k = - \sigma_1s_{k-1} + \sigma_2s_{k-2} - \cdots + (-1)^n\sigma_ns_{k-n}

이 성립한다.

2. 1. 멱합 다항식

멱합 다항식은 변수들의 거듭제곱 합으로 이루어진 대칭다항식이다. n개의 변수 x₁, x₂, ..., xₙ에 대한 k차 멱합 다항식 sₖ는 다음과 같이 정의된다.

:s_0 = n

:s_1 = x_1 + \cdots + x_n

:s_2 = x_1^2 + \cdots + x_n^2

:\cdots

변수 ''x''1, ..., ''x''''n''이 주어졌을 때, ''k'' ≥ 1에 대해 ''p''''k''(''x''1, ..., ''x''''n'')을 ''k''번째 거듭제곱합으로 나타내면 다음과 같다.

:p_k(x_1,\ldots,x_n)=\sum_{i=1}^n x_i^k = x_1^k+\cdots+x_n^k

2. 2. 기본 대칭 다항식

기본 대칭 다항식(elementary symmetric polynomial)은 주어진 변수들로 만들 수 있는 모든 서로 다른 곱들의 합으로 이루어진다. n개의 변수 x₁, x₂, ..., xₙ에 대한 k차 기본 대칭 다항식 σₖ는 다음과 같이 정의된다.[1]

식설명
σ₀ = 10개의 변수를 곱한 경우 (정의)
σ₁ = x₁ + x₂ + ... + xₙ1개의 변수를 곱한 모든 경우의 합
σₙ = x₁x₂...xₙn개의 변수를 모두 곱한 경우
σₖ (k > n) = 0n보다 많은 변수를 곱할 수 없으므로 0



예를 들어, σ₂는 x₁, x₂, ..., xₙ 중 서로 다른 두 변수를 곱한 모든 항들의 합이다. 기본 대칭 다항식은 x₁, ..., xₙ을 근으로 하는 다항식의 계수로부터 유도된다.

:\prod_{i=1}^n (x - x_i) = \sum_{k=0}^n (-1)^k\sigma_k x^{n-k}

3. 뉴턴 항등식

뉴턴 항등식은 멱합 다항식과 기본 대칭 다항식 사이의 관계를 나타내는 재귀적인 공식이다. 임의의 대칭다항식은 기본대칭다항식의 다항식으로 표현될 수 있으며, 멱합 다항식 또한 마찬가지이다. 뉴턴 항등식은 멱합을 기본대칭식으로 표현하는 재귀적인 방법을 제시한다.[1]

변수 ''x''1, ..., ''x''''n''이 주어졌을 때, ''k'' ≥ 1에 대해 ''p''''k''(''x''1, ..., ''x''''n'')를 ''k''번째 거듭제곱합으로, ''k'' ≥ 0에 대해 ''e''''k''(''x''1, ..., ''x''''n'')을 기본 대칭 다항식으로 나타내면 다음과 같다.

:p_k(x_1,\ldots,x_n)=\sum_{i=1}^n x_i^k = x_1^k+\cdots+x_n^k,

:\begin{align}

e_0(x_1, \ldots, x_n) &= 1,\\

e_1(x_1, \ldots, x_n) &= x_1 + x_2 + \cdots + x_n,\\

e_2(x_1,\ldots,x_n) &= \sum_{1 \leq i
&\;\;\vdots \\

e_n(x_1, \ldots, x_n) &= x_1 x_2 \cdots x_n,\\

e_k(x_1, \ldots, x_n) &= 0, \quad\text{for}\ k>n.\\

\end{align}

뉴턴 항등식은 다음과 같이 나타낼 수 있다.

: ke_k(x_1,\ldots,x_n) = \sum_{i=1}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), (''n'' ≥ ''k'' ≥ 1)

: 0 = \sum_{i=k-n}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), (''k'' > ''n'' ≥ 1)

이 방정식들은 변수의 개수 ''n''에 의존하지 않으며, 대칭 함수환의 항등식으로 나타낼 수 있다. ''e''''i''를 ''p''''k''로, 또는 그 반대로 재귀적으로 표현할 수 있다.

다항식의 근과 계수와의 관계에서, 근의 멱합이 주어지면 뉴턴 항등식을 사용하여 다항식의 계수를 재귀적으로 표현할 수 있다. 이는 Delves와 Lyness의 방법[1]을 사용하여 해석 함수의 영점을 찾는 데 유용하다.

뉴턴 항등식은 기본 대칭 다항식 ek(x1,...,xn)가 xi에 관한 대칭식의 대수적 기저를 형성한다는 것을 보여준다. 즉, xi의 모든 치환에 대해 불변인 다항식은 기본 대칭식으로 표현된다. 이는 갈루아 이론의 일반적인 결과와도 연결된다.

결론적으로, 뉴턴 항등식은 대칭 다항식 이론에서 중요한 역할을 하며, 다양한 분야에서 응용될 수 있는 유용한 도구이다.

3. 1. 기본 공식

Newton영어 항등식은 멱합 다항식을 기본 대칭 다항식으로 표현하거나, 반대로 기본 대칭 다항식을 멱합 다항식으로 표현하는 재귀적인 방법을 제시한다.

  • k \le n인 경우, 뉴턴 항등식은 다음과 같다.


: ke_k(x_1,\ldots,x_n) = \sum_{i=1}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n),

  • k > n인 경우, 뉴턴 항등식은 다음과 같다.


: 0 = \sum_{i=k-n}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n),

여기서 p_k(x_1,\ldots,x_n)은 k번째 거듭제곱합이고, e_k(x_1, \ldots, x_n)은 기본 대칭 다항식이다.

:p_k(x_1,\ldots,x_n)=\sum_{i=1}^n x_i^k = x_1^k+\cdots+x_n^k,

:\begin{align}

e_0(x_1, \ldots, x_n) &= 1,\\

e_1(x_1, \ldots, x_n) &= x_1 + x_2 + \cdots + x_n,\\

e_2(x_1,\ldots,x_n) &= \sum_{1 \leq i
&\;\;\vdots \\

e_n(x_1, \ldots, x_n) &= x_1 x_2 \cdots x_n,\\

e_k(x_1, \ldots, x_n) &= 0, \quad\text{for}\ k>n.\\

\end{align}

구체적으로, 처음 몇 개의 k 값에 대해 다음과 같은 식을 얻을 수 있다.

:\begin{align}

e_1(x_1, \ldots, x_n) &= p_1(x_1, \ldots, x_n),\\

2e_2(x_1, \ldots, x_n) &= e_1(x_1, \ldots, x_n)p_1(x_1, \ldots, x_n) - p_2(x_1, \ldots, x_n),\\

3e_3(x_1, \ldots, x_n) &= e_2(x_1, \ldots, x_n)p_1(x_1, \ldots, x_n) - e_1(x_1, \ldots, x_n)p_2(x_1, \ldots, x_n) + p_3(x_1, \ldots, x_n).

\end{align}

이 방정식들을 통해 e_i를 p_k로 재귀적으로 표현할 수 있으며, 역으로 p_k를 e_i로 표현할 수도 있다.

3. 2. 다른 표현

완전 동차 대칭 다항식(complete homogeneous symmetric polynomial) hₖ영어를 사용하면, 뉴턴 항등식과 유사한 관계식을 얻을 수 있다. 기본 대칭 다항식과 완전 동차 대칭 다항식을 멱합 다항식으로 표현하거나, 역으로 멱합 다항식을 기본 대칭 다항식 또는 완전 동차 대칭 다항식으로 표현하는 다양한 공식이 존재한다. 이러한 공식들은 행렬식을 사용하여 표현할 수도 있다.

  • '''hₖ영어를 사용한 표현'''


hₖ영어 (차수 k의 모든 단항식의 합)를 이용하면 다음과 같다.

:kh_k = \sum_{i=1}^kh_{k-i}p_i,

이는 모든 n \ge k \ge 1에 대해 유효하다.

처음 몇 개의 k 값에 대해 다음이 성립한다.

:\begin{align}

h_1 &= p_1,\\

2h_2 &= h_1p_1 + p_2,\\

3h_3 &= h_2p_1 + h_1p_2 + p_3.\\

\end{align}

이러한 관계는 다음 생성 함수 항등식에 기반한다.

:\sum_{k=0}^\infty h_k(x_1, \ldots, x_n)t^k = \prod_{i=1}^n\frac1{1 - x_it}.

  • '''기본 대칭 다항식을 멱합 다항식으로 표현'''


:\begin{align}

e_1 &= p_1,\\

e_2 &= \textstyle\frac12p_1^2 - \frac12p_2 = \textstyle\frac12 ( p_1^2 - p_2 ),\\

e_3 &= \textstyle\frac16p_1^3 - \frac12p_1 p_2 + \frac13p_3 = \textstyle\frac{1}{6} ( p_1^3 - 3 p_1 p_2 + 2 p_3 ),\\

e_4 &= \textstyle\frac1{24}p_1^4 - \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 - \frac14p_4

= \textstyle\frac1{24} ( p_1^4 - 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 - 6 p_4 ),\\

&~~\vdots

\end{align}

일반 공식은 다음과 같이 표현할 수 있다.

:e_k = \frac{(-1)^k}{k!} B_{k}(- p_1, -1! \, p_2, - 2! \, p_3, \ldots, - (k-1)! \, p_k ),

여기서 ''Bn''영어은 완전 지수 벨 다항식이다.

생성 함수에 대한 항등식은 다음과 같다.

: \sum_{k=0}^\infty e_k \,t^k = \exp\left(\sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} p_k \,t^k \right).

  • '''완전 동차 대칭 다항식을 멱합 다항식으로 표현'''

:\begin{align}

h_1 &= p_1,\\

h_2 &= \textstyle\frac12p_1^2 + \frac12p_2 = \textstyle\frac12 ( p_1^2 + p_2 ),\\

h_3 &= \textstyle\frac16p_1^3 + \frac12p_1 p_2 + \frac13p_3 = \textstyle\frac{1}{6} ( p_1^3 + 3 p_1 p_2 + 2 p_3 ),\\

h_4 &= \textstyle\frac1{24}p_1^4 + \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 + \frac14p_4

= \textstyle\frac1{24} ( p_1^4 + 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 + 6 p_4 ),\\

&~~\vdots

\end{align}

일반 공식은 완전 벨 다항식으로 표현하면 다음과 같다.

:h_k = \frac{1}{k!} B_{k}(p_1, 1! \, p_2, 2! \, p_3, \ldots, (k-1)! \, p_k ).

  • '''멱합 다항식을 기본 대칭 다항식으로 표현'''

:\begin{align}

p_1 &= e_1,\\

p_2 &= e_1^2 - 2 e_2,\\

p_3 &= e_1^3 - 3 e_2 e_1 + 3 e_3,\\

p_4 &= e_1^4 - 4 e_2 e_1^2 + 4 e_3 e_1 + 2 e_2^2 - 4 e_4,\\

p_5 &= e_1^5 - 5 e_2 e_1^3 + 5 e_3 e_1^2 + 5 e_2^2 e_1 - 5 e_4 e_1 - 5 e_3e_2 + 5 e_5,\\

p_6 &= e_1^6 - 6 e_2 e_1^4 + 6 e_3 e_1^3 + 9 e_2^2 e_1^2 - 6 e_4 e_1^2 - 12 e_3 e_2 e_1 + 6 e_5 e_1 - 2 e_2^3 + 3 e_3^2 + 6 e_4 e_2 - 6e_6.

\end{align}

일반 공식은 다음과 같다.

:p_m = (-1)^m m \sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m\ge 0} \frac{(r_1 + r_2 + \cdots + r_m - 1)!}{r_1!\,r_2! \cdots r_m!} \prod_{i=1}^m (-e_i)^{r_i}.

일반 벨 다항식 관점에서는 다음과 같다.

:p_m = (-1)^m m \sum_{k=1}^m \frac{1}{k} \hat{B}_{m,k}(-e_1,\ldots,-e_{m-k+1}),

생성 함수로는 다음과 같다.

:

\begin{align}

\sum_{k=1}^{\infty} (-1)^{k-1} p_k \frac{t^k}{k} & = \ln\left(1+e_1t+e_2t^2+e_3t^3+\cdots\right) \\

& = e_1 t - \frac{1}{2}\left(e_1^2-2e_2\right) t^2 + \frac{1}{3}\left(e_1^3-3e_1e_2+3e_3\right) t^3 + \cdots,

\end{align}


  • '''멱합 다항식을 완전 동차 대칭 다항식으로 표현'''

:\begin{align}

p_1 &= + h_1,\\

p_2 &= - h_1^2 + 2 h_2,\\

p_3 &= + h_1^3 - 3 h_2 h_1 + 3 h_3,\\

p_4 &= - h_1^4 + 4 h_2 h_1^2 - 4 h_3 h_1 - 2 h_2^2 + 4 h_4,\\

p_5 &= + h_1^5 - 5 h_2 h_1^3 + 5 h_2^2 h_1 + 5 h_3 h_1^2 - 5 h_3h_2 - 5 h_4 h_1 + 5 h_5,\\

p_6 &= - h_1^6 + 6 h_2 h_1^4 - 9 h_2^2 h_1^2 - 6 h_3 h_1^3 + 2 h_2^3 + 12 h_3 h_2 h_1 + 6 h_4 h_1^2 - 3 h_3^2 - 6 h_4 h_2 - 6 h_1 h_5 + 6h_6,

\end{align}

일반 공식은 다음과 같다.

:p_m = -\sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m \ge 0} \frac{m(r_1 + r_2 + \cdots + r_m - 1)!}{r_1!\,r_2!\cdots r_m!} \prod_{i=1}^m (-h_i)^{r_i}

  • '''행렬식을 이용한 표현'''


:\begin{align}

p_n ={} &\begin{vmatrix}

e_1 & 1 & 0 & \cdots \\

2e_2 & e_1 & 1 & 0 & \cdots \\

3e_3 & e_2 & e_1 & 1 \\

\vdots & & & \ddots & \ddots \\

ne_n & e_{n - 1} & \cdots & & e_1

\end{vmatrix}.

\end{align}

:\begin{align}

e_n = \frac1{n!}&\begin{vmatrix}

p_1 & 1 & 0 & \cdots \\

p_2 & p_1 & 2 & 0 & \cdots \\

\vdots & & \ddots & \ddots \\

p_{n-1} & p_{n-2} & \cdots & p_1 & n-1 \\

p_n & p_{n-1} & \cdots & p_2 & p_1

\end{vmatrix} \\[7pt]

p_n = (-1)^{n-1}&\begin{vmatrix}

h_1 & 1 & 0 & \cdots \\

2h_2 & h_1 & 1 & 0 & \cdots \\

3h_3 & h_2 & h_1 & 1 \\

\vdots & & & \ddots & \ddots \\

nh_n & h_{n-1} & \cdots & & h_1

\end{vmatrix} \\[7pt]

h_n = \frac1{n!}&\begin{vmatrix}

p_1 & -1 & 0 & \cdots \\

p_2 & p_1 & -2 & 0 & \cdots \\

\vdots & & \ddots & \ddots \\

p_{n - 1} & p_{n-2} & \cdots & p_1 & 1 - n \\

p_n & p_{n-1} & \cdots & p_2 & p_1

\end{vmatrix}.

\end{align}

4. 뉴턴 항등식의 응용

뉴턴 항등식은 다항식의 근과 계수 사이의 관계, 행렬의 특성 다항식, 갈루아 이론 등 다양한 분야에 응용된다.


  • 다항식의 근과 계수: 뉴턴 항등식은 다항식의 계수와 복소수 근의 거듭제곱합 사이의 관계를 나타낸다. 이를 통해 다항식의 근을 직접 구하지 않고도 근의 거듭제곱합을 계산하거나, 반대로 근의 거듭제곱합을 통해 다항식의 계수를 구할 수 있다.[1]
  • 행렬의 특성 다항식: 행렬의 고유값은 해당 행렬의 특성 다항식의 근이 된다. 뉴턴 항등식을 이용하면 행렬의 거듭제곱의 대각합을 통해 특성 다항식의 계수를 효율적으로 계산할 수 있으며, 이는 파데예프-르베리에 알고리즘으로 구현된다.[1]
  • 갈루아 이론: 뉴턴 항등식은 대칭 다항식의 기본 정리를 증명하는 데 사용된다. 다항식의 근에 대한 대칭식은 다항식의 계수만으로 표현 가능하다는 것을 보여주며, 이는 갈루아 이론에서 중요한 결과이다.

4. 1. 다항식의 근과 계수

뉴턴 항등식에 따라, 다항식의 복소수 근의 거듭제곱합

:s_k = x_1^k + \cdots + x_n^k

및 그들로 표현되는 중근 판별식

:\prod_{i > j} (x_i - x_j)^2 = \det VV^T = \det[s_{i+j-2}]_{i,j=1}^n

은 모두 다항식의 계수로도 표현된다.

다음을 이용하여 근이 ''x''''i''인 다항식을 전개할 수 있다.

: \prod_{i=1}^n (x - x_i) = \sum_{k=0}^n (-1)^k e_k x^{n-k},

여기서 계수 e_k(x_1,\ldots,x_n)는 위에 정의된 대칭 다항식이다.

근의 '멱합'이 주어지면

: p_k(x_1,\ldots,x_n)= \sum_{i=1}^n x_i^k,

근 x_1,\ldots,x_n을 갖는 다항식의 계수는 멱합을 사용하여 재귀적으로 표현될 수 있다.

:\begin{align}

e_0 &= 1,\\[4pt]

  • e_1 &=-p_1,\\[4pt]

e_2 &= \frac{1}{2}(e_1 p_1 - p_2),\\[4pt]

  • e_3 &=-\frac{1}{3}(e_2 p_1 - e_1 p_2 + p_3),\\[4pt]

e_4 &= \frac{1}{4}(e_3 p_1 - e_2 p_2 + e_1 p_3 - p_4), \\

& {} \ \ \vdots

\end{align}

이러한 방식으로 다항식을 공식화하는 것은 Delves와 Lyness의 방법[1]을 사용하여 해석 함수의 영점을 찾는 데 유용하다.

위의 다항식이 행렬 ''A''의 특성 다항식인 경우 (특히 ''A''가 다항식의 동반 행렬인 경우), 근 x_i는 행렬의 고유값이 된다. 또한 임의의 양의 정수 ''k''에 대해 행렬 ''A''''k''는 고유값 x_i^k를 가지며, 이들의 합은 ''A''''k''의 트레이스로 나타낼 수 있다.

:p_k = \operatorname{tr} ( A^k )\,.

뉴턴 항등식에 의해 이들로부터 기본 대칭식이 구해지므로, ''A''의 특성 다항식의 계수를 A''k''의 트레이스를 계산하여 구할 수 있다.

이 계산에서는 행렬의 거듭제곱 ''A''''k''의 트레이스 계산과, 뉴턴 항등식을 푸는 과정에서 삼각화된 연립 방정식을 풀어야 한다. 이러한 계산은 모두 복잡도 클래스 NC로 실행할 수 있다. 따라서 행렬의 특성 다항식은 NC로 계산할 수 있다. 케일리-해밀턴 정리에 의해, 모든 행렬은 그 특성 다항식을 만족하며, 단순한 변환에 의해 NC로 여인자 행렬을 찾을 수 있다.

계산을 효율적인 형식으로 재배치하면, ''파데예프-르베리에 알고리즘''(1840)이 얻어진다. 이것의 고속 병렬 구현은 L. Csanky(1976)에 의해 얻어졌다. 이 방식의 단점은 정수 나눗셈이 필요하다는 것이다. 따라서 군의 표수는 0이어야 한다.

4. 2. 행렬의 특성 다항식

행렬 \mathbf{A}의 특성 다항식의 근 x_i는 행렬의 고유값이며, 대수적 중복성을 포함하여 계산된다. 모든 양의 정수 k에 대해, 행렬 \mathbf{A}^k는 x_i^k를 고유값으로 가지며, \mathbf{A}의 각 고유값 x_i는 \mathbf{A}^k의 고유값 x_i^k의 중복성에 그 중복성을 기여한다. \mathbf{A}^k의 특성 다항식의 계수는 ''해당 거듭제곱'' x_i^k에서의 기본 대칭 다항식으로 주어진다. 특히, x_i^k의 합, 즉 \mathbf{A}의 특성 다항식의 근의 k 거듭제곱 합 p_k은 대각합:

:p_k = \operatorname{tr} ( \mathbf{A}^k )\,.

으로 주어진다.

뉴턴 항등식은 \mathbf{A}^k의 대각합과 \mathbf{A}의 특성 다항식의 계수를 관련짓는다. 역으로 사용하여 기본 대칭 다항식을 거듭제곱 합으로 표현하면, \mathbf{A}^k와 그 대각합만 계산하여 특성 다항식을 찾을 수 있다.

이 계산에는 행렬 거듭제곱 \mathbf{A}^k의 대각합 계산과 삼각 연립 방정식 풀이가 필요하다. 둘 다 NC 복잡도 클래스에서 수행할 수 있다 (삼각 연립 방정식은 분할 정복으로 풀 수 있다). 따라서 행렬의 특성 다항식은 NC에서 계산할 수 있다. 케일리-해밀턴 정리에 의해 모든 행렬은 자신의 특성 다항식을 만족하며, 간단한 변환을 통해 NC에서 수반 행렬을 찾을 수 있다.

계산을 효율적인 형태로 재배열하면 ''파데예프-르베리에 알고리즘''(1840)이 도출되며, 이 알고리즘의 빠른 병렬 구현은 L. Csanky (1976)에 의해 이루어졌다. 단점은 정수로 나누어야 하므로 일반적으로 필드는 0의 표수를 가져야 한다.

뉴턴 항등식은 크라머의 법칙을 적용하여 행렬식 형태로도 나타낼 수 있다.

4. 3. 갈루아 이론

뉴턴 항등식은 대칭 다항식의 기본 정리를 증명하는 데 사용될 수 있다. 다항식의 근에 대한 대칭식은 다항식의 계수만으로 표현될 수 있다는 것을 보여준다. 이는 갈루아 이론의 일반적인 결과이다.

단항 다항식 \textstyle t^n+\sum_{k=1}^n (-1)^{k} a_k t^{n-k}에 뉴턴 항등식을 적용하면, 그 근에서의 모든 대칭 다항식 표현 ''S''(''x''1,...,''x''''n'')을 근에 대한 지식 없이, 계수만으로 이루어진 다항식 표현 ''P''(''a''1,...,''a''''n'')으로 대신 표현할 수 있다.

뉴턴 항등식은 기본 대칭 다항식을 거듭제곱합 대칭 다항식으로 표현할 수 있도록 하여, 모든 대칭 다항식을 거듭제곱합으로 표현할 수도 있음을 보여준다.

5. 뉴턴 항등식의 증명

뉴턴 항등식은 간단한 대수학으로 확인할 수 있지만, 일반적으로는 그 타당성을 증명해야 한다. 다음은 몇 가지 가능한 유도 방법이다.[5]

5. 1. 급수의 계수 비교

형식적 멱급수를 이용하여 뉴턴 항등식을 유도할 수 있다. 우선, 다음과 같은 기본 관계식에서 시작한다.

:\prod_{i=1}^n (1- x_it) = \sum_{k=0}^n (-1)^{k} e_k(x_1, \ldots, x_n) t^k.

여기서 ek(x1, ..., xn)는 k차 기본 대칭 다항식이다. 이 식의 양변을 형식적으로 미분하고 t를 곱하면 다음과 같다.

:\begin{align}

\sum_{k=0}^n (-1)^{k}k e_k(x_1,\ldots,x_n) t^k

&= t \sum_{i=1}^n \left[(-x_i) \prod\nolimits_{j \neq i}(1 - x_jt)\right]\\

&= -\left(\sum_{i=1}^n \frac{x_it}{1 - x_it}\right) \prod\nolimits_{j=1}^n (1 - x_jt)\\

&= -\left[\sum_{i=1}^n \sum_{j=1}^\infty(x_it)^j\right]\left[\sum_{\ell=0}^n (-1)^\ell e_\ell(x_1,\ldots,x_n) t^\ell\right]\\

&= \left[\sum_{j=1}^\infty p_j(x_1, \ldots, x_n)t^j\right] \left[\sum_{\ell=0}^n (-1)^{\ell - 1} e_\ell(x_1, \ldots, x_n) t^\ell\right],\\

\end{align}

위 식에서 우변은 유리 함수를 이용하여 변형되었고, 다음 공식을 사용하여 t에 대한 급수로 전개되었다.

:\frac{X}{1 - X} = X + X^2 + X^3 + X^4 + X^5 + \cdots,

마지막으로 양변에서 tk의 계수를 비교하면 k번째 뉴턴 항등식을 얻는다.

:(-1)^{k}k e_k(x_1,\ldots,x_n) = \sum_{j=1}^k (-1)^{k-j-1} p_j(x_1,\ldots,x_n)e_{k-j}(x_1,\ldots,x_n),

5. 2. 조합론적 증명

도로론 자일버거는 1984년에 뉴턴 항등식에 대한 짧은 조합적 증명을 제시했다.[5]

참조

[1] 논문 A Numerical Method of Locating the Zeros of an Analytic Function 1967
[2] 문서 N.b., the coefficients of the weighted product terms in the sum given by the identity above are related to the ''M2'' numbers in Section 26.4 of the DLMF and/or the coefficients involved in the expansions of Faa di Bruno's formula https://dlmf.nist.go[...]
[3] 서적 Galois' theory of algebraic equations https://archive.org/[...] World Scientific 2004
[4] 웹사이트 Symmetric Polynomial
[5] 논문 A Combinatorial Proof of Newton's Identities 1984
[6] 논문 A Numerical Method of Locating the Zeros of an Analytic Function 1967
[7] 서적 Galois' theory of algebraic equations https://archive.org/[...] World Scientific 2004
[8] MathWorld Symmetric Polynomial


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com