9.   Non-linear Algebra and Non-Linear Equations

2016-05-23

$Version

9.1 Finding Characteristic  Quantities  of Algebraic Expressions

Coefficient[expr, form]  		coefficient  of  form  in  expr  

	CoefficientList[poly, form] 	give a list of the coefficients of powers of
						 	 form in polynomial poly
	
	CoefficientList[poly,{var1 var2,... }]	give an array of coefficients of va(Subscript[r, i])	  
   	
   	Exponent[expr]     		maximum power of  form  in  expr  
   		
    	Part[expr, n]            	n-th term of expr		

	Numerator[expr]          	numerator (German: Zähler) of expr	
 		
 	Denominator[expr]        	denominator (German: Nenner) of expr

Clear[e,x,y]

e = Expand[ (1 + 3 x + 4 y^2 )^2]

Coefficient[e, x]

Coefficient[e, y]

Coefficient[e, y^2]

Exponent[e,y]

pp = 17 + 2x y^2 + 3 x^3 y

CoefficientList[pp, x]

CoefficientList[pp, y]

CoefficientList[pp, {x,y}]

CoefficientList[pp, {y,x}]

The dimensions of the array returned by  CoefficientList  are determined by the values of  Exponent[poly, vari].

Exponent[pp,x]

Exponent[pp,y]

Part[e,5]

f = 2/3

Denominator[f]

Numerator[f]

s

Numerator[s]

Denominator[s]

9.2  Algebraic Operations on Polynomials

Clear[x, p1, p2 , q, r]

p1(x) = p2(x) * q(x)  +  r(x)

PolynomialQuotient[poly1, poly2,  x] 

	       	find the  result  of  dividing  poly1  in  x   by  poly2, dropping any remainder  term

PolynomialRemainder[poly1, poly2,  x] 

			find the  remainder  of dividing  poly1  in  x   by  poly2

Factor[poly]   	factor  the polynomial    poly

p1 = x^3 - 1

p2 = x - 1

PolynomialQuotient[p1, p2, x]

PolynomialRemainder[p1, p2, x]

Factor[p1]

p1 = x^3 - 2

Factor[p1]

PolynomialQuotient[p1, p2, x]

PolynomialRemainder[p1, p2, x]

PolynomialRemainder[x^2, x + 1, x]

PolynomialQuotient[x^2, x + 1, x]

{PolynomialRemainder[x + y, x - y, x], 
 PolynomialRemainder[x + y, x - y, y]  }

p1 = (x + 2)(x + 1)(x + 3); p1 = Expand[p1]

p2 = (x + 3)(x + 2)(x - 1); p2 = Expand[p2]

PolynomialGCD[poly1, poly2]	find the greatest  common divisor of two polynomials                     	    

PolynomialLCM[poly1, poly2]  	find the least common multiple of two polynomials

PolynomialGCD[p1, p2]//Factor

PolynomialLCM[p1, p2]//Factor

Resultant[poly1, poly2]		find the resultant  of two polynomials; this is zero if 									these  have (a) common root(s)

p1=((Sqrt[2])-x) (x+1) (((x+(Sqrt[2])))^2);p1=Expand[p1]

Clear[a]
p2=((x^3)+3 (x^2) + a)  ;p2=Expand[p2]

Solve[p1 == 0,x]

Solve[p2 == 0,x]

For which values of the variable a can the polynomials  p1(x)  and  p2(x) have a common root ?

Resultant[p1, p2, x]

so = Solve[% == 0,a]//Union

p11 = p1 /. so[[1]]//Factor
p21 = p2/. so[[1]]//Factor

a = - 2:  -1  is a common root of  p1  and  p2.

p11 = p1 /. so[[2]]//Factor
p21 = p2/. so[[2]]//Factor
Solve[p21 == 0]

a=2 (-3-(Sqrt[2])) :   (Sqrt[2])   is a common root of  p1  and  p2.

p11 = p1 /. so[[3]]//Factor
p21 = p2/. so[[3]]//Factor
Solve[p21 == 0]

a=2 (-3+(Sqrt[2]) : -(Sqrt[2])  is a common root of  p1  and  p2.

Often it is impossible to compute the roots of complicated polynomials. Even in such cases the Resultant[] tells us whether two polynomials have common roots. It assumes the value zero if there are common roots.

Resultant[ (x - y)^2  - 2, y^2 - 3, y]

Resultant[ (x - y)^2  - 2, y^2 - 3, x]

9.2.1  Field Extensions

In higher algebra a set  𝒦  of numbers or/and symbols is called a field (German: Körper) if 
	1. it is closed under addition and multiplication,
	2. is associative and commutative under both operations;
	3. contains a unique unit element  e;
	4. contains the solution x of any equation a + x = b, with arbitrary a, b ϵ 𝒦,
	5. contains the solution x of any equation   a x = b, with arbitrary  a ≠ 0, b ϵ 𝒦.
Examples are:
	ℚ, the field of all rational numbers  p/q,  with p, q  (q ≠ 0)  any integers.
	ℝ,  the field of all real numbers. 
	ℂ  the field of all complex numbers = ℝ[i] with i = (Sqrt[- 1]), the imaginary unit. 
	
It may well be possible that a non-linear equation cannot be solved over a field. For example,
take the equation:		
					(x^2) + 1 = 0

over the field  𝒦 = ℝ, the real numbers. This does not contain the imaginary unit i; so the above equation cannot be solved within ℝ. By joining the imaginary unit i to   ℚ  or  ℝ, these fields are  extended to that of the Gaussian rational field (= rational complex numbers)  ℚ[i] or the field of
all complex numbers  ℂ = ℝ[i] . The above equation has the two solutions  ± i within ℂ = ℝ[i]. 
Such an addition is called a field extension.
Similarly,   the equation:		
					(x^2) - 2 = 0
has no solutions over the field of fractions of integers  𝒦 = {a/b, b ≠ 0, a, b  ϵ  ℤ} = ℚ, but it has the solutions  ± (Sqrt[2])over the field  𝒦 = ℚ[(Sqrt[2])], So the above quadratic polynomial does not factor over 𝒦 = ℚ, but it does factor over 
	𝒦 = ℚ[(Sqrt[2])]:   		(x^2) - 2 = ( x - (Sqrt[2]))(x  + (Sqrt[2])).
Such an extension can be implemented in Mathematica in two ways:

9.2.2.1    Using the option  Extension

Factor[poly, Extenssion -> {(Subscript[a, 1]),(Subscript[a, 2]),....}]  factors  poly over the field  									ℚ[(Subscript[a, 1]), (Subscript[a, 2]), ....  ]

Factor[(x^2)- 2]

Factor[(x^2)- 2, Extension -> {(Sqrt[2])}]

Factor[(x^2)+ 2, Extension -> {I,(Sqrt[2])}]

Factor[3x^2 - 2 y^2,Extension -> {(Sqrt[2]),(Sqrt[3])}]

Now a cubic root is considered: α = (2^(1/3)), the real  solution of the following polynomial:

ff = Factor[x^3 - 2, Extension -> {(2^(1/3))}]

so = Solve[ff[[3]]== 0]

Factor[x^3 - 2, Extension -> {I ,(Sqrt[3]),(2^(1/3))}]

9.2.1.2	   By joining a polynomial and using PolynomialRemainder

Clear[α]
pa = (α^3)  - 2;

In the extended field  ℚ[α]{a+b α+c (α^2),a,b,c ∈ℚ}  any number  f(a + b α  + c (α^2))
 (f(x) a polynomial operator of x) may be given as   a1 + b1 α+c1 (α^2)  with  a1, b1, c1 ϵ  ℚ, Higher powers of α resulting from operations involving several such numbers are remomved 
with the help of PolynomialRemainder.
For example, the product  a+b α + c (α^2)  of two such numbers a1+b1 α + c1 (α^2) and a2+b2 α + c2 (α^2)
is expressed as:
			(a1+b1 α + c1 (α^2))(a2+b2 α+ c2 (α^2)) = a+b α + c (α^2) .

The coefficients a, b, c representing the product  a+b α + c (α^2)  of the two numbers can be expressed by  a1, a2, b1, b2, c1, c2  as given below in sopr. The corresponding formulae are found in the following way:

pr =(a1+b1 α + c1 (α^2))(a2+b2 α+ c2 (α^2)) //Expand

PolynomialRemainder[pr, pa,α ] -  (a+ b α + c (α^2))

Thread[CoefficientList[%,α]== Table[0,{Exponent[pa,α]}]]

sopr = Solve[%,{a,b,c}]//Flatten

pr = (a+ b α + c (α^2))/. sopr

The inverse element  inv  of   na  is found in the following way:

Clear[a,b,c,a1,b1,c1]
na = a1+b1 α + c1 (α^2)  ;

inv = a+b α + c (α^2)   ;

na.inv = 1 = ( a1+b1 α + c1 (α^2))(a+b α + c (α^2))

CoefficientList[PolynomialRemainder[( a1+b1 α + c1 (α^2))(a+b α + c (α^2)),pa,α],α] == {1,0,0};

so = Solve[%,{a,b,c}]//Flatten

inv = a+b α + c (α^2)   /. so

ai = na inv //Expand//Together

PolynomialRemainder[ai,pa,α]//Together

9.3  Solving Polynomial Equations

Solve[poly ==  0,  var]		Solves the algebraic equation  in  var  by radicals 
						     if Mathematica can  find such  a solution.
							 
NSolve[poly ==  0,  var]		Gets an approximate  numeric solution to the algebraic 						      equation in  var							 
NSolve[poly ==  0,  var, n]		Gets solutions  to  n-digit precision  (but does not 							      always  succeed  as  wanted)	

RootReduce[expr] 				 Attempt ro reduceexpr to a single Root object

Solve[ x^6 == 1, x]

p = 3 + 3 x - 7 x^2 - x^3 + 2 x^4 + 3 x^7 - 3 x^8 - x^9 + 
	x^10

Solve[p == 0, x]

Last entry -> running index of the roots; # ... unknown; the empersant symbol & closes the pure  function.

N[%,30]

q = x^6 - 9 x^4 - 4 x^3 + 27 x^2 - 36 x - 23

Solve[q == 0, x]

Even if a polynomial comprises higher powers than the fourth one, it may be possible to express its zeros by formulas involving root expressions. If Mathematica gives the answer in the Root form as above, this is no exact indication that zeros cannot be expressed by formulas involving roots. The sixth order polynomial   q   given above is such an example.  x1 and x2 are two such zeros of this polynomia, which can be expressed by roots:

Factor[q]

x1 = 2^(1/3) + 3^(1/2); 
N[%]

q /. x -> x1

ExpandAll[%]

RootReduce[%%]

x2 = 2^(1/3) - 3^(1/2); 
N[%]

Factor[q]

Factor[q, Extension -> {x1,x2}]

tr =Table[{x -> 2^(1/3) E^(I 2Pi k/3) + Sqrt[3] (-1)^n },
	{k,3},{n,2}]

q /. tr //FullSimplify

Solve[(Sqrt[-x] - a)^2 ==  b^2, x]

Solve[(Sqrt[-x] - a)^2 == 1. * b^2, x]

According to the theory of Evariste Galois the roots of every equation up to and including the 4th order can be expressed by radicals (= expressions involving only fractions and roots).  For equations of higher order this is possible in exceptional cases only.  Galois' theory based on group theory gives a means to investigate this question. Mathematica does not give such solutions even if this is possible in some of such cases.  If Mathematica gives the answer in the Root form as above, 
this is no exact indication that zeros cannot be expressed by formulas involving roots. The sixth order polynomial  q  given above is such an example.

For some cubic equations all zeros are real, but is impossible to get exact root expressions
without the imaginary unit i (casus irreducibilis). The polynomial below is such a case:

p =(x^3)+(x^2)-20x-9;

Solve[p == 0,x]

N[%]//Chop

ComplexExpand[x /. %]

The above expressions are throughout real, but they contain the imaginary unit  i   necessarily.

eq = a x^4 + b x^3 + c x^2 + d x + e == 0

Solve[eq,x] ;  (* The output fills 5 pages *)

RootReduce[expr] 		Attempt to reduce  expr  to a single Root object

ToRadicals[expr] 		Attempt to transform  Root objects to explicit radicals

p = x^3 + 2x- 2

so = Solve[p == 0]

(x /. so[[2]]) (x /. so[[3]])

RootReduce[%]

ToRadicals[%]

SolveAlways[eq,  {x,y}]		gives the values  of the parameters  that make the equation  eq 
 					valid for all  values of the variables   x  and y

Clear[a,b,x,y,r]
eq = (x^2 + 12 x + y^2 - 20 y + 15 == (x - a)^2 + (y - b)^2 - r^2);
Solve[eq,{a,b,r}]

Solve::svars: "Equations may not give solutions for all "solve" variables.

Above  eq  has been regarded as an equation for the single unknown  r. One may look at eq in a different way: There are two different expressions on the left-hand and on the right-hand side. On asks: for which values of  a, b, r are the sides identical functions in  x  and y ?

soa=SolveAlways[eq,{x,y}]

eq /. soa

FullSimplify[%]

??Eliminate

eqs = x^2+y^2+z^2==1&&x-y+z==2&&x^3-y^2==z+1

Eliminate[eqs,z]

Eliminate[eqs,{y,z}]

Eliminate[Sqrt[x]+Sqrt[y-1]==1&&2x^(1/3)+3 y^2==2,y]

9.3.1  Solving Polynomial Equations. History and Further Developements

Any polynomial equation up to the 4 th degree with real or complex coefficients

	(Subscript[p, 4])(x) := (Subscript[a, 4]) (x^4) + (Subscript[a, 3]) (x^3) + (Subscript[a, 2]) (x^2) + (Subscript[a, 1]) x + (Subscript[a, 0])  =  0				(1)

can be solved by radicals; i.e. it can by solved by addition, subtraction, multiplication, division and root extraction.This is acomplished by Mathematica by the command Solve[] as long as eq.(1) does not contain any decimal numbers. 
Of course, any polynomial equation has as many roots as its degree (counting multiplicities). But these can be expressed in any case by the five operations just listed only up to poynomials of the fourth degree. This is the content of Abel's impossibility theorem. Some special polynomial equations of degree 5 or higher may still be solvable by radicals. It is no proof to the contrary if Solve[] does not succeed in finding such a solution of an equation. The theory of Galois is a 
means to check whether an equation is solvable by radicals.

The solution theory of the polynomial equation of fifth degree was developed by Brioschi, Hermite and Kronecker.
A comprehensive representation of this work was given by F. Klein. A reedition of Klein’s book by Slodowy contains an introduction, a decription of further work and a list with more recent references. 

F, Klein: Vorlesungen ueber das Ikosaeder und die Auflösung der Gleichung fünften Grades.
 Birkhäuserverlag, Basel, 1993. Neuausgabe des 1884 erschienenen Werkes, hier mit einem 
 umfangreichen Vorwort und nachstehendem Kommentar von P. Slodowy.

The historical developement of the solution theory is listed in the notes
 M9EquationsHistory.doc.

9.3.2  Solving Inequalities

Reduce[Abs[-3+x]<= (x+1)Abs[4+x],x, Reals]

v0 = Last[%]//N

Plot[-Abs[-3+x]+(x+1) Abs[4+x],{x,-5,1},PlotRange->{-9,4},AspectRatio->0.3`,Epilog->{Thickness[0.01`],Hue[0],Line[{{v0,0},{1.1`,0}}]}]

Reduce[x (x^2 - 2) (x^2 - 3) > 0, x, Reals]

Plot[x ((x^2)-2) ((x^2)-3),{x,-2,2},PlotRange->3 {-1,1},AspectRatio->0.4`,Epilog->{Thickness[0.01`],Hue[0],Line[{{-(Sqrt[3]),0},{-(Sqrt[2]),0}}],Line[{{0,0},{(Sqrt[2]),0}}],Line[{{(Sqrt[3]),0},{2.1`,0}}]}]

In the example below the unknowns are  restricted  to

Clear[x1, x2, x3]
tx = {x1,x2,x3^2};

ma = {{2,1,3},{4,3,5}}; MatrixForm[ma]

ma.tx <= {7,9}//Thread;
sys = {ungl1,ungl2} = %

Reduce[Join[sys,
{(x1==0||x1==1),(x2==0||x2==1),(x3==0||x3==1)}],
                {x1,x2,x3}]

Tnis result  is translated  into sets  of substitions:

sos = {{x1 -> 0, x2 -> 0, x3 -> 0},
       {x1 -> 0, x2 -> 0, x3 -> 1},
       {x1 -> 0, x2 -> 1, x3 -> 0},
       {x1 -> 0, x2 -> 1, x3 -> 1},
       {x1 -> 1, x2 -> 0, x3 -> 0},
       {x1 -> 1, x2 -> 0, x3 -> 1},
       {x1 -> 1, x2 -> 1, x3 -> 0}};

sys /. sos

9.3.2  Solving Transcendental Equations

Solve[Cos[x] == 0,x]

Solve::"ifun" : 
Inverse functions are being used by Solve,so some solutions may not be found;
 use Reduce for complete solution information.

Reduce[Cos[x] == 0,x]

This gives all roots.

Solve[Sin[x] +3 Cos[x] == 0,x]

Solve::"ifun" : 
Inverse functions are being used by Solve,so some solutions may not be foundÖ
 use Reduce for complete solution information.

N[%]

Reduce[Sin[x] +3 Cos[x] == 0,x]

This gives all roots. These consist of either one of the basis expressions given below plus 2π x an integer.

N[{2 ArcTan[(1/3) (1+(Sqrt[10]))],2 ArcTan[(1/3) (1-(Sqrt[10]))]}]

9.4  Reduce

??Reduce

Clear[n,q,x,y]

Reduce[x^2+y^2<1,{x,y}]

Reduce[x^2-7y^2==1&&x>0&&y>0,{x,y},Reals]

Reduce[Exists[{x,y},x^2+a y^2≤1 &&x-y≥2],a]

Reduce[2 x+3y-5z==1&&3x-4y+7z==3,{x,y,z},Reals]

Reduce[Abs[3x^2-7x-6]<Abs[x^2+x],x,Reals]

Reduce[BesselJ[n-1,q]-2 n/q BesselJ[n,q]+BesselJ[n+1,q]==0,{q}]

Reduce::fexp: “Warning: Reduce used FunctionExpand to transform the system. Since FunctionExpand transformation rules 
are only generically correct, the solution set might have been altered.”

Limit[BesselJ[n-1,q]-2 n/q BesselJ[n,q]+BesselJ[n+1,q],{q -> 0}]

9.5  Finding Approximate Roots of Expressions by Iterative Methods

9.5.1	One Unknown

FindRoot[exp,{x,(Subscript[x, 0])}] searches for a root of the algebraic or transcendental expression 				exp  starting the iteration with   x = (Subscript[x, 0]).
				
FindRoot[exp,{x,(Subscript[x, 0]),(Subscript[x, 1])}]	if  Mathematica cannot find the derivative of exp  then it needs 				    	two starting values   (Subscript[x, 0]),(Subscript[x, 1])   to work with secants

This works also for complex expressions. It finds complex roots of real expressions.

FindRoot[Sin[x] + 3 Cos[x] ,{x,2.1} ]

f = z^2 + Conjugate[z] + 2 I

FindRoot[f,{z,1 +2 I}]

f /.%

This shows that it is important to find a good starting value. Therefore we plot the complex function:

Plot3D[Abs[f/.z->x+I y],{x,-3,3},{y,-3,3}]

FindRoot[f,{z,2 -2 I}]

f /.%

FindRoot[f,{z,- 1}]

f /.%

One may give also two starting vales. In some cases FindRoot[] even asks for this.

Clear[x,fx]

fx = Sin[x] + x - 2;

p1=Plot[(E^(Abs[x]))-2,{x,-1,1},PlotLabel->"(E^(Abs[x])) - 2\n"];
p2=Plot[fx,{x,0,2},PlotLabel->fx];
Show[GraphicsRow[{p1,p2}],ImageSize->400]

FindRoot[(E^(Abs[x]))==2,{x,1}]

9.4.1.1	Roots with Higher Precision

FindRoot[fx,{x,1},MaxIterations->50,
	AccuracyGoal->24,WorkingPrecision->34]

fx /. %

9.5.2	n Expressions for n  Unknowns

Solve[{x^3 - y^2 == 0, x + y == 2},{x,y}]

ContourPlot[{x^3 - y^2 == 0, x + y == 2},{x,0,2},{y,0,2}]

FindRoot[{x^3 - y^2, x + y  -2},{x,1},{y,2}]

FindRoot[{x^3 - y^2, x + y  -2},{x,I},{y,2I}]

Chop[%]

FindRoot[{x^3 - y^2, x + y  -2},{x,I},{y,-2I}]

Chop[%]

9.5.2.1	Roots with Higher Precision

FindRoot[{x^3 - 2 y^2, x + y  -2},{x,I},{y,-2I},
AccuracyGoal->24,WorkingPrecision->34]

9.6	Exercises

9.1.   Divide  the polynomial   f   by the polynomial  g.  Find the quotient and  the remainder.  

	 1)	f   =  x6  -  5 x5  +  4 x4  -  2 x3  +  3 x2  -  x  -  1, 	g  =  x2 -  x  +  1;
	2)	f   =  x7  +  x6  -  1,					g  =  x  -  1.

9.2   	A square of given side length s is inscribed into a right triangle such that one of its corners 	coincides with the right apex and two of its sides are aligned with the legs of the triangle. 		The length of the hypotenuse, c, is given. 
  	a)   Determine the lengths of the legs.
  	b)  Specialize to s = 4, c = 20. Draw the solutions, together with the square filled. .

9.3   	Compute f(a,b,c) = a^4 + b^4 + c^4,  where 
	a + b + c =  3,   a^2 + b^2 + c^2 = 9,  a^3 + b^3 + c^3  =  24.  
	The result  f(a,b,c)   is an integer.

9.4	For which real value(s) of  the parameter  a  occur multiple roots of the following equation :
		(a^4)+3 (a^2) x+a (x^4)+(x^5)  =  0  
	These value(s) should be given with an accuracy of 30 decimal places.