香港大学：Solving Polynomial Equations（2006.12.5）

Seminar on Advanced Topics in Mathematics Solving Polynomial Equations 5 December 2006 Dr.Tuen Wai Ng,HKU

Seminar on Advanced Topics in Mathematics Solving Polynomial Equations 5 December 2006 Dr. Tuen Wai Ng, HKU

What do we mean by solving an equation Example 1.Solve the equation z2 -1. x2=1 x2-1=0 (x-1)(x+1) =0 x=10r=-1 Need to check that in fact (1)2=1 and (-1)2=1. Exercise.Solve the equation Vx+Vx-a=2 where a is a positive real number

What do we mean by solving an equation ? Example 1. Solve the equation x 2 = 1. x 2 = 1 x 2 − 1 = 0 (x − 1)(x + 1) = 0 x = 1 or = −1 • Need to check that in fact (1)2 = 1 and (−1)2 = 1. Exercise. Solve the equation √ x + √ x − a = 2 where a is a positive real number

What do we i mean by solving a polynomial equation Meaning I: Solving polynomial equations:finding numbers that make the polynomial take on the value zero when they replace the variable. We have discovered that z,which is something we didn't know,turns out to be 1 or-1

What do we mean by solving a polynomial equation ? Meaning I: Solving polynomial equations: finding numbers that make the polynomial take on the value zero when they replace the variable. • We have discovered that x, which is something we didn’t know, turns out to be 1 or −1

Example 2.Solve the equation z2=5. x2 =5 x2-5 =0 (x-V5)(x+V5) =0 =50r-vV5 C ●But what is√5？Well,V5 is the positive real number that square to5. We have "learned"that the positive solution to the equation z2-5 is the positive real number that square to 5 !! So there is a sense of circularity in what we have done here. Same thing happens when we say that i is a solution of x2=-1

Example 2. Solve the equation x 2 = 5. x 2 = 5 x 2 − 5 = 0 (x − √ 5)(x + √ 5) = 0 x = √ 5 or − √ 5 • But what is √ 5 ? Well, √ 5 is the positive real number that square to 5. • We have ”learned” that the positive solution to the equation x 2 = 5 is the positive real number that square to 5 !!! • So there is a sense of circularity in what we have done here. • Same thing happens when we say that i is a solution of x 2 = −1

What are "solved"when we s solve t these equations The equations z2=5 and x2=-1 draw the attention to an inadequacy in a certain number system (it does not contain a solution to the equation). One is therefore driven to extend the number system by introducing,or adjoining',a solution. Sometimes,the extended system has the good algebraic properties of the original one,e.g.addition and multiplication can be defined in a natural way. .These extended number systems (e.g.Q(v5)or Q(i))have the added advantage that more equations can be solved

What are “solved” when we solve these equations ? • The equations x 2 = 5 and x 2 = −1 draw the attention to an inadequacy in a certain number system (it does not contain a solution to the equation). • One is therefore driven to extend the number system by introducing, or ‘adjoining’, a solution. • Sometimes, the extended system has the good algebraic properties of the original one, e.g. addition and multiplication can be defined in a natural way. • These extended number systems (e.g. Q( √ 5) or Q(i)) have the added advantage that more equations can be solved

Consider the equation x2=x+1. By completing the square,or by applying the formula,we know that the solutions are 15 or 15 2 2 It is certainly not true by definition that5 is a solution of the equation. 2 What we have done is to take for granted that we can solve the equation z2=5 (and similar ones)and to use this interesting ability to solve an equation which is not of such a simple form. When we solve the quadratic,what we are actually showing that the problem can be reduced to solving a particularly simple quadratic 2=c

Consider the equation x 2 = x + 1. • By completing the square, or by applying the formula, we know that the solutions are 1+√ 5 2 or 1− √ 5 2 . • It is certainly not true by definition that 1+√ 5 2 is a solution of the equation. • What we have done is to take for granted that we can solve the equation x 2 = 5 (and similar ones) and to use this interesting ability to solve an equation which is not of such a simple form. • When we solve the quadratic, what we are actually showing that the problem can be reduced to solving a particularly simple quadratic x 2 = c

What do we i mean by solving a polynomial equation Meaning Il: Suppose we can solve the equation xT=c,i.e.taking roots,try to express the the roots of a degree n polynomial using only the usual algebraic operations (addition,subtraction,multiplication,division)and application of taking roots. In this sense,one can solve any polynomials of degree 2,3 or 4 and this is in general impossible for polynomials of degree 5 or above

What do we mean by solving a polynomial equation ? Meaning II: Suppose we can solve the equation x n = c, i.e. taking roots, try to express the the roots of a degree n polynomial using only the usual algebraic operations (addition, subtraction, multiplication, division) and application of taking roots. • In this sense, one can solve any polynomials of degree 2,3 or 4 and this is in general impossible for polynomials of degree 5 or above

The Babylonians (about 2000 B.C.)knew how to solve specific quadratic equations. The solution formula for solving the quadratic equations was mentioned in the Bakshali Manuscript written in India between 200 BC and 400 AD. Based on the work of Scipione del Ferro and Nicolo Tartaglia,Cardano published the solution formula for solving the cubic equations in his book Ars Magna (1545). Lodovico Ferrari,a student of Cardano discovered the solution formula for the quartic equations in 1540 (published in Ars Magna later). The formulae for the cubic and quartic are complicated,and the methods to derive them seem ad hoc and not memorable

• The Babylonians (about 2000 B.C.) knew how to solve specific quadratic equations. • The solution formula for solving the quadratic equations was mentioned in the Bakshali Manuscript written in India between 200 BC and 400 AD. • Based on the work of Scipione del Ferro and Nicolo Tartaglia, Cardano published the solution formula for solving the cubic equations in his book Ars Magna (1545). • Lodovico Ferrari, a student of Cardano discovered the solution formula for the quartic equations in 1540 (published in Ars Magna later). • The formulae for the cubic and quartic are complicated, and the methods to derive them seem ad hoc and not memorable

Solving polynomial equations using circulant matrices D.Kalman and J.E.White,Polynomial Equations and Circulant Matrices,The American Mathematical Monthly,108,no.9,821-840,2001. Circulant matrices.An n x n circulant matrix is formed from any n-vector by cyclically permuting the entries.For example,starting with a b c we can generate the 3 x 3 circulant matrix (a b C= a b (1) 0 Circulant matrices have constant values on each downward diagonal,that is,along the lines of entries parallel to the main diagonal

Solving polynomial equations using circulant matrices D. Kalman and J.E. White, Polynomial Equations and Circulant Matrices, The American Mathematical Monthly, 108, no.9, 821-840, 2001. Circulant matrices. An n×n circulant matrix is formed from any n-vector by cyclically permuting the entries. For example, starting with [a b c] we can generate the 3 × 3 circulant matrix C =   a b c c a b b c a   . (1) • Circulant matrices have constant values on each downward diagonal, that is, along the lines of entries parallel to the main diagonal

The eigenvalues and eigenvectors of circulant matrices are very easy to compute using the nth roots of unity. For the 3 x 3 matrix C in (1),we need the cube roots of unity: 1,w=(-1+iv3)/2andw2=o. Direct computations show that the eigenvalues of C are a+b+ c,a+bw +cw2,and a+bw+cw2,with corresponding eigenvectors (1,1,1)T,(1,w,w2)T,and(1,⑦，2)T. This result can be generalized to higher dimensions (n>3)

The eigenvalues and eigenvectors of circulant matrices are very easy to compute using the nth roots of unity. • For the 3 × 3 matrix C in (1), we need the cube roots of unity: 1, ω = (−1 + i √ 3)/2 and ω 2 = ω. • Direct computations show that the eigenvalues of C are a + b + c, a + bω + cω2 , and a + bω + cω 2 , with corresponding eigenvectors (1, 1, 1)T , (1, ω, ω2 ) T , and (1, ω, ω 2 ) T . • This result can be generalized to higher dimensions (n ≥ 3)