Thursday, January 29, 2009

Degree of a Polynomial

Definition 1: Degree of a polynomial

The highest nonzero exponent is the degree of the polynomial.

As a convention, the degree of a zero polynomial is said to be -∞.

Lemma 1: deg(A+B) ≤ max(degA,degB)

Proof:

(1) We start with with deg A = 0, deg B=0 where A ≠ -B [We can ignore deg = - ∞ since by the Additive Identity Property (see here), it is true]

(2) A+B ≠ 0, so deg(A+B) = 0

(3) Assume that this is true up to deg A, deg B ≤ n-1.

(4) Let:

A = anxn + ... + a0

B = bnxn-1 + ... + b0

(5) We can assume that an ≠ -bn [Since if this is the case, the n degrees cancels out and the proposition is true by the inductive hypothesis.]

(6) an + bn = (a+b)n [See here for Additive Rule for Polynomials]

(7) So the deg(A+B) = n

QED

Lemma 2: deg(AB) = deg(A) + deg(B)

Proof:

(1) Assume deg A = 0, deg B = 0

(2) Then deg(AB) = 0 = 0 + 0

(3) Assume that the proposition is true up to n-1

(4) Let:

A = anxn + ... + a0

B = bnxn-1 + ... + b0

(5) The highest exponent will be an*bn = (a*b)n+n

(6) deg(a*b)n+n = 2n = deg(a) + deg(b)

QED

References