Newton's Identities: Newton's Formula

Newton's identities (see here for an introduction to Newton's identities) are relationships between the roots of a cubic polynomial and its coefficients. They were first presented by Albert Girard but were presented in even greater detail independently by Sir Isaac Newton.

In today's blog, I will present Newton's formula and show how it leads to Newton's identities. In a future blog, I will provide the proof for the formula.

Definition 1: Newton's Formula for Newton's Identities

For a polynomial of degree n, with roots { r₁, ..., r_n }:

For any integer i, let s_i be the sum based on the roots:

s_i = r₁ⁱ + r₂ⁱ + ... + r_nⁱ.

For any integer j, Let σ_j be the elementary symmetric polynomial for j in n [see here for details if needed on elementary symmetric polynomials]

Then, Newton's formula is:



where σ₀ = 1 and if k is greater than n, σ_k=0.

We can now use it to build some equations for s_i and σ_j.

If k=1, then we have:

s₁ = σ₁

If k ≥ 2, then we have:

s_k = ∑ (i=1, k-1) (-1)ⁱ⁺¹s_k-iσ_i + (-1)^k+1kσ_k

Using the above formula gives us:

s₁ = σ₁

s₂ = s₁σ₁ - 2σ₂

s₃ = s₂σ₁ - s₁σ₂ + 3σ₃

s₄ = s₃σ₁ - s₂σ₂ + s₁σ₃ - 4σ₄

s₅ = s₄σ₁ - s₃σ₂ + s₂σ₃ - s₁σ₄ + 5σ₅

...

Now, building each formula based on the previous formula gives us the following formulas for s_k in term so of σ_i:

s₁ = σ1

s₂ = s₁σ₁ - 2σ₂ = (σ₁)σ₁ - 2σ₂ = σ₁² - 2σ₂

s₃ = s₂σ₁ - s₁σ₂ + 3σ₃ = (σ₁² - 2σ₂)σ₁ - (σ₁)σ₂ + 3σ₃ = σ₁³ -3σ₁σ₂ + 3σ₃

s₄ = s₃σ₁ - s₂σ₂ + s₁σ₃ - 4σ₄ = σ₁( σ₁³ -3σ₁σ₂ + 3σ₃) - σ₂(σ₁² - 2σ₂) + σ₃(σ₁) - 4σ₄ =

= σ₁⁴ - 3σ₁²σ₂ + 3σ₁σ₃ - σ₁²σ₂ + 2σ₂² + σ₁σ₃ - 4σ₄ =

= σ₁⁴ -4σ₁²σ₂ + 4σ₁σ₃ + 2σ₂² - 4σ₄

...

Further, we can use these same formulas for each σ_i so that:

σ₁ = s₁

σ₂ = (1/2)[s₁σ₁ - s₂]

σ₃ = (1/3)[s₃ - s₂σ₁ + s₁σ₂]

σ₄ = (1/4)[-s₄ + s₃σ₁ - s₂σ₂ + s₁σ₁

σ₅ = (1/5)[s₅ - s₄σ₁ + s₃σ₂ - s₂σ₃ + s₁σ₄]


Now, I will show these equations can be used to derive Newton's identities for cubic polynomials (that is, where n = 3). [See here for review of Newton's identities] where I am assuming an equation of the following form:

x³ + bx² + cx + d = 0

Here are the justifications for each formula presented previously.

Identity 1: r + s + t = -b

Proof:

σ₁ = r + s + t [See Definition 1, here]

σ₁ = (-1)¹(b) = -b [See Lemma 1, here]

QED

Identity 2: r² + s² + t² = b² - 2c

Proof:

s₂ = r² + s² + t² [See Definition 1 above]

s₂ = σ₁² - 2σ₂ [See formula above]

σ₁² - 2σ₂ = ((-1)¹b)² - 2(-1)²(c) = b² - 2c.

QED

Identity 3: r³ + s³ + t³ = -b³ + 3bc - 3d

Proof:

s₃ = r³ + s³ + t³ [See Definition 1 above]

s₃ = σ₁³ -3σ₁σ₂ + 3σ₃ [See formula above]

σ₁³ -3σ₁σ₂ + 3σ3 = [(-1)¹b]³ - 3(-1)¹b(-1)²c + 3(-1)³d =

= -b³ +3bc -3d.

QED

Identity 4: rs + rt + st = c

Proof:

σ₂ = rs + rt + sr + st +tr + ts [See Definition 1, here]

σ₂ = (-1)²c = c

QED

Identity 5: r²s + r²t + s²r + s²t + t²r + t²s = -bc + 3d

Proof:

(rs + rt + sr + st +tr + ts)(r + s + t) - 3rst = r²s + r²t + s²r + s²t + t²r + t²s

(rs + rt + sr + st +tr + ts)(r + s + t) - 3rst = σ₂σ₁ - 3σ₃ = (-1)¹b(-1)²c - 3*(-1)³d = -bc + 3d.

QED

Identity 6: r³s + r³t + s³r + s³t + t³r + t³s = b²c - 2c² - bd

Proof:

(r³ + s³ + t³)(r + s + t) - (r⁴ + s⁴ + t⁴) = r³s + r³t + s³r + s³t + t³r + t³s

(r³ + s³ + t³)(r + s + t) - (r⁴ + s⁴ + t⁴) =( s₃)(σ₁) - s₄

( s₃)(σ₁) - s₄ = (σ₁³ -3σ₁σ₂ + 3σ₃)(σ₁) - (σ₁⁴ - 4σ₁²σ₂ + 4σ₁σ₃ + 2σ₂² - 4σ₄) =

= σ₁²σ₂ - σ₁σ₃ - 2σ₂² + 4σ₄ = [(-1)b]²(-1)²c - 2[(-1)²c]² - [(-1)b(-1)³d] =

= b²c - 2c² - bd + 0 = b²c - 2c² - bd

QED

Identity 7: r²s² + r²t² + s²t² = c² - 2bd

Proof:

r²s² + r²t² + s²t² = (1/2)(r² + s² + t²)(r² + s² + t²) - (1/2)(r⁴ + s⁴ + t⁴) - =

= (1/2)s₂*s₂ - (1/2)s₄ =

= (1/2)(σ₁² - 2σ₂)(σ₁² - 2σ₂) - (1/2)( σ₁⁴ - 4σ₁²σ₂ + 4σ₁σ₃ + 2σ₂² - 4σ₄) =

= (1/2)σ₁⁴ - 2σ₁²σ₂ + 2σ₂² - (1/2)σ₁⁴ + 2σ₁²σ₂ - 2σ₁σ₃ - σ₂² + 2σ₄ =

= σ₂² - 2σ₁σ₃ + 2σ₄ =

= (c)² - 2*(-1)(b)(-1)(d) + 2*(0) = c² -2bd.

QED

Identity 8: r³s² + r³t² + s³r² + s³t² + t³r² + t³s² = -bc² + 2b²d + cd

Proof:

(1) (r²s² + r²t² + s²t²)(r + s + t) - (rst)(rs + rt + st) =
r³s² + r³t² + s³r² + s³t² + t³r² + t³s²

(2) (r²s² + r²t² + s²t²)(r + s + t) - (rst)(rs + rt + st) =

=(σ₂² - 2σ₁σ₃ + 2σ₄ )(σ₁) - (σ₃)(σ₂) =

= σ₁σ₂² - 2σ₁²σ₃ + 2σ₁σ₄ - σ₂σ₃ =

= (-1)b(c)² - 2(b)²(-d) + 2(-b)(0) - (c)(-d) =

= -bc² + 2b²d + cd

QED


Identity 9: r³s³ + r³t³ + s³t³ = c³ - 3bcd + 3d²

Proof:

(1) r³s³ + r³t³ + s³t³ = (r²s² + r²t² + s²t²)(rs + rt + st) - (r³s²t + r³st² + s³r²t + s³t²r + t³r²s + t³s²r )

(2) (r²s² + r²t² + s²t²)(rs + rt + st) - (r³s²t + r³st² + s³r²t + s³t²r + t³r²s + t³s²r ) = (c² - 2bd)(σ₂) - (bcd - 3d²) =

= (c² - 2bd)(c) - (bcd - 3d²) = c³ - 2bcd -bcd + 3d² =

= c³ - 3bcd +3d²

QED

Identity 10: rst = -d

Proof:

σ₃ = rst

σ₃ = (-1)³d = -d

QED

Identity 11: r²st + s²rt + t²rs = bd

Proof:

r²st + s²rt + t²rs = rst(r + s + t) = σ₃*σ₁ = (-1)(d)(-1)(b) = bd

QED


Identity 12: r³st + s³rt + t³rs = -b²d + 2cd

Proof:

(rst)(r² + s² + t²) = r³st + s³rt + t³rs

(rst)(r² + s² + t²) = σ₃s₂ =

= σ₃(σ₁² - 2σ₂) = (-d)(b² -2c) = -b²d + 2cd.

QED

Identity 13: r²s²t + r²st² + rs²t² = -cd

Proof:

(rst)(rt + rs + st) = r²s²t + r²st² + rs²t²

(rst)(rt + rs + st) = σ₃σ₂ = (-d)(c) = -cd.

QED
Identity 14: r³s²t + r³st² + s³r²t + s³t²r + t³r²s + t³s²r = bcd - 3d²

Proof:

(rst)[(rs + rt + st)(r + s + t) - 3rst] = r³s²t + r³st² + s³r²t + s³t²r + t³r²s + t³s²r
(rst)[(rs + rt + st)(r + s + t) - 3rst] = σ₃[(σ₂)(σ₁) - 3σ₃] =
σ₃[(σ₂)(σ₁) - 3σ₃] = (-1)d[c(-b) - 3(-1)d] = (-d)[-bc + 3d] = bcd - 3d²

QED

Identity 15: r³s³t + r³t³s + s³t³r = -c²d + 2bd²

Proof:

(rst)[(1/2)(r² + s² + t²)(r² + s² + t²) - (1/2)(r⁴ + s⁴ + t⁴) ] = r³s³t + r³t³s + s³t³r

(rst)[(1/2)(r² + s² + t²)(r² + s² + t²) - (1/2)(r⁴ + s⁴ + t⁴) ] =

= σ₃[(1/2)(s₂)(s₂) - (1/2)s₄ ] =

= σ₃[(1/2)(σ₁² - 2σ₂)(σ₁² - 2σ₂) - (1/2)( σ₁⁴ - 4σ₁²σ₂ + 4σ₁σ₃ + 2σ₂² - 4σ₄)] =

= σ₃[(1/2)σ₁⁴ - 2σ₁²σ₂ + 2σ₂² - (1/2)σ₁⁴ + 2σ₁²σ₂ - 2σ₁σ₃ - 2σ₂² + 2*0)] =

= σ₃[σ₂² -2σ₁σ₃] = (-1)d[(c)² - 2*(-1)b(-1)d] =

= (-d)[c² - 2bd] = -c²d + bd².

QED

Identity 16: r²s²t² = d²

Proof:

r²s²t² = (rst)² = (σ₃)² = [(-1)³d]² = d²

QED

Identity 17: r³s²t² + s³r²t² + t³r²s² = -bd²

Proof:

(rst)(rst)(r + s + t) = r³s²t² + s³r²t² + t³r²s²

(rst)(rst)(r + s + t) = σ₃²*σ₁ = (-b)d²= -bd²

QED

Identity 18: r³s³t² + r³t³s² + s³t³r² = cd²

Proof:

(rs + rt + st)(rst)(rst) = r³s³t² + r³t³s² + s³t³r²

(rs + rt + st)(rst)(rst) = σ₂*σ₃² = (c)(d)² = cd²

QED

Identity 19: r³s³t³ = -d³

Proof:

r³s³t³ = (rst)³ = (σ₃)³ = (-d)³ = -d³

QED

References

• "Newton's Identities", Wikipedia
  
• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001
• Harold M. Edwards, Galois Theory, Springer, 1984.

Newton's Identities: Vandermonde Matrix

In today's blog, I will provide a formula for obtaining the determinant of the Vandermonde matrix. For review of determinants of n x n matrices, start here.

This blog is part of the discussion of Newton's Identities. If you are interested in going to the beginning of this thread, then start here.

Definition 1: Vandermonde matrix V_n

The Vandermonde matrix is an n x n matrix where the jth column is the vector (x₁^j-1, x₂^j-1, ..., x_n^j-1).

So based on this definition, the Vandermonde matrix V_n =





Theorem 1:



Proof:

(1) Using elementary matrices (see Lemma 3, here), we know that:

I_{(-x1R1 + R2)}*I_{(-x2Rn-2 + R3)}*...*I_{(-xn-1Rn-1 + Rn)}*V_n =



(2) Using a basic property of determinants of matrices (see Definition 4, here), we know that:

det(I_{(-x1R1 + R2)}*I_{(-x2Rn-2 + R3)}*...*I_{(-xn-1Rn-1 + Rn)}*V_n) = det[I_{(-x1R1 + R2)]}*det[I_{(-x2Rn-2 + R3)}]*...*det[I_{(-xn-1Rn-1 + Rn)}]*det(V_n)

(3) Now, since det(I_{(kR1 + R2)}) = 1 (see Lemma 7, here), this gives us:

det(V_n) =



(4) We can further simplify this expression to be:

det(V_n) = det(M_1,1(V_n))

[See Corollary 3.1, here where M_1,1 is the Minor of Ent_1,1(V_n); see Definition 1 here for definition of the minor of a matrix; see Definition 1, here for definition of Ent_1,1(V_n) notation]

(5) Now, we know that M_1,1(V_n) =



=




(6) Using elementary matrices (see Corollary 4.2, here), we know that:

M_1,1(V_n) =



(7) Using step #4 gives us:

det(V_n) = det(M_1,1(V_n) =



(8) Since det(I_(kCi)) = det(I(kR_i) = k [see Theorem 9, here; see Lemma 4, here], we have:

det(V_n) =



(9) So, we have found ourselves in the same situation as step#1 except that we have eliminated x₁ as a column.

(10) If we repeat, the same process, we ultimately get:

det(V_n) =



(11) So, using the determinant formula for 2 x 2 matrices (see Property 5, here; see Lemma 1, here), we have:



QED

References

• "Vandermonde Matrix", Wikipedia.org
• "Proof of the Determinant of the Vandermonde Matrix", PlanetMath.org
• "Determinants", Toomas Lepikult, at http://www.cs.ut.ee/~toomas_l/
  

Newton's Identities: Fundamental Theorem on Symmetric Polynomials

In today's blog, I will present the Fundamental Theorem of Symmetric Polynomials. In my previous blog, I talked about symmetric polynomials and elementary symmetric polynomials. In today's blog, I show the relationship between the two.

The content in today's blog is taken straight from Harold M. Edwards' Galois Theory.

Theorem 1: Fundamental Theorem on Symmetric Polynomials

Every symmetric polynomial in r₁, ..., r_n can be expressed as a polynomial in elementary symmetric polynomials σ₁, ..., σ_n. In addition, a symmetric polynomial with integer coefficients can be expressed as a polynomial in elementary symmetric polynomials with integer coefficients.

Proof:

(1) For n=1, the symmetric polynomial is x - r₁ so that we see that a₁ = -r₁ and σ_i = (-1)¹(-r₁)=r₁

[See Definition 1, here for definition of symmetric polynomial; see Definition 2, here for definition of the kth elementary symmetric polynomial]

(2) if a₁ is an integer, then r₁ is an integer and σ₁ is an integer.

(3) The polynomial in elementary symmetric functions is then x - σ₁ which shows that the theorem is true for n=1.

(4) Let's assume that the theorem has been proved for all symmetric polynomials up to n-1.

(5) Let G(r₁, r₂, ..., r_n) be a symmetric polynomial in n variables so that:

G(r₁, r₂, ..., r_n) = (x - r₁)*(x - r₂)*...*(x - r_n)

(6) Let G_i be a series of polynomials such that:

G(r₁, r₂, ..., r_n) = G₀ + G₁r_n + G₂(r_n)² + ... + G_v(r_n)^v

where:

v is the highest power of r_n that occurs in G and each G_i is only made up of r₁, r₂, ..., r_n-1.

We can see that G₀ is a polynomial that doesn't include r_n. G₁ includes all multiples of (r_n)¹. G₂ includes all the multiples of (rn)² and so on up until v which is defined as the highest power of r_n which can be 1.

(7) Now, since G(r₁, r₂, ..., r_n) is a symmetric polynomial, it is unchanged if any two variables r_i and r_j are interchanged. [See Definition 1 here for definition of symmetric polynomial]

(8) Since G(r₁, r₂, ..., r_n) is unchanged with any interchange, so too are the polynomials defined by G_i are unchanged.

(9) This means that each G_i is itself a symmetrical polynomial on r₁, r₂ ... r_n-1.

(10) By the inductive hypothesis in step #4, we can assume that each G_i is itself expressible as an elementary symmetric polynomial in r₁, r₂, ..., r_n-1

(11) Let τ_i, τ₂, ..., τ_n-1 denote these elementary polynomials in (n-1) variables such that [See Definition 2 here for definition of elementary symmetric polynomials]:

τ₁ = r₁ + r₂ + ... + r_n-1

τ₂ = r₁r₂ + r₁r₃ + ... + r_n-2r_n-1
...

τ_n-1 = r₁r₂*...*r_n-1

[NOTE: Each τ_i represents the sum of all i-combinations of 1 ... n-1. So, τ₁ is the sum of all 1-combinations, τ₂ is the sum of all 2-combinations, and τ_n-1 is the sum of all n-1 combinations (for which there is only one)].

(12) So, from the inductive hypothesis, if we let G_i(r₁, ..., r_n-1) represent the symmetric polynomial G_i, we can see that there exists another polynomial g_i such that:

G_i(r₁, ..., r_n-1) = g_i(τ₁, τ₂, ..., τ_n-1)

(13) Further, from the inductive hypothesis, we know that if G_i has integer coefficients, then, so does g_i.

(14) Let σ₁, σ₂, ..., σ_n be the elementary symmetric polynomials in n variables.

(15) We can now restate σ_i in terms of τ_i since:

σ₁ = r₁ + r₂ + ... + r_n = τ₁ + r_n

σ₂ = r₁r₂ + r₁r₃ + ... + r_n-1r_n = τ₂ + r_nτ₁

[Note: r_n*τ₁ is equal to the sum of all (n-1) 1-combinations with r_n]

σ₃ = r₁r₂r₃ + r₁r₂r₄ + ... + r_n-2r_n-1r_n = τ₃ + r_nτ₂

[Note: r_n*τ₁ is equal to the sum of all (n-1) 2-combinations with r_n]

σ₄ = τ₄ + r_nτ₃

...

σ_n = r₁*r₂*....*r_n = 0 + r_n*t_n-1

[Note: the main idea here is the σ_i represents the sum of all i-combinations of n variables. We are now equating these sums with τ_i which represents the sum of all i-combinations of (n-1) variables. In other words, we are now including the new combinations with r_n.]

(16) We can now restate the equations in step #15 in terms of τ_i to get (using the basic algebraic operations of addition/subtraction to both sides of the equation):

τ₁ = σ₁ - r_n

τ₂ = σ₂ - r_nτ₁ = σ₂ - r_n(σ₁ - r_n) = σ₂ - r_nσ₁ + (r_n)²

τ₃ = σ₃ - r_nτ₂ = σ₃ - r_nσ₂ + (r_n)²σ₁ - (r_n)³.

...

τ_n-1 = σ_n-1 - r_nτ_n-2 = σ_n-1 - r_nσ_n-2 + ... + (-1)^n-1(r_n)^n-1

(17) Finally, we can use the last equation in step #15, to get:
0 = σ_n - r_nτ_n-1 = σ_n - r_nσ_n-1 + ... + (-1)ⁿ(r_n)ⁿ.

(18) Since we restate all the terms τ_i in terms of r_n and σ_i, we can define a polynomial f_i(σ₁, σ₂, ..., σ_n-1), such that using step # 12, we have:

G(r₁, r₂, ..., r_n) = f₀ + f₁(σ_n) + f₂(σ_n)² + ... + f_μ(σ_n)^μ

where each f_i is a polynomial strictly in terms of σ₁, σ₂, ..., σ_n-1 and does not include σ_n.

(19) Each f_i has integer coefficients if G does since:

(a) Using steps #16, we can state each f_i in terms of τ₁,...,τ_n-1

(b) From step #13, we know that τ₁,...,τ_n-1 have integer coefficients if G has.

(20) From step #17, we get the following:

(r_n)ⁿ = (r_n)^n-1σ₁ - (r_n)^n-2σ₂ + (r_n)^n-3σ₃ + ... + (-1)^n-1σ_n

(21) If μ ≥ n, then we can continuously apply the result in step #18 to the result in step #20, to get:

G(r₁, r₂, ..., r_n) = f₀(σ) + f₁(σ)r_n + f₂(σ)(r_n)² + ... + f_n-1(σ)(r_n)^n-1

(22) Since interchanging any values r_i with r_j doesn't change the value of G(r₁, r₂, ..., r_n), then it doesn't change the value of f₀(σ) + f₁(σ)r_n + f₂(σ)(r_n)² + ... + f_n-1(σ)(r_n)^n-1

(23) By repeatedly interchanging distinct r_i and r_j values where i ≠ j, we get the following n set of equations using step #21:

G(r₁, r₂, ..., r_n) = f₀ + f₁r₁ + f₂(r₁)² + ... + f_n-1(r₁)^n-1
G(r₁, r₂, ..., r_n) = f₀ + f₁r₂ + f₂(r₂)² + ... + f_n-1(r₂)^n-1
...

G(r₁, r₂, ..., r_n) = f₀ + f₁r_n + f₂(r_n)² + ... + f_n-1(r_n)^n-1

(24) We can think of these n equations of n terms as an n x n matrix of the form (r_i)^j-1 where i = the column (1 ... n) and j = the row (1 ... n).

(25) The determinant of this matrix which is a polynomial in r₁, r₂, ..., r_n is nonzero since this is an example of the transpose of the Vandermonde Matrix [see Definition 1, here] and:

(a) From the properties of determinants, we know that det(V_n) = det(V_n^T) [See Theorem 9, here]

(b) The formula for the determinant of the Vandermonde matrix is (see Theorem 1, here):




(c) Since by assumption r₁ ≠ r₂ ≠ ... ≠ r_n [since each of the parameters is distinct], we can conclude that det(V_n) ≠ 0.

(26) We can think of the set of equations as a multiplication between the above matrix [(r_i)^j-1] and the vector [f₀(σ), f₁(σ), ..., f_n-1(σ)] [See here for review of matrix multiplication] since:





(27) But, the the set of equations is also the result of multiplying the vector[G,0,0,...,0] since:

(a) We have the following equation:





(b) From step #23, we have:



=



(c) So we can conclude that the following two equations are equal:






(28) Since the determinant in step #24 above is nonzero, the matrix is invertible (see Theorem 4, here) and we can multiply its inverse to both sides to get:



(29) From this, we can conclude that:

f₀ = G and f₁=0, ..., f_n-1=0. [See Definition 2, here]

(30) Since f₀ is an elementary symmetric polynomial (see step #18 above) and since f₀ has integer coefficients if G does (see step #19 above), the conclusion follows from mathematical induction (see here for review of mathematical induction).

QED

In my next blog, I will complete the proof by reviewing the formula for the determinant of the Vandermonde Matrix. In a future blog, I will show how this theorem can be used to derive Newton's identities.

References

• Harold M. Edwards, Galois Theory, Springer, 1984.