Ten problems on quadratic forms and positive definite matrices: writing a form as xᵀAx with a symmetric matrix, classifying definite, semidefinite and indefinite matrices by their eigenvalues, the leading principal minors of a 3×3 matrix, completing the square as LDLᵀ, a Cholesky factor by hand, the range of a parameter that keeps a matrix positive definite, the largest and smallest values on the unit circle, the axes of an ellipse, why AᵀA is positive semidefinite and when it is definite, and the Hessian of a ridge regression loss, with worked solutions and the mistakes of the unhalved cross term, a positive diagonal taken as proof, leading minors for a semidefinite test, the long axis along the largest eigenvalue and the extremes read off the diagonal.
Before you start
A quadratic form is a sum of squares and cross products, such as ,3x2+4xy+2y2, and every one of them can be written as x⊤Ax with a symmetric matrix .A. The question that matters is its sign: a form that is positive for every nonzero x is positive definite, and that single property is what makes a critical point a minimum, a loss convex with a unique minimizer, a covariance matrix valid and a Cholesky factor exist. These ten problems build the matrix of a form, test definiteness three ways (eigenvalues, leading principal minors and completing the square), factor a matrix by Cholesky, find the extremes of a form on the unit circle and the axes of an ellipse, and end with why ridge regression always has exactly one solution.
A quadratic form is q(x)=x⊤Ax=∑i,jAijxixj with A symmetric. The coefficient of xi2 is ,Aii, and the coefficient of xixj for i=j is ,2Aij, so the off-diagonal entries are half the cross coefficients.
A is positive definite (PD) if x⊤Ax>0 for every ,x=0,positive semidefinite (PSD) if x⊤Ax≥0 for every ,x, negative (semi)definite if −A is, and indefinite if x⊤Ax takes both signs.
Eigenvalue test. A symmetric A is QΛQ⊤ with Q orthogonal, so with ,y=Q⊤x,.x⊤Ax=∑iλiyi2.A is PD exactly when every ,λi>0, PSD when every ,λi≥0, and indefinite when there are eigenvalues of both signs.
Sylvester's criterion.A is PD exactly when its leading principal minors (the determinants of the top-left ,1×1,,2×2, …, n×n blocks) are all positive. For semidefiniteness the leading minors are not enough: every principal minor must be .≥0.
Cholesky.A is PD exactly when A=LL⊤ with L lower-triangular and its diagonal positive. Equivalently A=LDL⊤ with L unit lower-triangular and the pivots of elimination on the diagonal of ,D, all positive.
Rayleigh quotient. For symmetric ,A, the largest and smallest values of x⊤Ax over unit vectors x are λmax and ,λmin, reached at their eigenvectors. For PD ,A, the set x⊤Ax=c is an ellipse (ellipsoid) with axes along the eigenvectors and semi-axis lengths .c/λi.
Write q(x,y)=3x2+4xy+2y2 as x⊤Ax with A symmetric, and check it at .(1,−1). Then write the matrix of .x2+2y2+3z2+2xy−4yz.
·
Classify each matrix as positive definite, positive semidefinite or indefinite from its eigenvalues: ,A=(2112),,B=(1221),.C=(1224).
··
Use the leading principal minors to show that A=2−10−12−10−12 is positive definite, and confirm with its eigenvalues.
··
Complete the square in ,q(x,y)=3x2+4xy+2y2, and write the result as .A=LDL⊤.
··
Find the Cholesky factor L of ,A=42−22102−226, and use it to get .detA.
··
For which real k is A=21012k0k2 positive definite?
··
Find the largest and smallest values of q(x,y)=5x2+4xy+2y2 on the unit circle ,x2+y2=1, and where they occur.
··
Find the axes, the semi-axis lengths and the area of the ellipse .5x2−4xy+5y2=21.
···
Show that M⊤M is positive semidefinite for any matrix ,M, and positive definite exactly when the columns of M are independent. Test M1=111123 and .M2=111222.
···
Ridge regression minimizes .L(w)=∥Xw−y∥2+λ∥w∥2. Find the gradient and Hessian of .L. With X=M2 from Problem 9, y=(1,2,3) and ,λ=21, show that the Hessian is positive definite and find the unique minimizer.
Answers
;A=(3222);11012−20−23
A is positive definite, B is indefinite, C is positive semidefinite (not definite)
;Δ1,Δ2,Δ3=2,3,4; the eigenvalues are ,2−2≈0.586,2 and ,2+2≈3.414, all positive
,q=3(x+32y)2+32y2,A=LDL⊤ with ,L=(13201),:D=diag(3,32): positive definite
,L=21−1031002,detA=(2⋅3⋅2)2=144
−3<k<3
Maximum 6 at ;±51(2,1); minimum 1 at ±51(1,−2)
Major semi-axis 7 along ,(1,1), minor semi-axis 3 along ;(1,−1); area π73=π21≈14.40
M⊤M is always PSD; M1⊤M1 is PD, M2⊤M2 is only PSD, with v⊤M2⊤M2v=0 at v=(2,−1)
,∇2L=2(X⊤X+λI), PD with eigenvalues 1 and ;31;w∗=(3112,3124)
Worked solutions
Problem 1
Write q(x,y)=3x2+4xy+2y2 as x⊤Ax with A symmetric, and check it at .(1,−1). Then write the matrix of .x2+2y2+3z2+2xy−4yz.
A11=3 and A22=2The squares go on the diagonal.
,2A12=4, so A12=A21=2The cross term 4xy is ,A12xy+A21yx, split evenly between the two off-diagonal entries.
A=(3222)Symmetric, as a form's matrix should be.
At :(1,−1):,q=3−4+2=1, and x⊤Ax=(1,−1)(10)=1.Ax=(3−2,2−2)=(1,0). Using 4 off the diagonal instead gives −3 (Mistake 1).
;A=(3222);11012−20−23In the second form, 2xy gives ,A12=1,−4yz gives ,A23=−2, and there is no xz term, so .A13=0.
Problem 2
Classify each matrix as positive definite, positive semidefinite or indefinite from its eigenvalues: ,A=(2112),,B=(1221),.C=(1224).
:A:,λ2−4λ+3=0, so λ=1,3Trace ,4, determinant .3.
:B:,λ2−2λ−3=0, so λ=3,−1Trace ,2, determinant .−3. A negative determinant of a 2×2 always means one eigenvalue of each sign.
:C:,λ2−5λ=0, so λ=0,5Determinant :0: the rows are proportional.
qB(1,−1)=1−4+1=−2 and qC(2,−1)=4−8+4=0A witness for each: (1,−1) is B's eigenvector for ,−1, and (2,−1) spans C's null space.
A is positive definite, B is indefinite, C is positive semidefinite (not definite)B has positive diagonal entries and is still not PD (Mistake 2).
Problem 3
Use the leading principal minors to show that A=2−10−12−10−12 is positive definite, and confirm with its eigenvalues.
Δ1=2The top-left entry.
Δ2=2⋅2−(−1)(−1)=3The top-left 2×2 block.
Δ3=2(4−1)−(−1)(−2−0)+0=6−2=4Expand along the first row.
All three are positive, so A is PD by Sylvester's criterionThis is the second-difference matrix behind a discretized .−u′′.
;Δ1,Δ2,Δ3=2,3,4; the eigenvalues are ,2−2≈0.586,2 and ,2+2≈3.414, all positiveTheir product is 4=detA and their sum is .6=trA.
Problem 4
Complete the square in ,q(x,y)=3x2+4xy+2y2, and write the result as .A=LDL⊤.
3x2+4xy=3(x2+34xy)=3(x+32y)2−34y2Factor out the x2 coefficient, then half of 34 is ,32, and .3⋅94=34.
q=3(x+32y)2+32y2.2−34=32.
Both coefficients are positive, so q>0 unless y=0 and ,x+32y=0, that is unless x=y=0A sum of positive multiples of squares of independent combinations.
,L=(13201),D=diag(3,32)The rows of L⊤ are the combinations being squared; the entries of D are the pivots of elimination on .A.
,q=3(x+32y)2+32y2,A=LDL⊤ with ,L=(13201),:D=diag(3,32): positive definiteCheck: .detA=3⋅32=2=6−4.
Problem 5
Find the Cholesky factor L of ,A=42−22102−226, and use it to get .detA.
,l11=4=2,,l21=22=1,l31=2−2=−1The first column of A is l11 times the first column of .L.
l22=10−l212=9=3Subtract what the first column already supplies, then take the root.
Find the largest and smallest values of q(x,y)=5x2+4xy+2y2 on the unit circle ,x2+y2=1, and where they occur.
A=(5222)Half of 4 off the diagonal.
,λ2−7λ+6=0, so λ=6,1Trace ,7, determinant .10−4=6.
:λ=6:(A−6I)v=0 with rows ,(−1,2), so v=51(2,1)Check: .q=51(20+8+2)=6.
:λ=1: rows ,(4,2), so v=51(1,−2)Check: .q=51(5−8+8)=1.
Maximum 6 at ;±51(2,1); minimum 1 at ±51(1,−2)Every other unit vector gives a value in between, for example .q(1,0)=5. The smallest diagonal entry, ,2, is not the minimum (Mistake 5).
Problem 8
Find the axes, the semi-axis lengths and the area of the ellipse .5x2−4xy+5y2=21.
A=(5−2−25) has λ=3 for (1,1)/2 and λ=7 for (1,−1)/2A(1,1)=(3,3) and .A(1,−1)=(7,−7).
In the rotated coordinates y=Q⊤x the ellipse is 3y12+7y22=21The cross term disappears along the eigenvectors.
Semi-axes 21/3=7≈2.646 along (1,1) and 21/7=3≈1.732 along (1,−1)Divide by the eigenvalue: the smaller eigenvalue gives the longer axis.
Check the end of the long axis, ,7⋅21(1,1), where :x=y=3.5:(5−4+5)⋅3.5=21It lies on the ellipse.
Major semi-axis 7 along ,(1,1), minor semi-axis 3 along ;(1,−1); area π73=π21≈14.40Putting the long axis along the eigenvector of 7 gives a point where the form is 49 (Mistake 4).
Problem 9
Show that M⊤M is positive semidefinite for any matrix ,M, and positive definite exactly when the columns of M are independent. Test M1=111123 and .M2=111222.
v⊤M⊤Mv=(Mv)⊤(Mv)=∥Mv∥2≥0A squared length is never negative, so M⊤M is PSD.
,∥Mv∥2=0⟺Mv=0, and Mv is the combination of the columns with coefficients vSo v⊤M⊤Mv>0 for every v=0 exactly when no nonzero combination of the columns is .0.
,M1⊤M1=(36614), with minors 3 and 42−36=6Both positive: PD, as the columns (1,1,1) and (1,2,3) are independent.
,M2⊤M2=(36612), with determinant 0 and eigenvalues 0 and 15The second column is twice the first, and v=(2,−1) gives .M2v=0.
M⊤M is always PSD; M1⊤M1 is PD, M2⊤M2 is only PSD, with v⊤M2⊤M2v=0 at v=(2,−1)This is why the normal equations have a unique solution exactly when the features are not collinear.
Problem 10
Ridge regression minimizes .L(w)=∥Xw−y∥2+λ∥w∥2. Find the gradient and Hessian of .L. With X=M2 from Problem 9, y=(1,2,3) and ,λ=21, show that the Hessian is positive definite and find the unique minimizer.
∇L=2X⊤(Xw−y)+2λw and ∇2L=2(X⊤X+λI),L=w⊤(X⊤X+λI)w−2y⊤Xw+y⊤y, a quadratic form plus a linear term.
v⊤(X⊤X+λI)v=∥Xv∥2+λ∥v∥2>0 for v=0Whatever X is, when .λ>0. So L is strictly convex with one minimizer.
,X⊤X+21I=(3.56612.5), with eigenvalues 0.5 and ,15.5, and X⊤y=(6,12)The eigenvalues of ,X⊤X,0 and ,15, each move up by .λ.
,det=43.75−36=7.75, so w1=7.7512.5⋅6−6⋅12=3112 and w2=7.753.5⋅12−6⋅6=3124Cramer's rule on .(X⊤X+λI)w=X⊤y.
,∇2L=2(X⊤X+λI), PD with eigenvalues 1 and ;31;w∗=(3112,3124)Without λ the Hessian is singular and every w with w1+2w2=2 is a minimizer. Ridge picks one along ,(1,2), with ,w1+2w2=3160≈1.935, shrunk slightly below .2.
Where this goes wrong
1. The cross coefficient left unhalved
The coefficient of xy is copied straight into the matrix.
,q=3x2+4xy+2y2, with 3 and 2 on the diagonalRight so far: Problem 1.
“The xy coefficient goes off the diagonal: .A=(3442).”Both off-diagonal entries multiply ,xy, so together they give .8xy.
The form is indefinite, since detA=6−16=−10<0That matrix is the form .3x2+8xy+2y2. At (1,−1) it gives ,−3, while .q(1,−1)=1. With A12=2 the determinant is 2>0 and q is positive definite (Problem 4).
2. A positive diagonal taken as proof
A diagonal matrix with positive entries is positive definite, and the shortcut gets applied to every matrix.
B=(1221) has B11=B22=1>0Right so far: Problem 2. A positive diagonal is necessary, since .ei⊤Bei=Bii.
“Every diagonal entry is positive, so every x⊤Bx is positive.”The cross term 4xy can outweigh the squares.
B is positive definite,qB(1,−1)=1−4+1=−2, and the eigenvalues are 3 and .−1. A positive diagonal is not sufficient; a 2×2 also needs ,det>0, and here .detB=−3.
3. Leading minors used to test semidefiniteness
Sylvester's criterion is remembered as “check the leading minors”, with >0 relaxed to .≥0.
A=(000−1) has Δ1=0 and Δ2=0Right so far: both leading minors are .≥0.
“All leading minors are non-negative, so A is PSD.”For semidefiniteness every principal minor must be checked, including the bottom-right entry .−1.
A is positive semidefinite:(0,1)⊤A(0,1)=−1<0:A is negative semidefinite. The 1×1 principal minor A22=−1 is the one the leading minors skip.
4. The long axis along the largest eigenvalue
The biggest eigenvalue is thought of as the biggest direction, as it is for a covariance matrix.
5x2−4xy+5y2=21 has eigenvalues 3 along (1,1) and 7 along (1,−1)Right so far: Problem 8.
“The major semi-axis 7 points along the eigenvector of .7.”Along an eigenvector the form is ,λr2, so a large λ reaches 21 at a small .r.
The ellipse reaches 7⋅21(1,−1)There x=−y=3.5 and the form is ,(5+4+5)⋅3.5=49, not .21. The semi-axis along an eigenvector is :c/λ:21/7=3 along (1,−1) and 7 along .(1,1). For a Gaussian the ellipse is ,x⊤Σ−1x=c, whose eigenvalues are ,1/λ, which is why the covariance's largest eigenvalue does give the long axis.
5. The extremes read off the diagonal
On the unit circle the values at (1,0) and (0,1) are the diagonal entries, and these are taken as the extremes.
q=5x2+4xy+2y2 has q(1,0)=5 and q(0,1)=2Right so far: Problem 7.
“The coordinate axes give the largest and smallest values.”Only when the cross term is ,0, so that the axes are the eigenvectors.
On the unit circle, 2≤q≤5The eigenvalues are 6 and ,1, at 51(2,1) and .51(1,−2). The diagonal entries always lie between λmin and ,λmax, so they never show the extremes unless the matrix is diagonal.