Vieta 公式給出了多項式方程根與係數的關係, 而不必實際地把這些根求出來, 由於高次多項式方程的求解一般而言非常困難, 該公式極大地簡化了對多項式方程的研究.
由代數基本定理知, 一個 n n n n n n n n n f ( x ) = x n + ∑ i = 1 n a i x n − i f(x)=x^n+\sum_{i=1}^{n}a_i x^{n-i} f ( x ) = x n + ∑ i = 1 n a i x n − i
f ( x ) = ( x − x 1 ) ( x − x 2 ) ⋯ ( x − x n ) f(x)=(x-x_1)(x-x_2)\cdots(x-x_n) f ( x ) = ( x − x 1 ) ( x − x 2 ) ⋯ ( x − x n ) 直接展開比較係數即得
{ a 1 = ( − 1 ) ∑ i = 1 n x i a 2 = ( − 1 ) 2 ∑ i < j x i x j ⋯ ⋯ a k = ( − 1 ) k ∑ i 1 < ⋯ < i k x i 1 x i 2 ⋯ x i k ⋯ ⋯ a n = ( − 1 ) n x 1 x 2 ⋯ x n
\begin{cases}
a_1 = (-1)\sum_{i=1}^n x_i \\
a_2 = (-1)^2\sum_{i<j} x_i\thinspace x_j \\
\cdots\cdots \\
a_k = (-1)^k\sum_{i_1<\cdots<i_k} x_{i_1}x_{i_2}\cdots x_{i_k} \\
\cdots\cdots \\
a_n = (-1)^n x_1 x_2\cdots x_n
\end{cases}
⎩ ⎨ ⎧ a 1 = ( − 1 ) ∑ i = 1 n x i a 2 = ( − 1 ) 2 ∑ i < j x i x j ⋯⋯ a k = ( − 1 ) k ∑ i 1 < ⋯ < i k x i 1 x i 2 ⋯ x i k ⋯⋯ a n = ( − 1 ) n x 1 x 2 ⋯ x n 我們得到 n n n x 1 , ⋯ , x n x_1,\cdots,x_n x 1 , ⋯ , x n
{ s 1 = ∑ i = 1 n x i s 2 = ∑ i < j x i x j ⋯ ⋯ s k = ∑ i 1 < ⋯ < i k x i 1 x i 2 ⋯ x i k ⋯ ⋯ s n = x 1 x 2 ⋯ x n
\begin{cases}
s_1 = \sum_{i=1}^n x_i \\
s_2 = \sum_{i<j} x_i\thinspace x_j \\
\cdots\cdots \\
s_k = \sum_{i_1<\cdots<i_k} x_{i_1}x_{i_2}\cdots x_{i_k} \\
\cdots\cdots \\
s_n = x_1 x_2\cdots x_n
\end{cases}
⎩ ⎨ ⎧ s 1 = ∑ i = 1 n x i s 2 = ∑ i < j x i x j ⋯⋯ s k = ∑ i 1 < ⋯ < i k x i 1 x i 2 ⋯ x i k ⋯⋯ s n = x 1 x 2 ⋯ x n 注意到 s k ( x 1 , ⋯ , x n ) s_k(x_1,\cdots,x_n) s k ( x 1 , ⋯ , x n ) ( x 1 , ⋯ , x n ) (x_1,\cdots,x_n) ( x 1 , ⋯ , x n )
s k ( x 1 , x 2 , ⋯ , x n ) = s k ( x σ ( 1 ) , x σ ( 2 ) , ⋯ , x σ ( n ) ) s_k(x_1,x_2,\cdots,x_n)=s_k\left(x_{\sigma(1)},x_{\sigma(2)},\cdots,x_{\sigma(n)}\right) s k ( x 1 , x 2 , ⋯ , x n ) = s k ( x σ ( 1 ) , x σ ( 2 ) , ⋯ , x σ ( n ) ) 恆成立, 其中 σ ∈ S n \sigma\in S_n σ ∈ S n ( 1 , ⋯ , n ) (1,\cdots,n) ( 1 , ⋯ , n )
因此, 我們稱多項式 s k s_k s k n n n
一般地, 設 A A A n n n f ∈ A [ x 1 , ⋯ , x n ] f\in A\left[x_1,\cdots,x_n\right] f ∈ A [ x 1 , ⋯ , x n ] σ ∈ S n \sigma\in S_n σ ∈ S n
f ( x 1 , x 2 , ⋯ , x n ) = f ( x σ ( 1 ) , x σ ( 2 ) , ⋯ , x σ ( n ) ) f(x_1,x_2,\cdots,x_n) = f\left(x_{\sigma(1)},x_{\sigma(2)},\cdots,x_{\sigma(n)}\right) f ( x 1 , x 2 , ⋯ , x n ) = f ( x σ ( 1 ) , x σ ( 2 ) , ⋯ , x σ ( n ) ) 則稱 f f f
對 f ∈ A [ x 1 , ⋯ , x n ] f\in A\left[x_1,\cdots,x_n\right] f ∈ A [ x 1 , ⋯ , x n ] σ ∈ S n \sigma\in S_n σ ∈ S n
( σ ∘ f ) ( x 1 , x 2 , ⋯ , x n ) = f ( x σ ( 1 ) , x σ ( 2 ) , ⋯ , x σ ( n ) ) (\sigma\circ f)(x_1,x_2,\cdots,x_n) = f\left(x_{\sigma(1)},x_{\sigma(2)},\cdots,x_{\sigma(n)}\right) ( σ ∘ f ) ( x 1 , x 2 , ⋯ , x n ) = f ( x σ ( 1 ) , x σ ( 2 ) , ⋯ , x σ ( n ) ) 則 ∑ σ ∈ S n σ ∘ f \sum_{\sigma\in S_n}\sigma\circ f ∑ σ ∈ S n σ ∘ f ∏ σ ∈ S n σ ∘ f \prod_{\sigma\in S_n}\sigma\circ f ∏ σ ∈ S n σ ∘ f
σ ∘ ( f g ) = ( σ ∘ f ) ( σ ∘ g ) σ ∘ ( f + g ) = σ ∘ f + σ ∘ g
\begin{align*}
\sigma\circ (fg) &= (\sigma\circ f)(\sigma\circ g) \\
\sigma\circ (f+g) &= \sigma\circ f+\sigma\circ g
\end{align*}
σ ∘ ( f g ) σ ∘ ( f + g ) = ( σ ∘ f ) ( σ ∘ g ) = σ ∘ f + σ ∘ g 所以 A A A n n n R = A [ x 1 , ⋯ , x n ] R=A\left[x_1,\cdots,x_n\right] R = A [ x 1 , ⋯ , x n ] F ∈ A [ y 1 , ⋯ , y m ] F\in A\left[y_1,\cdots,y_m\right] F ∈ A [ y 1 , ⋯ , y m ] f 1 , ⋯ , f m ∈ R f_1,\cdots,f_m\in R f 1 , ⋯ , f m ∈ R F ( f 1 , ⋯ , f m ) F(f_1,\cdots,f_m) F ( f 1 , ⋯ , f m ) R R R
對稱多項式基本定理是說, 整環 A A A f ∈ A [ x 1 , ⋯ , x n ] f\in A\left[x_1,\cdots,x_n\right] f ∈ A [ x 1 , ⋯ , x n ] g ∈ A [ y 1 , ⋯ , y m ] g\in A\left[y_1,\cdots,y_m\right] g ∈ A [ y 1 , ⋯ , y m ]
f ( x 1 , x 2 , ⋯ , x n ) = g ( s i 1 , s i 2 , ⋯ , s i m ) f(x_1,x_2,\cdots,x_n) = g(s_{i_1},s_{i_2},\cdots,s_{i_m}) f ( x 1 , x 2 , ⋯ , x n ) = g ( s i 1 , s i 2 , ⋯ , s i m ) 其中 s i 1 , ⋯ , s i m s_{i_1},\cdots,s_{i_m} s i 1 , ⋯ , s i m 0 ≤ i 1 < ⋯ < i m ≤ n 0\leq i_1<\cdots<i_m\leq n 0 ≤ i 1 < ⋯ < i m ≤ n m m m n n n
證明即給出表示法. 首先容易看出, 任意對稱多項式可以表為若干齊次對稱多項式之和, 故只需分別處理齊次部分即可. 設 f ( x 1 , ⋯ , x n ) f(x_1,\cdots,x_n) f ( x 1 , ⋯ , x n ) a i x 1 l i , 1 x 2 l i , 2 ⋯ x n l i , n a_{i}x_1^{l_{i,1}}x_2^{l_{i,2}}\cdots x_n^{l_{i,n}} a i x 1 l i , 1 x 2 l i , 2 ⋯ x n l i , n L i = ( l i , 1 , ⋯ , l i , n ) L_i=(l_{i,1},\cdots,l_{i,n}) L i = ( l i , 1 , ⋯ , l i , n )
若 l i , 1 < l j , 1 l_{i,1}<l_{j,1} l i , 1 < l j , 1 L i < L j L_i<L_j L i < L j
若 l i , 1 = l j , 1 l_{i,1}=l_{j,1} l i , 1 = l j , 1 ⋯ \cdots ⋯ l i , k = l j , k l_{i,k}=l_{j,k} l i , k = l j , k l i , k + 1 < l j , k + 1 l_{i,k+1}<l_{j,k+1} l i , k + 1 < l j , k + 1 L i < L j L_i<L_j L i < L j
按字典序由大到小排列 f f f a 1 x 1 l 1 x 2 l 2 ⋯ x n l n a_1 x_1^{l_1}x_2^{l_2}\cdots x_n^{l_n} a 1 x 1 l 1 x 2 l 2 ⋯ x n l n l 1 ≥ ⋯ ≥ l n ≥ 0 l_1\geq\cdots\geq l_n\geq 0 l 1 ≥ ⋯ ≥ l n ≥ 0 φ 1 = a 1 s 1 l 1 − l 2 s 2 l 2 − l 3 ⋯ s n l n \varphi_1=a_1 s_1^{l_1-l_2}s_2^{l_2-l_3}\cdots s_n^{l_n} φ 1 = a 1 s 1 l 1 − l 2 s 2 l 2 − l 3 ⋯ s n l n φ 1 \varphi_1 φ 1
a 1 x 1 l 1 − l 2 ( x 1 x 2 ) l 2 − l 3 ⋯ ( x 1 ⋯ x n ) l n = a 1 x 1 l 1 x 2 l 2 ⋯ x n l n a_1 x_1^{l_1-l_2}(x_1x_2)^{l_2-l_3}\cdots(x_1\cdots x_n)^{l_n}=a_1 x_1^{l_1}x_2^{l_2}\cdots x_n^{l_n} a 1 x 1 l 1 − l 2 ( x 1 x 2 ) l 2 − l 3 ⋯ ( x 1 ⋯ x n ) l n = a 1 x 1 l 1 x 2 l 2 ⋯ x n l n 而 φ 1 \varphi_1 φ 1 g 1 = f − φ 1 g_1=f-\varphi_1 g 1 = f − φ 1 g 1 g_1 g 1
這樣做下去便得到一串多項式 g 1 , g 2 , ⋯ g_1,g_2,\cdots g 1 , g 2 , ⋯ g i g_i g i x 1 x_1 x 1 0 0 0 g i = 0 g_i=0 g i = 0 L 1 L_1 L 1 l 1 , 1 = 1 l_{1,1}=1 l 1 , 1 = 1 l 1 , 1 ≥ ⋯ ≥ l 1 , n ≥ 0 l_{1,1}\geq\cdots\geq l_{1,n}\geq 0 l 1 , 1 ≥ ⋯ ≥ l 1 , n ≥ 0 g m g_m g m a 1 ′ x 1 ⋯ x r a_1'x_1\cdots x_r a 1 ′ x 1 ⋯ x r r ≤ n r\leq n r ≤ n g m = a 1 ′ ∑ i 1 < ⋯ < i r x i 1 x i 2 ⋯ x i r g_m=a_1'\sum_{i_1<\cdots<i_r} x_{i_1}x_{i_2}\cdots x_{i_r} g m = a 1 ′ ∑ i 1 < ⋯ < i r x i 1 x i 2 ⋯ x i r a 1 ′ s r a_1' s_r a 1 ′ s r 0 0 0 s s s
接下來引入一類特殊的對稱多項式 p k ( x 1 , ⋯ , x n ) = ∑ i = 1 n x i p_k(x_1,\cdots,x_n)=\sum_{i=1}^n x_i p k ( x 1 , ⋯ , x n ) = ∑ i = 1 n x i k k k p p p s s s
規定 s 0 = 1 s_0=1 s 0 = 1 s m = 0 s_m=0 s m = 0 ( m > n ) (m>n) ( m > n )
k s k + ∑ i = 1 k ( − 1 ) i p i s k − i = 0 ks_k + \sum_{i=1}^k(-1)^i p_is_{k-i} = 0 k s k + i = 1 ∑ k ( − 1 ) i p i s k − i = 0 特別地, 當 k > n k>n k > n
∑ i = k − n k ( − 1 ) i p i s k − i = 0 \sum_{i=k-n}^k(-1)^i p_is_{k-i} = 0 i = k − n ∑ k ( − 1 ) i p i s k − i = 0 下面提供兩種證明.
(聽說這是 Kostrikin 的證法. )
令 f ( x ) = ∏ i = 1 n ( x − x i ) = ∑ i = 1 n ( − 1 ) i s i x n − i f(x)=\prod_{i=1}^n(x-x_i)=\sum_{i=1}^n(-1)^i s_i x^{n-i} f ( x ) = ∏ i = 1 n ( x − x i ) = ∑ i = 1 n ( − 1 ) i s i x n − i
f ′ ( x ) f ( x ) = ∑ i = 1 n 1 x − x i \frac{f'(x)}{f(x)} = \sum_{i=1}^n \frac{1}{x-x_i} f ( x ) f ′ ( x ) = i = 1 ∑ n x − x i 1 把 1 / ( x − x i ) 1/(x-x_i) 1/ ( x − x i )
1 x − x i = 1 x ∑ j = 0 ∞ ( x i x ) j \frac{1}{x-x_i} = \frac{1}{x}\sum_{j=0}^{\infty}\left(\frac{x_i}{x}\right)^j x − x i 1 = x 1 j = 0 ∑ ∞ ( x x i ) j 所以
RHS = 1 x ∑ i = 1 n ∑ j = 0 ∞ x i j x j = 1 x ∑ j = 0 ∞ p j x j \text{RHS} = \frac{1}{x}\sum_{i=1}^n\sum_{j=0}^{\infty}\frac{x_i^j}{x^j} = \frac{1}{x}\sum_{j=0}^{\infty}\frac{p_j}{x^j} RHS = x 1 i = 1 ∑ n j = 0 ∑ ∞ x j x i j = x 1 j = 0 ∑ ∞ x j p j 即
x f ′ ( x ) = ∑ i = 1 n ( − 1 ) i i s i x n − i = ( ∑ i = 1 n ( − 1 ) i s i x n − i ) ( ∑ j = 0 ∞ p j x j ) xf'(x) = \sum_{i=1}^n(-1)^i is_i x^{n-i} = \left(\sum_{i=1}^n(-1)^i s_i x^{n-i}\right)\left(\sum_{j=0}^{\infty}\frac{p_j}{x^j}\right) x f ′ ( x ) = i = 1 ∑ n ( − 1 ) i i s i x n − i = ( i = 1 ∑ n ( − 1 ) i s i x n − i ) ( j = 0 ∑ ∞ x j p j ) 當 k ≤ n k\leq n k ≤ n n − k n-k n − k
( − 1 ) k k s k = ∑ i = 0 k − 1 ( − 1 ) i p k − i s i (-1)^k ks_k = \sum_{i=0}^{k-1} (-1)^i p_{k-i} s_i ( − 1 ) k k s k = i = 0 ∑ k − 1 ( − 1 ) i p k − i s i 當 k > n k>n k > n 0 0 0
0 = ∑ i = k − n k ( − 1 ) i p k − i s i 0 = \sum_{i=k-n}^k (-1)^i p_{k-i} s_i 0 = i = k − n ∑ k ( − 1 ) i p k − i s i (右式仍為 n − k n-k n − k □ \square □
下面是一種非常巧妙的組合證明, 由 Doron Zeilberger 發表於1984年.
考慮由有序對 ( A , j l ) (A,j^l) ( A , j l ) A ( n , k ) \mathscr{A}(n,k) A ( n , k )
A A A { 1 , ⋯ , n } \lbrace 1,\cdots,n\rbrace { 1 , ⋯ , n }
j ∈ { 1 , ⋯ , n } j\in\lbrace 1,\cdots,n\rbrace j ∈ { 1 , ⋯ , n }
∣ A ∣ + l = k |A|+l=k ∣ A ∣ + l = k ∣ A ∣ |A| ∣ A ∣ A A A
l ≥ 0 l\geq 0 l ≥ 0 l = 0 l=0 l = 0 j ∈ A j\in A j ∈ A
定義 ( A , j l ) (A,j^l) ( A , j l ) w ( A , j l ) w(A,j^l) w ( A , j l ) w ( A , j l ) = ( − 1 ) ∣ A ∣ ( ∏ a ∈ A x a ) x j l w(A,j^l)=(-1)^{|A|}(\prod_{a\in A}x_a)x_j^l w ( A , j l ) = ( − 1 ) ∣ A ∣ ( ∏ a ∈ A x a ) x j l
∑ ( A , j l ) ∈ A w ( A , j l ) = ∑ i = 0 k − 1 ( − 1 ) i p k − i s i + ( − 1 ) k k s k \sum_{(A,j^l)\in\mathscr{A}}w(A,j^l) = \sum_{i=0}^{k-1} (-1)^i p_{k-i} s_i + (-1)^k ks_k ( A , j l ) ∈ A ∑ w ( A , j l ) = i = 0 ∑ k − 1 ( − 1 ) i p k − i s i + ( − 1 ) k k s k 在右側和式中令 i = ∣ A ∣ < k i=|A|<k i = ∣ A ∣ < k k − i = l k-i=l k − i = l
故只需證明所有權重的和為 0 0 0 T : A → A T:\mathscr{A}\to\mathscr{A} T : A → A
T ( A , j l ) = { ( A ∖ { j } , j l + 1 ) , j ∈ A ( A ∪ { j } , j l − 1 ) , j ∉ A
T(A,j^l)=\begin{cases}
(A\setminus\lbrace j\rbrace,j^{l+1}), &j\in A \\
(A\cup\lbrace j\rbrace,j^{l-1}), &j\not\in A
\end{cases}
T ( A , j l ) = { ( A ∖ { j } , j l + 1 ) , ( A ∪ { j } , j l − 1 ) , j ∈ A j ∈ A 於是有 w ( A , j l ) = − w ( T ( A , j l ) ) w(A,j^l)=-w(T(A,j^l)) w ( A , j l ) = − w ( T ( A , j l )) T ∘ T = id A T\circ T=\text{id}_{\mathscr{A}} T ∘ T = id A T T T w ( A , j l ) w(A,j^l) w ( A , j l ) w ( T ( A , j l ) ) w(T(A,j^l)) w ( T ( A , j l )) 0 0 0 □ \square □
這種證法也暗示了 Newton 恆等式在本質上是容斥原理的一種特殊形式.
通過 Newton 恆等式, 我們可以遞歸地用 p p p s k s_k s k
s k = 1 k ∑ i = 1 k ( − 1 ) i − 1 p i s k − 1 s_k=\frac{1}{k}\sum_{i=1}^k (-1)^{i-1}p_i s_{k-1} s k = k 1 i = 1 ∑ k ( − 1 ) i − 1 p i s k − 1 前文已經證明, A A A s s s p p p k k k k = 1 , ⋯ , n k=1,\cdots,n k = 1 , ⋯ , n n n n s s s s k s_k s k p p p
進一步地, 我們可以用行列式來求出 s s s p p p
{ s 1 − p 1 = 0 2 s 2 − p 1 s 1 + p 2 = 0 3 s 3 − p 1 s 2 + p 2 s 1 − p 3 = 0 ⋯ ⋯ k s k − p 1 s k − 1 + ⋯ + ( − 1 ) k p k = 0
\begin{cases}
s_1 - p_1 = 0 \\
2s_2 - p_1s_1 + p_2 = 0 \\
3s_3 - p_1s_2 +p_2s_1 - p_3 =0 \\
\cdots\cdots \\
ks_k - p_1s_{k-1} + \cdots + (-1)^k p_k = 0
\end{cases}
⎩ ⎨ ⎧ s 1 − p 1 = 0 2 s 2 − p 1 s 1 + p 2 = 0 3 s 3 − p 1 s 2 + p 2 s 1 − p 3 = 0 ⋯⋯ k s k − p 1 s k − 1 + ⋯ + ( − 1 ) k p k = 0 把 p 1 , ⋯ , p k p_1,\cdots,p_k p 1 , ⋯ , p k k k k
( − 1 0 0 ⋯ 0 − s 1 1 0 ⋯ 0 − s 2 s 1 − 1 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ − s k − 1 s k − 2 − s k − 3 ⋯ ( − 1 ) k ) ( p 1 p 2 p 3 ⋮ p k ) = ( − s 1 − 2 s 2 − 3 s 3 ⋮ − k s k )
\begin{pmatrix}
-1&0&0&\cdots&0\\
-s_1&1&0&\cdots&0\\
-s_2&s_1&-1&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
-s_{k-1}&s_{k-2}&-s_{k-3}&\cdots&(-1)^k
\end{pmatrix}
\begin{pmatrix}p_1\\p_2\\p_3\\\vdots\\p_k\end{pmatrix}
= \begin{pmatrix}-s_1\\-2s_2\\-3s_3\\\vdots\\-ks_k\end{pmatrix}
− 1 − s 1 − s 2 ⋮ − s k − 1 0 1 s 1 ⋮ s k − 2 0 0 − 1 ⋮ − s k − 3 ⋯ ⋯ ⋯ ⋱ ⋯ 0 0 0 ⋮ ( − 1 ) k p 1 p 2 p 3 ⋮ p k = − s 1 − 2 s 2 − 3 s 3 ⋮ − k s k 得到
p k = ∣ − 1 0 ⋯ − s 1 − s 1 1 ⋯ − 2 s 2 ⋮ ⋮ ⋱ ⋮ − s k − 1 s k − 2 ⋯ − k s k ∣ / ∣ − 1 0 ⋯ 0 − s 1 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ − s k − 1 s k − 2 ⋯ ( − 1 ) k ∣ = ( − 1 ) k − 1 ∣ 1 0 ⋯ s 1 s 1 1 ⋯ 2 s 2 ⋮ ⋮ ⋱ ⋮ s k − 1 s k − 2 ⋯ k s k ∣ = ∣ s 1 1 0 0 ⋯ 0 2 s 2 s 1 1 0 ⋯ 0 3 s 3 s 2 s 1 1 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ( k − 1 ) s k − 1 s k − 2 s k − 3 s k − 4 ⋯ 1 k s k s k − 1 s k − 2 s k − 3 ⋯ s 1 ∣
\begin{align*}
p_k &= \left.\begin{vmatrix}
-1&0&\cdots&-s_1\\
-s_1&1&\cdots&-2s_2\\
\vdots&\vdots&\ddots&\vdots\\
-s_{k-1}&s_{k-2}&\cdots&-ks_k
\end{vmatrix} \middle/
\begin{vmatrix}
-1&0&\cdots&0\\
-s_1&1&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
-s_{k-1}&s_{k-2}&\cdots&(-1)^k
\end{vmatrix}\right. \\
&= (-1)^{k-1} \begin{vmatrix}
1&0&\cdots&s_1\\
s_1&1&\cdots&2s_2\\
\vdots&\vdots&\ddots&\vdots\\
s_{k-1}&s_{k-2}&\cdots&ks_k
\end{vmatrix} \\
&= \begin{vmatrix}
s_1&1&0&0&\cdots&0\\
2s_2&s_1&1&0&\cdots&0\\
3s_3&s_2&s_1&1&\cdots&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
(k-1)s_{k-1}&s_{k-2}&s_{k-3}&s_{k-4}&\cdots&1\\
ks_k&s_{k-1}&s_{k-2}&s_{k-3}&\cdots&s_1
\end{vmatrix}
\end{align*}
p k = − 1 − s 1 ⋮ − s k − 1 0 1 ⋮ s k − 2 ⋯ ⋯ ⋱ ⋯ − s 1 − 2 s 2 ⋮ − k s k / − 1 − s 1 ⋮ − s k − 1 0 1 ⋮ s k − 2 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ ( − 1 ) k = ( − 1 ) k − 1 1 s 1 ⋮ s k − 1 0 1 ⋮ s k − 2 ⋯ ⋯ ⋱ ⋯ s 1 2 s 2 ⋮ k s k = s 1 2 s 2 3 s 3 ⋮ ( k − 1 ) s k − 1 k s k 1 s 1 s 2 ⋮ s k − 2 s k − 1 0 1 s 1 ⋮ s k − 3 s k − 2 0 0 1 ⋮ s k − 4 s k − 3 ⋯ ⋯ ⋯ ⋱ ⋯ ⋯ 0 0 0 ⋮ 1 s 1 反過來把 s 1 , ⋯ , s k s_1,\cdots,s_k s 1 , ⋯ , s k
( 1 0 0 ⋯ 0 p 1 − 2 0 ⋯ 0 p 2 − p 1 3 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ p k − 1 − p k − 2 p k − 3 ⋯ ( − 1 ) k − 1 k ) ( s 1 s 2 s 3 ⋮ s k ) = ( p 1 p 2 p 3 ⋮ p k )
\begin{pmatrix}
1&0&0&\cdots&0\\
p_1&-2&0&\cdots&0\\
p_2&-p_1&3&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&-p_{k-2}&p_{k-3}&\cdots&(-1)^{k-1}k
\end{pmatrix}
\begin{pmatrix}s_1\\s_2\\s_3\\\vdots\\s_k\end{pmatrix}
= \begin{pmatrix}p_1\\p_2\\p_3\\\vdots\\p_k\end{pmatrix}
1 p 1 p 2 ⋮ p k − 1 0 − 2 − p 1 ⋮ − p k − 2 0 0 3 ⋮ p k − 3 ⋯ ⋯ ⋯ ⋱ ⋯ 0 0 0 ⋮ ( − 1 ) k − 1 k s 1 s 2 s 3 ⋮ s k = p 1 p 2 p 3 ⋮ p k 得到
s k = ( − 1 ) k − 1 ∣ 1 0 ⋯ p 1 p 1 2 ⋯ p 2 ⋮ ⋮ ⋱ ⋮ p k − 1 p k − 2 ⋯ p k ∣ / ∣ 1 0 ⋯ 0 p 1 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ p k − 1 p k − 2 ⋯ k ∣ = 1 k ! ∣ p 1 1 0 0 ⋯ 0 p 2 p 1 2 0 ⋯ 0 p 3 p 2 p 1 3 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ p k − 1 p k − 2 p k − 3 p k − 4 ⋯ k − 1 p k p k − 1 p k − 2 p k − 3 ⋯ p 1 ∣
\begin{align*}
s_k &= (-1)^{k-1}\left.\begin{vmatrix}
1&0&\cdots&p_1\\
p_1&2&\cdots&p_2\\
\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&p_{k-2}&\cdots&p_k
\end{vmatrix} \middle/
\begin{vmatrix}
1&0&\cdots&0\\
p_1&2&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&p_{k-2}&\cdots&k
\end{vmatrix}\right. \\
&= \frac{1}{k!} \begin{vmatrix}
p_1&1&0&0&\cdots&0\\
p_2&p_1&2&0&\cdots&0\\
p_3&p_2&p_1&3&\cdots&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&p_{k-2}&p_{k-3}&p_{k-4}&\cdots&k-1\\
p_k&p_{k-1}&p_{k-2}&p_{k-3}&\cdots&p_1
\end{vmatrix}
\end{align*}
s k = ( − 1 ) k − 1 1 p 1 ⋮ p k − 1 0 2 ⋮ p k − 2 ⋯ ⋯ ⋱ ⋯ p 1 p 2 ⋮ p k / 1 p 1 ⋮ p k − 1 0 2 ⋮ p k − 2 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ k = k ! 1 p 1 p 2 p 3 ⋮ p k − 1 p k 1 p 1 p 2 ⋮ p k − 2 p k − 1 0 2 p 1 ⋮ p k − 3 p k − 2 0 0 3 ⋮ p k − 4 p k − 3 ⋯ ⋯ ⋯ ⋱ ⋯ ⋯ 0 0 0 ⋮ k − 1 p 1 例如當 k = 3 k=3 k = 3
s 3 = 1 6 ∣ p 1 1 0 p 2 p 1 2 p 3 p 2 p 1 ∣ = 1 6 ( p 1 3 − 3 p 1 p 2 + 2 p 3 )
s_3 = \frac{1}{6}\begin{vmatrix}
p_1&1&0\\
p_2&p_1&2\\
p_3&p_2&p_1
\end{vmatrix}
= \frac{1}{6}(p_1^3-3p_1p_2+2p_3)
s 3 = 6 1 p 1 p 2 p 3 1 p 1 p 2 0 2 p 1 = 6 1 ( p 1 3 − 3 p 1 p 2 + 2 p 3 ) n n n 次多項式
f ( x ) = x n + ∑ i = 1 n a i x n − i f(x)=x^n+\sum_{i=1}^{n}a_i x^{n-i} f ( x ) = x n + ∑ i = 1 n a i x n − i 有重根的判別式
D f D_f D f 定義為
D f = ∏ i < j ( x i − x j ) 2 = ∣ 1 1 ⋯ 1 x 1 x 2 ⋯ x n x 1 2 x 2 2 ⋯ x n 2 ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 ⋯ x n n − 1 ∣ 2
D_f = \prod_{i<j}(x_i-x_j)^2 = \begin{vmatrix}
1&1&\cdots&1\\
x_1&x_2&\cdots&x_n\\
x_1^2&x_2^2&\cdots&x_n^2\\
\vdots&\vdots&\ddots&\vdots\\
x_1^{n-1}&x_2^{n-1}&\cdots&x_n^{n-1}
\end{vmatrix}^2
D f = i < j ∏ ( x i − x j ) 2 = 1 x 1 x 1 2 ⋮ x 1 n − 1 1 x 2 x 2 2 ⋮ x 2 n − 1 ⋯ ⋯ ⋯ ⋱ ⋯ 1 x n x n 2 ⋮ x n n − 1 2 其中,
V = ∣ 1 1 ⋯ 1 x 1 x 2 ⋯ x n x 1 2 x 2 2 ⋯ x n 2 ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 ⋯ x n n − 1 ∣ = ∏ i < j ( x i − x j )
V = \begin{vmatrix}
1&1&\cdots&1\\
x_1&x_2&\cdots&x_n\\
x_1^2&x_2^2&\cdots&x_n^2\\
\vdots&\vdots&\ddots&\vdots\\
x_1^{n-1}&x_2^{n-1}&\cdots&x_n^{n-1}
\end{vmatrix} = \prod_{i<j}(x_i-x_j)
V = 1 x 1 x 1 2 ⋮ x 1 n − 1 1 x 2 x 2 2 ⋮ x 2 n − 1 ⋯ ⋯ ⋯ ⋱ ⋯ 1 x n x n 2 ⋮ x n n − 1 = i < j ∏ ( x i − x j ) 是一個 Vandermonde 行列式. 之所以要取平方, 是因為平方後成為一個對稱多項式, 更容易計算. 顯然, f f f D f = 0 D_f=0 D f = 0
根據 Vandermonde 行列式的性質, 我們有
D f = det ( V ⋅ V T ) = det ( n p 1 p 2 ⋯ p n − 1 p 1 p 2 p 3 ⋯ p n p 2 p 3 p 4 ⋯ p n + 1 ⋮ ⋮ ⋮ ⋱ ⋮ p n − 1 p n p n + 1 ⋯ p 2 n − 2 )
D_f = \det(V\cdot V^T) = \det\begin{pmatrix}
n&p_1&p_2&\cdots&p_{n-1}\\
p_1&p_2&p_3&\cdots&p_n\\
p_2&p_3&p_4&\cdots&p_{n+1}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
p_{n-1}&p_{n}&p_{n+1}&\cdots&p_{2n-2}
\end{pmatrix}
D f = det ( V ⋅ V T ) = det n p 1 p 2 ⋮ p n − 1 p 1 p 2 p 3 ⋮ p n p 2 p 3 p 4 ⋮ p n + 1 ⋯ ⋯ ⋯ ⋱ ⋯ p n − 1 p n p n + 1 ⋮ p 2 n − 2 上文已給出 p k p_k p k s s s s k = ( − 1 ) k a k s_k=(-1)^k a_k s k = ( − 1 ) k a k D f D_f D f
首先來看實係數二次方程 a 0 x 2 + a 1 x + a 2 = 0 a_0 x^2+a_1 x+a_2=0 a 0 x 2 + a 1 x + a 2 = 0 0 0 0 a 1 = 0 a_1=0 a 1 = 0 a 0 a 2 < 0 a_0 a_2<0 a 0 a 2 < 0 n n n
——這是前不久我的一個同學遇到的面試題. 結論並不難猜, 若 n n n f ( x ) = ∑ i = 0 n a i x n − i = 0 f(x)=\sum_{i=0}^{n}a_i x^{n-i}=0 f ( x ) = ∑ i = 0 n a i x n − i = 0 n n n 0 0 0 a k = 0 a_k=0 a k = 0 k < n k<n k < n a k − 1 a k + 1 < 0 a_{k-1}a_{k+1}<0 a k − 1 a k + 1 < 0 n n n s k − 1 s k + 1 − s k 2 s_{k-1}s_{k+1}-s_k^2 s k − 1 s k + 1 − s k 2 0 0 0
最後在 Hardy et al. 的名著《不等式》中找到了這個結論. 事實上, 書中證明的是一個更強的不等式, 但很容易從中推導出我們所需的結論. (書裡說這是 Newton 的結果, 但我沒有找到原始出處. )
記 ∑ ! F ( a 1 , ⋯ , a n ) = ∑ σ ∈ S n F ( a σ ( 1 ) , ⋯ , a σ ( n ) ) \sum!F(a_1,\cdots,a_n)=\sum_{\sigma\in S_n}F\left(a_{\sigma(1)},\cdots,a_{\sigma(n)}\right) ∑ ! F ( a 1 , ⋯ , a n ) = ∑ σ ∈ S n F ( a σ ( 1 ) , ⋯ , a σ ( n ) ) a a a n ! n! n !
[ α 1 , ⋯ , α n ] = 1 n ! ∑ ! F ( a 1 α 1 , ⋯ , a n α n ) \left[\alpha_1,\cdots,\alpha_n\right] = \frac{1}{n!}\sum!F(a_1^{\alpha_1},\cdots,a_n^{\alpha_n}) [ α 1 , ⋯ , α n ] = n ! 1 ∑ ! F ( a 1 α 1 , ⋯ , a n α n ) 為 n n n a i a_i a i n ! n! n ! α \alpha α
設 x 1 , ⋯ , x n x_1,\cdots,x_n x 1 , ⋯ , x n n n n 0 0 0
s k = 1 k ! ( n − k ) ! ∑ ! x 1 ⋯ x k s_k = \frac{1}{k!(n-k)!}\sum!x_1\cdots x_k s k = k ! ( n − k )! 1 ∑ ! x 1 ⋯ x k 其中 k ! ( n − k ) ! k!(n-k)! k ! ( n − k )!
d k = k ! ( n − k ) ! n ! s k = [ 1 , ⋯ , 1 ⏟ k , 0 , ⋯ , 0 ] d_k = \frac{k!(n-k)!}{n!}s_k = [\underbrace{1,\cdots,1}_{k},0,\cdots,0] d k = n ! k ! ( n − k )! s k = [ k 1 , ⋯ , 1 , 0 , ⋯ , 0 ] 規定 d 0 = s 0 = 1 d_0=s_0=1 d 0 = s 0 = 1 d k − 1 d k + 1 < d k 2 d_{k-1}d_{k+1}<d_k^2 d k − 1 d k + 1 < d k 2
令
f ( x , y ) = ( x − x 1 y ) ( x − x 2 y ) ⋯ ( x − x n y ) = d 0 x n + ( n 1 ) d 1 x n − 1 y + ( n 2 ) d 2 x n − 2 y 2 + ⋯ + d n y n
\begin{align*}
f(x,y) &= (x-x_1 y)(x-x_2 y)\cdots(x-x_n y)\\
&= d_0 x^n+\binom{n}{1}d_1 x^{n-1}y+\binom{n}{2}d_2 x^{n-2}y^2+\cdots+d_n y^n
\end{align*}
f ( x , y ) = ( x − x 1 y ) ( x − x 2 y ) ⋯ ( x − x n y ) = d 0 x n + ( 1 n ) d 1 x n − 1 y + ( 2 n ) d 2 x n − 2 y 2 + ⋯ + d n y n 對其多次微分得到導出方程
d k − 1 x 2 + 2 d k x y + d k + 1 y 2 = 0 d_{k-1}x^2 + 2d_k xy + d_{k+1}y^2 = 0 d k − 1 x 2 + 2 d k x y + d k + 1 y 2 = 0 由於 x i ≠ 0 x_i\not=0 x i = 0 x / y = 0 x/y=0 x / y = 0 x / y = 0 x/y=0 x / y = 0 d d d 0 0 0
d k − 1 d k + 1 ≤ d k 2 d_{k-1}d_{k+1}\leq d_k^2 d k − 1 d k + 1 ≤ d k 2 等號成立, 當且僅當所有 x i x_i x i
進而,
s k − 1 s k + 1 = n ! ( k − 1 ) ! ( n − k + 1 ) ! d k − 1 ⋅ n ! ( k + 1 ) ! ( n − k − 1 ) ! d k + 1 = k k + 1 ⋅ n − k n − k + 1 ⋅ ( k ! ( n − k ) ! n ! ) 2 d k − 1 d k + 1 < ( k ! ( n − k ) ! n ! ) 2 d k − 1 d k + 1 ≤ ( k ! ( n − k ) ! n ! ) 2 d k 2 = s k 2
\begin{align*}
s_{k-1}s_{k+1} &= \frac{n!}{(k-1)!(n-k+1)!}d_{k-1}\cdot\frac{n!}{(k+1)!(n-k-1)!}d_{k+1}\\
&= \frac{k}{k+1}\cdot\frac{n-k}{n-k+1}\cdot\left(\frac{k!(n-k)!}{n!}\right)^2 d_{k-1}d_{k+1}\\
&< \left(\frac{k!(n-k)!}{n!}\right)^2 d_{k-1}d_{k+1}\\
&\leq \left(\frac{k!(n-k)!}{n!}\right)^2 d_k^2 = s_k^2
\end{align*}
s k − 1 s k + 1 = ( k − 1 )! ( n − k + 1 )! n ! d k − 1 ⋅ ( k + 1 )! ( n − k − 1 )! n ! d k + 1 = k + 1 k ⋅ n − k + 1 n − k ⋅ ( n ! k ! ( n − k )! ) 2 d k − 1 d k + 1 < ( n ! k ! ( n − k )! ) 2 d k − 1 d k + 1 ≤ ( n ! k ! ( n − k )! ) 2 d k 2 = s k 2 特別地, 當 s k = 0 s_k=0 s k = 0 s k − 1 s k + 1 < 0 s_{k-1}s_{k+1}<0 s k − 1 s k + 1 < 0 □ \square □
這樣, 原問題大致就解決了. 唯一留下的一個小瑕疵是所有實根都非 0 0 0 0 0 0 n n n n n n 0 0 0