QUADRATIC FORMS AND DEFINITE MATRICES

1 QUADRATIC FORMS AND DEFINITE MATRICES1. DEFINITION AND CLASSIFICATION OF QUADRATIC of a QUADRATIC A denote an n x n symmetric matrix with real entries andlet x denote an n x 1 column vector. Then Q = x Ax is said to be aquadratic form . Note thatQ=x Ax=( ) a11 ann (x1xn)=(x1,x2, ,xn) anixi =a11x21+a12x1x2+..+a1nx1xn+a21x2x1+a22x2 2+..+a2nx2xn+..+..+..+an1xnx1+an2xnx2+.. +annx2n= i jaijxixj(1)For example, consider the matrixA=[1221]and the vector x. Q is given byQ=x Ax=[x1x2][1221][x1x2]=[x1+2x22x1+x2][x1x 2]=x21+2x1x2+2x1x2+x22=x21+4x1x2+ of the QUADRATIC form Q =x Ax:A QUADRATIC form is said to be:a:negative DEFINITE :Q<0whenx6=0b:negative semidefinite:Q 0for all x andQ=0for somex6=0c:positive DEFINITE :Q>0whenx6=0d:positive semidefinite:Q 0for all x and Q = 0 for somex6=0e:indefinite:Q>0for some x andQ<0for some otherxDate.

2 September 14, FORMS AND DEFINITE MATRICESC onsider as an example the 3x3 diagonal matrix D below and a general 3 element vector 100020004 The general QUADRATIC form is given byQ=x Ax=[x1x2x3] 100020004 x1x2x3 =[x12x24x3] x1x2x3 =x21+2x22+4x23 Note that for any real vector x6=0, that Q will be positive, because the square of any numberis positive, the coefficients of the squared terms are positive and the sum of positive numbers isalways positive. Also consider the following 21 01 2000 2 The general QUADRATIC form is given byQ=x Ax=[x1x2x3] 21 01 2000 2 x1x2x3 =[ 2x1+x2x1 2x2 2x3] x1x2x3 = 2x21+x1x2+x1x2 2x22 2x23= 2x21+2x1x2 2x22 2x23= 2[x21 x1x2] 2x22 2x23= 2x21 2[x22 x1x2] 2x23 Note that independent of the value of x3, this will be negative if x1and x2are of opposite signor equal to one another.

3 Now consider the case where|x1|>|x2|. Write Q asQ= 2x21+2x1x2 2x22 2x23 The first, third, and fourth terms are clearly negative. But with|x1|>|x2|,|2x21|>|2x1x2|so that the first term is more negative than the second term is positive, and so the whole expressionis negative. Now consider the case where|x1|<|x2|. Write Q asQ= 2x21+2x1x2 2x22 2x23 The first, third, and fourth terms are clearly negative. But with|x1|<|x2|,|2x22|>|2x1x2|so that the third term is more negative than the second term is positive, and so the whole expressionis negative.

4 Thus this QUADRATIC form is negative DEFINITE for any and all real values of x6= FORMS AND DEFINITE x has only two elements, we can graphically represent Q in 3 di-mensions. A positive DEFINITE QUADRATIC form will always be positive except at the point where x= 0. This gives a nice graphical representation where the plane at x = 0 bounds the function frombelow. Figure 1 shows a positive DEFINITE QUADRATIC Positive DEFINITE QUADRATIC Form3x21+3x22-10-50510x1-10-50510x202004 00600Q-10-505x110-505x2 Similarly, a negative DEFINITE QUADRATIC form is bounded above by the plane x = 0.

5 Figure 2 showsa negative DEFINITE QUADRATIC FORMS AND DEFINITE MATRICESFIGURE2. Negative DEFINITE QUADRATIC form 2x21 2x22-10-50510x1-10-50510x2-400-300-200-1 000Q-10-505x110-505x2A positive semi- DEFINITE QUADRATIC form is bounded below by the plane x = 0 but will touch theplane at more than the single point (0,0), it will touch the plane along a line. Figure 3 shows apositive semi- DEFINITE QUADRATIC negative semi- DEFINITE QUADRATIC form is bounded above by the plane x = 0 but will touch theplane at more than the single point (0,0). It will touch the plane along a line.

6 Figure 4 shows anegative- DEFINITE QUADRATIC indefinite QUADRATIC form will not lie completely above or below the plane but will lie abovefor some values of x and below for other values of x. Figure 5 shows an indefinite QUADRATIC on matrix associated with a QUADRATIC form B need not be , no loss of generality is obtained by assuming B is symmetric. We can always take definiteand semidefinite MATRICES to be symmetric since they are defined by a QUADRATIC form . Specificallyconsider a nonsymmetric matrix B and define A as12(B+B ), A is now symmetric andx Ax=x DEFINITE AND SEMIDEFINITE of DEFINITE and semi- DEFINITE A be a square matrix of order n andlet x be an n element vector.

7 Then A is said to be positive semidefinite iff for all vectors xQUADRATIC FORMS AND DEFINITE MATRICES5 FIGURE3. Positive Semi- DEFINITE QUADRATIC Form2x21+4x1x2+ Negative Semi- DEFINITE QUADRATIC form 2x21+4x1x2 Ax 0(2)The matrix A is said to be positive DEFINITE if for non zero xx Ax >0(3)6 QUADRATIC FORMS AND DEFINITE MATRICESFIGURE5. Indefinite QUADRATIC form 2x21+4x1x2+ A be a square matrix of order n. Then A is said to be negative (semi) DEFINITE iff -A is positive(semi) elements of positive DEFINITE A be a positive DEFINITE matrix of order m.

8 Thenaii>0,i=1,2, .., A is only positive semidefinite thenaii 0,i=1,2, .., e ibe them-element vector all of whose elements are zeros save theith, which is example if m = 5 and i = 2 [0,1,0,0,0]IfAis positive DEFINITE , because e iis notthe null vector, we must havee iAe i>0,i=1,2, .., m.(4)Bute iAe i=aii,i=1,2, .., m.(5)IfAis positive semidefinite butnotpositive DEFINITE then repeating the argument above we findaii=e iAe i 0,i=1,2, .., m.(6) QUADRATIC FORMS AND DEFINITE positive DEFINITE MATRICES (Cholesky factorization).Theorem A be a positive DEFINITE matrix of order n.

9 Then there exists a lower triangular matrix Tsuch thatA=TT (7) T as followsT= t1100 0t21t220 0t31t32t33 tnn (8)Now defineTT TT = t1100 0t21t220 0t31t32t33 tnn t11t21t31 tn10t22t32 tn200t33 tnn = t211t11t21t11t31 t11tn1t21t11t221+t222t21t31+t22t32 t21tn1+t22tn2t31t11t31t21+t32t22t231+t23 2+t233 t31tn1+t32tn2+ +tn2t22tn1t31+tn2t32+tn3t33 ni=1t2ni (9)Now defineA=TT and compare like elementsA=TT a11a12a13 a1na21a22a23 a2na31a32a33 ann = t211t11t21t11t31 t11tn1t21t11t221+t222t21t31+t22t32 t21tn1+t22tn2t31t11t31t21+t32t22t231+t23 2+t233 t31tn1+t32tn2+ +tn2t22tn1t31+tn2t32+tn3t33 ni=1t2ni (10)Solve the system now for each tijas functions of the aij.

10 The system is obviously recursivebecause we can solve first fort11, thent21, etc. A schematic algorithm is given FORMS AND DEFINITE MATRICESt11= a11,t21=a12t11,t31=a13t11, ,tn1=a1nt11t22= a22 a122a11,t32=a23 t21t31t22, ,tn2=a2n t21tn1t22t33= a33 t231 t232= a33 a213a11 (a23 t21t31t22)2t43=a34 t31t41 t32t42t33, ,tn3=a3n t31tn1 t32tn2t33(11)This matrix is not unique because the square roots involve two roots. The standard procedure isto make the diagonal elements positive. Consider the following matrix as an exampleF= 420290002 .We can factor it into the following matrix TT= 20 012 2000 2 and its transposeT.