Newton's Identities: Euler's Generalization

As mentioned earlier, Sir Isaac Newton's main purpose in coming up with his "identities" (see here for introduction to Newton's Identities) was to find a formula for determining whether two cubic equations possessed a common root.

Leonhard Euler was able to find a very general solution for finding this formula for any two equations of any degree. This general solution is today known as a resultant.

In today's blog, I will show the general solution for the resultant and then show that this equation has the properties that it equals 0 if and only if two equations have at least one solution in common.

The content in today's blog is taken from Galois' Theory of Algebraic Equations by Jean-Pierre Tignol.

Definition 1: Resultant

Let P = a_nXⁿ + a_n-1X^n-1 + ... + a₁X + a₀ where a_n ≠ 0

Let Q = b_mX^m + b_m-1X^m-1 + ... + b₁X + b₀ where b_m ≠ 0

The resultant of P and Q is the determinant of the following (m+n) x (m+n) matrix:



For review of computing the determinant using the method of cofactor expansion, see here.

Here is the theorem justifying this construction:

Theorem: Common Roots of Two Polynomials

Let P,Q be the polynomials described in definition.

Let R be the resultant of P,Q

R = 0 if and only if P,Q have a common root

Proof:

(1) Assume that P,Q have a common root u

(2) Then (x - u) divides both P,Q and there exists P₁, Q₁ such that:

P = (x - u)P₁

Q = (x - u)Q₁

and degree of P₁ is less than degree of P [See Theorem here for details]
and degree of Q₁ is less than degree of Q [See Theorem here for details]

(3) We can also see that:

Q₁ = Q/(x - u)
P₁ = P/(x - u)

(4) So that:

PQ₁ = (x - u)P₁*Q/(x - u) = QP₁

(5) We can see that P,Q,P₁,Q₁ are all polynomials and:

There exists a_i such that:

P = a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀

where a_n ≠ 0.

There exists b_j such that:

Q = b_mx^m + b_m-1x^m-1 + ... + b₁x + b₀

where b_m ≠ 0

There exists z_k such that:

P₁ = -(z₁x^n-1 + z₂x^n-2 + ... + z_n-1x + z_n)

where z₁ ≠ 0

There exists y_l such that:

Q₁ = y₁x^m-1 + y₂x^m-2 + ... + y_m-1x + y_m

where y₁ ≠ 0

(6) From step #4, we can see that:

PQ₁ - QP₁ = 0

(7) In the expression in step #6, we can see that the coefficient for x^k = ∑ (i+j=k) (a_iy_m-j) + ∑ (i+j=k) (b_iz_n-j) since:

(a) For each term i in P, a_i is the coefficient for xⁱ

(b) For each term j in Q₁, y_m-j is the coefficient for x^j.

Consider 1 = m - (m-1); 2 = m - (m - 2); m-1 = m - (1); m = m - (0)

(c) For PQ₁, the coefficient is ∑ (i+j=k) (a_iy_m-j)

(d) For each term i in Q, b_i is the coefficient for xⁱ

(e) For each term j in P₁, -z_n-j is the coefficient for x_j.

Consider 1 = n - (n-1); 2 = n - (n-2); n-1 = n - (1); n = n - (0)

(f) For QP₁, the coefficient is ∑ (i+j=k) (-b_iz_n-j)

(g) For PQ₁ - QP₁, then, the coefficient is:

∑(i+j=k) (a_iy_m-j + b_iz_n-j) = ∑ (i+j=k) (a_iy_m-j) + ∑(i+j=k) (b_iz_n-j)

(8) We can further simplify this expression by defining s,t such that:

s = m-j
t = n-j

so that:

j = m - s = n - t

and:

i + j =k → i + m - s = k → i - s = k - m

i + j = k → i + n - t = k → i - t = k - n

which gives us:

∑ (i+j=k) (a_iy_m-j) + ∑(i+j=k) (b_iz_n-j) =

∑ (i - s = k - m) (a_iy_s) + ∑ (i - t = k - n) (b_iz_t)

(9) Now since the degree of P is n, the degree of P₁ is n-1, the degree of Q is m, and the degree of Q₁ is m-1, it follows that the degree of PQ₁ = m+n-1 and the degree of QP₁ = m+n-1.

(10) So, we can use the result in step #6 and the result in step #9 to build m + n linear equations where each linear equation represents a different value of k since the sum of coefficents for each power of x must equal 0.

for k = m + n - 1, we have:

a_ny₁x^(m+n-1) + b_mz₁x^(m+n-1) = 0

for k = m + n - 2, we have:

a_ny₂x^(m+n-2) + a_n-1y₁x^(m+n-2) + b_mz₂x^(m+n-2) + b_m-1z₁x^(m+n-2) = 0

...

for k = 1, we have:

a₁y_mx¹ + a₀y_m-1x¹ + b₁z_nx¹ + b₀z_n-1x¹ = 0

for k = 0, we have:

a₀y_m + b₀z_n = 0

(11) Factoring out x^k from each of these equations, gives us:

for k = m + n - 1, we have:

a_ny₁ + b_mz₁ = 0

for k = m + n - 2, we have:

a_ny₂ + a_n-1y₁ + b_mz₂ + b_m-1z₁ = 0

...

for k = 1, we have:

a₁y_m + a₀y_m-1 + b₁z_n + b₀z_n-1 = 0

for k = 0, we have:

a₀y_m + b₀z_n = 0

(12) For each of these linear equations, we can view the unknowns as consisting of y_s and z_t so that we get the following matrix representing a homogeneous system of linear equations:



(13) Now, it is clear that the equation above is none other than:

RX = 0

(14) We also know that there exists a nontrivial solution since from step #5 above,



(15) Since a nontrivial solution exists, we know that det R = 0 [See Theorem 6, here]

(16) Assume that det(R)=0

(17) It follows that R can be expressed as a homogeneous system of linear equations with a nontrivial solution. [See Theorem 6, here]

(18) We can label this nontrivial solution the same step #14 above:



(19) Multiplying out R with the nontrivial solution gives us the same set of m+n equations as step #11 above:

for the first equation, we have:

a_ny₁ + b_mz₁ = 0

for the second equation, we have:

a_ny₂ + a_n-1y₁ + b_mz₂ + b_m-1z₁ = 0

...

for the (m+n-1)th equation, we have:

a₁y_m + a₀y_m-1 + b₁z_n + b₀z_n-1 = 0

for the (m+n)th equation, we have:

a₀y_m + b₀z_n = 0

(20) Since these are the exact same as step #11, we know that we can factor them out into P,Q,P₁,Q₁ just as we did in step #6 and step #7 above.

(21) To complete this proof, let's assume that P and Q are relatively prime -- that is, they don't have at least one solution in common.

(22) Using PQ₁ = QP₁, we conclude that P must divide P₁ since it cannot divide Q (since P,Q are relatively prime).

(23) But this is impossible since P₁ has a lower degree than P.

(24) Therefore, we have a contradiction and we can conclude that P and Q have a solution in common.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001