Principles of Mathematics in Operations Research

5.3 Semidefinite Matrices 75

cTAx •• [xk,0] A* * k * Xk

0

= x\AkXk > 0.

If we apply (i) <=> (ii) for Ak (its eigen values are different, but all

are positive), then its determinant is the product of its eigen values

yielding a positive result.

(Hi) =$• (iv): Claim: If A = LDU, then the upper left corner satisfy Ak =

LkDkUk-

Proof: A Lk^0

B C

Dk 0

0 E

UkF

0 G =

LkDkUk LkDkF

BDkUk BDkF + CEG

det Ak = det Lk det Dk det Uk — det Dk = d\ • di • • • dk =>

dk — fotA* (Pivot=Ratio of determinants). If all determinants are

positive, then all pivots are positive.

(iv) => (v): In a Gaussian elimination of a symmetric matrix U = LT,

then A = LDLT. One can take the square root of positive pivots

dt > 0. Then,

A = Ly/D~VDLT = WTW.

(v) =* (i):

xTAx = xTWTWx = \\Wx\\^2 > 0.

Wx = 6 => x = 9 since W is nonsingular.

Therefore, xTAx > 0, Vcc ^ 6. D

Remark 5.2.2 The above theorem would be exactly the same in the complex

case, for Hermitian matrices A — AH.

5.3 Semidefinite Matrices

Theorem 5.3.1 A real symmetric matrix A is positive semidefinite if and

only if one of the following holds:

i. xTAx > 0, Vx ^ 6;

ii. All the eigen values of A satisfy A; > 0;

Hi. All the submatrices Ak have nonnegative determinants;

iv. All the pivots (without row exchanges) satisfy d, > 0;

v. 3 a possibly singular matrix W 3 A = WTW;

Remark 5.3.2 xTAx >0o\i>0is important.

A = QAQT => xTAx = xTQAQTx = yTAy = Xxy\ + ••• + \nyl,

and it is nonnegative when Ai 's are nonnegative. If A has rank r, there are r

nonzero eigen values and r perfect squares.