Principles of Mathematics in Operations Research

76 5 Positive Definiteness

Remark 5.3.3 (Indefinite matrices) Change of Variables: y = Cx. The

quadratic form becomes yTCTACy. Then, we have congruence transforma-

tion: A H-> CT AC for some nonsingular C. The matrix CT AC has the same

number of positive (negative) eigen values of A, and the same number of zero

eigen values. If we let A = I, CT AC = CTC. Thus, for any symmetric matrix

A, the signs of pivots agree with the signs of eigen values. A and D have the

same number of positive (negative) entries, and zero entries.

5.4 Positive Definite Quadratic Forms

Proposition 5.4.1 If A is symmetric positive definite, then

P(x) = -xTAx - xTb

assumes its minimum at the point Ax = b.

Proof. Let x 9 Ax = b. Then, Vy € Rn,

P(y) - P(x) = (\yTAy - yTb^ - {^xTAx - xTb^

= -^VTAy - yTAx + -xTAx

= ^{V ~ xf A{y - x)

>0.

Hence, Vy ^ x, P(y) > P(x) => x is the minimum. D

Theorem 5.4.2 (Rayleigh's principle) Without loss of generality, we may

assume that

Ai < A 2 < • • • < An.

The quotient, R(x) — x ^ , is minimized by the first eigen vector v\ and its

minimum value is the smallest eigen value \\:

vfAvi ufAi«i

R(Vl) = —f = -^T = Al-

v( Vi v[ v\

Remark 5.4.3 Va;, R(x) is an upper bound for X.

Remark 5.4.4 Rayleigh's principle is the basis for the principle component
analysis, which has many engineering applications like factor analysis of the
variance covariance matrix (symmetric) in multivariate data analysis.

Corollary 5.4.5 If x is orthogonal to the eigen vectors vi,...,Vj-i, then
R(x) will be minimized by the next eigen vector Vj.