1 Quadratic Forms - rmi.ge

1 Reading[SB], Ch. , p. 375-3931 Quadratic FormsAquadratic functionf:R Rhas the formf(x) =a x2. Generalizationof this notion to two variables is thequadratic formQ(x1, x2) =a11x21+a12x1x2+a21x2x1+ each term has degree 2 (the sum of exponents is 2 for all summands).A Quadratic form of three variables looks asf(x1, x2, x3) =a11x21+a12x1x2+a13x1x3+a21x2x1+a22x22+a 23x2x3+a31x1x3+a32x3x2+ general Quadratic form ofnvariables is a real-valued functionQ:Rn Rof the formQ(x1, x2, .., xn) =a11x21+a12x1x2+..+a1nx1xn+a21x2x1+a22x2 2+..+a2nx2xn+..an1xnx1+an2xnx2+..+annx2n In shortQ(x1, x2, .., xn) = ni, we see a Quadratic form is determined by the matrixA= ann . Matrix Representation of Quadratic FormsLetQ(x1, x2, .., xn) = ni,jaijxixjbe a Quadratic form with matrixA. Easyto see thatQ(x1, .., xn) = (x1, .., xn) ann .1 EquivalentlyQ(x) =xT A Quadratic formQ(x1, x2, x3) = 5x21 10x1x2+x22whosesymmetric matrix isA=(5 5 5 1)is the product of three matrices(x1, x2, x3) (5 5 5 1) x1x2x3.

2 Symmetrization of matrixThe Quadratic formQ(x1, x2, x3) = 5x21 10x1x2+x22can be represented, forexample, by the following 2 2 matrices(5 2 8 1),(5 3 7 1),(5 5 5 1)the last one issymmetric:aij= 1 Any Quadratic form can be represented by symmetric , ifaij6=ajiwe replace them by newa ij=a ji=aij+aji2, this doesnot change the corresponding Quadratic , one can find symmetrizationA of a matrixAbyA =A+ Definiteness of Quadratic FormsA Quadratic form of one variable is just a Quadratic functionQ(x) =a >0 thenQ(x)>0 for each <0 thenQ(x)<0 for each the sign of the coefficientadetermines the sign ofone notion ofdefinitenessdescribed bellow generalizes this phenomenonfor multivariable Quadratic Generic ExamplesThe Quadratic formQ(x, y) =x2+y2ispositiveforallnonzero (that is(x, y)6= (0,0)) arguments (x, y). Such Forms are calledpositive Quadratic formQ(x, y) = x2 y2isnegativeforallnonzero argu-ments (x, y).

3 Such Forms are callednegative Quadratic formQ(x, y) = (x y)2isnonnegative. This means thatQ(x, y) = (x y)2is either positive or zero for nonzero arguments. Suchforms are calledpositive Quadratic formQ(x, y) = (x y)2isnonpositive. This means thatQ(x, y) = (x y)2is either negative or zero for nonzero arguments. Suchforms are callednegative Quadratic formQ(x, y) =x2 y2is calledindefinitesince it cantake both positive and negative values, for exampleQ(3,1) = 9 1 = 8>0, Q(1,3) = 1 9 = 8< Quadratic formQ(x) =xT A x(equivalentlya symmetricmatrixA) is(a)positive definiteifQ(x)>0 for allx6= 0 Rn;(b)positive semidefiniteifQ(x) 0 for allx6= 0 Rn;(c)negative definiteifQ(x)<0 for allx6= 0 Rn;(d)negative semidefiniteifQ(x) 0 for allx6= 0 Rn;(e)indefiniteifQ(x)>0 for somexandQ(x)<0 for some Definiteness and OptimalityDetermining the definiteness of Quadratic formQis equivalent to determiningwetherx= 0 is max, min or neither.

4 Particularly:IfQis positive definite thenx= 0 is global maximum;IfQis negative definite thenx= 0 is global Definiteness of 2 Variable Quadratic FormLetQ(x1, x2) =ax21+ 2bx1x2+cx22= (x1, x2) (a bb c) (x1x2)be a 2variable Quadratic (a bb c)is the symmetric matrix of the Quadratic form . Thedeterminant a bb c =ac b2is to see thatax21+ 2bx1x2+cx22=a(x1+bax2)2+ac us use the notationD1=a, D2=ac b2. ActuallyD1andD2areleading principal minorsofA. Note that there exists one more principal(non leading) minor (of degree 1)D 1= (x1, x2) =D1(x1+bax2)2+ this expression we obtain:31. IfD1>0 andD2>0 then the form is ofx2+y2type, so it ispositivedefinite;2. IfD1<0 andD2>0 then the form is of x2 y2type, so it isnegativedefinite;3. IfD1>0 andD2<0 then the form is ofx2 y2type, so it isindefinite;IfD1<0 andD2<0 then the form is of x2+y2type, so it is alsoindefinite.

5 Thus ifD2<0 then the form is depends not only on leading principal minorsD1, D2but also onallprincipal minors, in this case onD 1= IfD1 0, D 1 0 andD2 0 then the form ispositive that onlyD1 0 andD2 0 is not enough, the additional conditionD 1 0 here is absolutely necessary: consider the formQ(x1, x2) = x22witha= 0, b= 0, c= 1, hereD1=a 0, D2=ac b2 0, nevertheless theform is not positive IfD1 0, D 1 0 andD2 0 then the form isnegative that onlyD1 0 andD2 0 is not enough,the additional conditionD 1 0 again is absolutely necessary: consider the formQ(x1, x2) =x22witha= 0, b= 0, c= 1, hereD1=a 0, D2=ac b2 0, nevertheless theform is not negative Definiteness of 3 Variable Quadratic FormLet us start with the (x1, x2, x3) =x21+ 2x22 7x23 4x1x2+ 8x1x3. The symmetricmatrix of this Quadratic form is 1 2 4 2 2 04 0 7 .The leading principal minors of this matrix are|D1|= 1 = 1,|D2|= 1 2 2 2 = 2,|D3|= 1 2 4 2 2 04 0 7 = look:Q(x1, x2, x3) =x21+ 2x22 7x23 4x1x2+ 8x1x3=x21 4x1x2+ 8x1x3+ 2x22 7x23=x21 4x1(x2 2x3) + 2x22 7x23=[x21 4x1(x2 2x3) + 4(x2 2x3) 4(x2 2x3)] + 2x22 7x23=[x1 2x2+ 4x3]2 2x22 16x2x3 23x23=[x1 2x2+ 4x3]2 2(x22 8x2x3) 23x23=[x1 2x2+ 4x3]2 2[x22 8x2x3+ 16x23 16x23] 23x23=[x1 2x2+ 4x3]2 2[x2 4x3]2 16x23) 23x23=[x1 2x2+ 4x3]2 2[x2 4x3]2+ 32x23 23x23=[x1 2x2+ 4x3]2 2[x2 4x3]2+ 9x23=|D1|l21+D2D1l2+D3D2l23,wherel1=x1 2x2+4x3,l2=x2 4x3,l3= is (l1, l2, l3) are linear combinations of (x1, x2, x3).

6 More precisely l1l2l3 = 1 2 40 1 40 0 1 x1x2x3 whereP= 1 2 40 1 40 0 1 is a nonsingular matrix (changing variables).Now turn to general 3 variable Quadratic formQ(x1, x2, x3) = (x1, x2, x3) a11a12a13a21a22a23a31a32a33 x1x2x3 .The following three determinants|D1|= a11 ,|D2|= a11a12a21a22 ,|D3|= a11a12a13a21a22a23a31a32a33 areleading principal is possible to show that, as in 2 variable case, if|D1| 6= 0,|D2| 6= 0,thenQ(x1, x2, x3) =|D1|l21+|D2||D1|l22+|D3||D2|l235wherel1 , l2, l3are some linear combinations ofx1, x2, x3(this is calledLa-grange s reduction).This implies the following criteria:1. The form is positive definite iff|D1|>0,|D2|>0,|D3|>0, that is allprincipal minors are The form is negative definite iff|D1|<0,|D2|>0,|D3|<0, that isprincipal minors alternate in sign starting with negative the definiteness of the formQ(x1, x2, x3) = 3x21+2x22+3x23 2x1x2 matrix of our form is 3 1 0 1 2 10 1 3.

7 The leading principal minors are|D1|= 3>0,|D2|= 3 1 1 2 >5,|D3|= 3 1 0 1 2 10 1 3 = 18>0,thus the form is positive Definiteness ofnVariable Quadratic FormLetQ(x1, .., xn) = (x1, .., xn) .. ann be annvariablequadratic followingndeterminants|D1|= a11 ,|D2|= a11a12a21a22 , .. ,|Dn|= .. ann areleading principal in previous cases, it is possible to show thatQ(x1, .. , x3) =|D1|l21+|D2||D1|l22+..+|Dn||Dn 1|l2nwhere (l1, l2, .. , ln) are linear combinations of (x1, x2, .. , xn), more precisely = p1n.. pnn 6whereP= p1n.. pnn is a nonsingular matrix (changing variables).Theorem 21. A Quadratic form is positive definite if and only if|D1|>0,|D2|>0, .. ,|Dn|>0,that is all principal minors are positive;2. A Quadratic form is negative definite if and only if|D1|<0,|D2|>0,|D3|<0,|D4|>0.

8 ,that is principal minors alternate in sign starting with negative If somekth order leading principal minor is nonzero but does not fiteither of the above two sign patterns, then the form is situation with semidefiniteness is more complicated, here are involvednot only leading principal minors, butallprincipal 31. A Quadratic form is positive semidefinite if and only if allprincipal minors are 0;2. A Quadratic form is negative semidefinite if and only if all principalminors of odd degree are 0, and all principal minors of even degree are Definiteness and EigenvaluesAs we know a symmetricn nmatrix hasnreal eigenvalues (maybe somemultiple).Theorem 4 Given a Quadratic formQ(x) =xTAxand let 1, .. , nbeeigenvalues ofA. ThenQ(x)is positive definite iff i>0, i= 1, .. , n; negative definite iff i<0, i= 1, .. , n; positive semidefinite iff i 0, i= 1, .. , n; negative semidefinite iff i 0, i= 1.

9 , n; >0 i>0. Letvbe the normalized eigenvector of i, that isAv= iv. Then0< vTAv= ivTv= Linear Constraints and Bordered Two Variable CaseThe Quadratic formQ(x1, x2) =x21 x22is indefinite (why?).But if we restrictQto the subset (subspace) ofR2determined by theconstraintx2= 0 we obtain a one variable Quadratic formq(x) =Q(x,0) =x2which is definitely positive definite. Thus the restriction ofQonx1axisis positive , the constraintx1= 0 givesq(x) =Q(0, x) = x2which isnegative definite. Thus the restriction ofQonx2axis is positive let us consider the constraintx1 2x2= 0. Solvingx1from thisconstraint we obtainx1= 2x2. Substituting inQwe obtain one variablequadratic formq(x) =Q(2x, x) = 4x2 x2= 3x2which is positive the restriction ofQon the linex1+ 2x2= 0 is positive us repeat the last calculations for a general 2 variable Quadratic formQ(x1, x2) =ax21+ 2bx1x2+cx22= (x1, x2)(a bb c)(x1x2)subject to the linear constraintAx1+Bx2= us, as above, solvex1from the constraintx1= BAx2and substitute inQ:Q(x1, x2) =Q( BAx2, x2) =a11( BAx2)2+ 2a12( BAx2)x2+a22x22==aB2 2bAB+ the definiteness ofQ(x1, x2) on the constraint setAx1+Bx2= 0 dependson the sign of coefficientaB2 2bAB+cA2A2, more precisely on the nominatoraB2 2bAB+cA2,which is nothing else than It is easy to see that det 0A BA a bB b c.

10 8 This matrix 0A BA a bB b c is calledborderedmatrix we have proved theTheorem 5A two variable Quadratic formQ(x1, x2) =a11x21+ 2a12x1x2+a22x22restricted on the constrained setAx1+Bx2= 0is positive (resp. neg-ative) if and only if the determinant of the bordering matrixdet 0A BA a bB b c is negative (resp. positive). m Constraint CaseAnalogous result holds in general , A= ann andQ(x1, .. , xn) =xTAxbe annvariable Quadratic form . Consider a constraint set Bmn = .In fact this set is the null space ofB, is not it?The bordered matrix for this situation looks asH= | |.. | Bmn Bm1| |.. Bmn| ann =(0 BBTA).This (m+n) (m+n) matrix hasm+nleading principal minorsM1, M2, .. , Mm, Mm+1, .. , M2m 1, M2m, M2m+1, .. , Mm+n= firstmmatricesM1, .. , Mmare zero 1 matricesMm+1, .. , M2m 1have zero determinant of the next minorM2mis det B 2whereB is the leftm mminor ofB, it does not carry any information only the determinants of lastn mmatricesM2m+1.