8.2 Quadratic Forms Example 1 - NCU

1 (x1; x2) = 8x21 4x1x2+ 5x22 Determinewhetherq(0;0) is matrixtechniqueRewriteq("x1x2#) = 8x21 4x1x2+ 5x22="x1x2# "8x1 2x2 2x1+ 5x2#Notethatwe splitthecontribution 4x1x2equallyamongthetwo succinctly, we canwriteq(~x) =~x A~x;where A="8 2 25#1orq(~x) =~xTA~xThematrixAis symmetricby ,thereis an orthonormaleigenbasis~v1; ~v2forA. We nd~v1=1p5"2 1#; ~v2=1p5"12#withassociatedeigenvalues 1= 9 and 2= ~x=c1~v1+c2~v2, we canexpressthevalueof thefunctionas follows:q(~x) =~x A~x= (c1~v1+c2~v2) (c1 1~v1+c2 2~v2)= 1c21+ 2c22= 9c21+ 4c22 Therefore,q(~x)>0 for all nonzero~ (0;0) =0 is theglobalminimumof functionq(x1; x2; : : : ; xn) fromRntoRiscalleda quadraticformif it is a linear combina-tionof functionsof theformxixj. A quadraticformcanbe writtenasq(~x) =~x A~x=~xTA~xfor a symmetricn (x1; x2; x3) = 9x21+7x22+3x23 2x1x2+4x1x3 6x2x3 Finda symmetricmatrixAsuchthatq(~x) =~x A~xfor all~ Example1, we letaii= (coe cientofx2i),aij=12(coe cientofxixj), ifi6= ,A=2649 12 17 32 333752 Changeof Variablesin a quadraticformq(~x) =~x A~xfromRntoR.

2 LetBbe an orthonormaleigenbasisforA, withassociatedeigenvalues 1; : : : ; n. Thenq(~x) = 1c21+ 2c22+: : :+ nc2n;wheretheciare thecoordinatesof~ y, or equivalently,y=P 1x= , if changeof variableis madein a quadraticformxTAx, thenxTAx= (P y)TA(P y) =yTPTAPy=yT(PTAP)ySincePorghogonallydiag onalizesA, thePTAP=P 1AP= nitequadraticformIfq(~x)>0 for all nonzero~xinRn, we sayAispositivede (~x) 0 for all nonzero~xinRn, we sayAispositivesemide (~x) takes positiveas well as negativevalues,we sayAis inde nmatrixA. Showthatthefunctionq(~x) =jjA~xjj2is a quadraticform, ndits matrixanddetermineits de (~x) = (A~x) (A~x) = (A~x)T(A~x) =~xTATA~x=~x (ATA~x).Thisshowsthatqis a quadraticform, (~x) =jjA~xjj2 0 for all vectors~xinRn,thisquadraticformis positivesemide (~x) = 0 i ~xis in thekernelofA.

3 Therefore,thequadraticformis positivede nitei ker(A) =f~ nitenessA symmetricmatrixAis positivede nitei allits eigenvaluesare positivesemide nitei all of itseigenvaluesare positiveor :ThePrincipalAxesTheoremLetAbe ann an orthogonalchangeof variable,x=P y, thattransformsthequadraticformxTAxintoa quadraticformyTDywithno studya functionf(x1; x2; : : : ; xn) fromRntoR, we are ofteninterestedin thesolutionof theequationf(x1; x2; : : : ; xn) =k;for a xedkinR, 4x1x2+ 5x22= 1 SolutionIn Example1, we foundthatwe canwritethisequationas9c21+ 4c22= 16wherec1andc2are thecoordinatesof~xwithrespectto theorthonormaleigenbasis~v1=1p5"2 1#; ~v2=1p5"12#forA="8 2 25#. We calledtheprincipleaxesof thequadraticformq(x1; x2) = 8x21 4x1x2+5x22.

4 Notethattheseare theeigenspacesof thematrixA="8 2 25#of quadraticformQhasno cross-productterms,it is easyto ndthemaximumandmin-imumofQ(~x) for~xT~xx= (~x) = 9x21+ 4x22+ 3x23subjecttotheconstraint~xT~xx= (~x) = 9x21+ 4x22+ 3x23 9x21+ 9x22+ 9x23= 9(x21+x22+x23) = 9wheneverx21+x22+x23= (~x) = 9 when~x= (1;0;0).Similarly,Q(~x) = 9x21+ 4x22+ 3x23 3x21+ 3x22+ 3x23= 3(x21+x22+x23) = 3wheneverx21+x22+x23= (~x) = 3 when~x= (0;0;1).7 THEOREMLetAbe a symmetricmatrix,andde nem=minfxTAx:k~xg= 1g; M=maxfxTAx:k~xg= 1g:ThenMis thegreatesteigenvalues 1ofAandmis theleasteigenvalueofA. ThevalueofxTAxisMwhenxis a uniteigenvectoru1correspondingto eigenvalueM. ThevalueofxTAxismwhenxis a uniteigenvector , (by changeof variablex=P y), we cantrans-formthequadraticformxTAx= (P y)TA(P y)intoyTDy.

5 Theconstraintkxk= 1 implieskyk= 1 sincekxk2=kP yk2= (P y)TP y=yTPTP y=yT(PTP)y=yTy= thatP=hu1 uniand 1 , observethatyTDy= 1c21+ + nc2n 1c21+ + 1c2n= 1kyk= 1 ThusxTAxhasthelargestvalueM= 1wheny= , y= similar argumentshow thatmis theleasteigenvalue nwheny= , y= ; 1andu1be as in theconstraintsxTx= 1; xTu1= 0is thesecondgreatesteigenvalue, 2, andthismaximumis attainedwhenxis an eigenvectoru2correspondingto a symmetricn nma-trixwithanorthogonaldiagonalizationA =P DP 1, wheretheentrieson thediagonalofDare arrangedso that 1 n, andwherethecolumnsofPare correspondinguniteigen-vectorsu1; :::;un. Thenfork= 2; :::;n, themaximumvalueofxTAxsubjectto thecon-straintsxTx= 1; xTu1= 0; :::;xTuk 1= 0is theeigenvalue k, andthismaximumis at-tainedwhenx= ValueDecompositionTheabsolutevaluesof theeigenvaluesof asymmetricmatrixAmeasuretheamountsthatAs tretchesor xandxTx= 1, thenkAxk=k xk=j jkxk=j jbasedonthediagonalizationofA=P DP analoguefor rectangu-lar matricesthatwillleadto thesingular valuedecompositionA=QDP "4 111487 2#, thenthelin-ear transformationT(x) =Axmapstheunitspherefx:kxk= 1ginR3intoan ellipseinR2( ).

6 Finda unitvector at whichkAxkis (Ax)TAx=xTATAx=xT(ATA)xAlsoATAis a symmetricmatrixsince(ATA)T=ATAT T=ATA. So theproblemnow is to max-imizethequadraticformxT(ATA)xsubject totheconstraintkxk= 235 4 111487 2 =2480100401001701404014020035 FindtheeigenvaluesofATA: 1= 360; 2= 90; 3= 0,andthecorrespondinguniteigenvectors,v1 =241=32=32=335; v2=24 2=3 1=32=335; v3=242=3 2=31=335 ThemaximumvalueofkAxk2is 360,attainedwhenxis Valuesof anm nMatrixLetAbe anm sym-metricandcanbe ; :::;vngbe an orthonormalbasisforRnconsistingof eigenvectors ofATA, andlet 1; :::; nbe theassociatedeigenvaluesofATA. Thenfor 1 i n,kAvik2= (Avi)TAvi=vTiATAvi=vTi( ivi) = iSotheeigenvaluesofATAare all 1 2 n 0 Thesingular valuesofAare thesquare rootsoftheeigenvaluesofATA, denotedby 1; :::; i=p ifor 1 i n.

7 Thesingu-lar valuesofAare thelengthsof thevectorsAv1; :::; thematrixin 360,90,and0, thesingularvaluesofAare 1=p360= 6p10; 2=p90 = 3p10; 3= 0 Notethat,the rstsingular valueofAis themaximumofkAxkoverall unitvectors,andthemaximumis at-tainedat theuniteigenvectorv1. ThesecondsingularvalueofAis themaximumofkAxkoverall unitvectorsthatare orthogonaltov1, andthismaximumis attainedat theseconduniteigenvector,v2. ComputeAv1= 4 111487 2 241=32=32=335= 186 Av2= 4 111487 2 24 2=3 1=32=335= 3 9 ThefactthatAv1andAv2are orthogonalis no accident,as ; :::;vngis an or-thonormalbasisofRnconsistingof eigenvec-tors ofATA, arrangedso thatthecorrespond-ingeigenvaluesofATAsat isfy 1 2 n,andsupposethatAhasrnonzerosingular ; :::;Avrgis an orthogonalbasisfor im(A), andrank(A)= orthogonalfori6=j,(Avi)T(Avj) =vTiATAvj=vTi jvj= 0 ThusfAv1; :::;Avngis an ,Avi= 0 fori >r.

8 For anyyinim(A), (c1v1+ +cnvn)=c1Av1+ +crAvr+ 0 + + 0 Thusyis in SpanfAv1; :::;Avrg, whichshowsthatfAv1; :::;Avrgis an(orthogonal)basisforim(A). Hencerank(A)=dimim(A)=