next up previous
Next: Negative eigenvalues Up: Sufficient Conditions for Multiply Previous: Introduction.

Non-positive eigenvalues

As in [6], we define tex2html_wrap_inline548 to be the vector such that tex2html_wrap_inline550 .

lemma36

Proof: Certainly tex2html_wrap_inline568 , where tex2html_wrap_inline570 and tex2html_wrap_inline572 . Take tex2html_wrap_inline574 so that tex2html_wrap_inline576 . Defining tex2html_wrap_inline578 to be the orthogonal projection of tex2html_wrap_inline574 onto the range of A, one finds that tex2html_wrap_inline584 , concluding the proof.

Now define the matrix B by

displaymath536

  lemma46

Proof: This is essentially Lemma 1 of [3], obtained by writing out the matrix multiplication. Note that tex2html_wrap_inline618 is orthogonal to ker(A).

  lemma59

Proof: If the lemma is false, then there exist sequences tex2html_wrap_inline642 and tex2html_wrap_inline644 so that tex2html_wrap_inline646 and tex2html_wrap_inline648 . By taking a subsequence, we may assume that tex2html_wrap_inline650 converges (strongly) to tex2html_wrap_inline652 . Therefore tex2html_wrap_inline654 converges to z as well. Since Y is closed, tex2html_wrap_inline660 , so tex2html_wrap_inline654 converges to the zero vector. This contradicts the assumption that tex2html_wrap_inline646 .

  theorem63

Proof: Let tex2html_wrap_inline702 be the span of the vectors tex2html_wrap_inline704 , and tex2html_wrap_inline706 its orthogonal complement. tex2html_wrap_inline708 is said to be strongly positive on the space tex2html_wrap_inline706 if for some tex2html_wrap_inline712 there holds tex2html_wrap_inline714 for all tex2html_wrap_inline716 . This condition is sufficient to imply that y is a strong local constrained minimum (see [1, chapter 3,]), so this is what we need to prove.

Let x be an arbitrary element of tex2html_wrap_inline706 . I will first show that there exist unique scalars tex2html_wrap_inline724 , tex2html_wrap_inline438 , tex2html_wrap_inline728 so that tex2html_wrap_inline730 is perpendicular to tex2html_wrap_inline732 , tex2html_wrap_inline438 , tex2html_wrap_inline736 . We seek tex2html_wrap_inline724 , tex2html_wrap_inline438 , tex2html_wrap_inline728 to solve

eqnarray72

so that it certainly suffices to show that the matrix

displaymath537

is invertible. If not, then some non-trivial linear combination of the columns is the zero vector, implying that there is a non-trivial linear combination tex2html_wrap_inline744 of the vectors tex2html_wrap_inline746 , tex2html_wrap_inline438 , tex2html_wrap_inline618 which is perpendicular to tex2html_wrap_inline732 , tex2html_wrap_inline438 , tex2html_wrap_inline736 . This leads to a contradiction as follows. Since tex2html_wrap_inline744 is a non-trivial vector which is orthogonal to all of the non-positive eigenvectors of A, tex2html_wrap_inline762 . On the other hand, a non-trivial linear combination tex2html_wrap_inline764 satisfies

displaymath538

since tex2html_wrap_inline766 is the tex2html_wrap_inline768 eigenvalue of B.

Since x is orthogonal to all of the tex2html_wrap_inline774 's, tex2html_wrap_inline776 for i=1, tex2html_wrap_inline438 , n. (Of course if tex2html_wrap_inline784 , tex2html_wrap_inline786 for all i.) It follows that

  equation94

for all i. Let tex2html_wrap_inline792 . Then

  equation99

holds for all i.

Now, v is certainly perpendicular to ker(A), since v is perpendicular to all eigenspaces corresponding to non-positive eigenvalues. Using this fact and the A-orthogonality of the tex2html_wrap_inline804 's, equation 2.2 becomes

displaymath539

Substituting this into

eqnarray108

we obtain

displaymath540

with the last inequality due to the fact that the first k eigenvalues of B are negative. Since v is orthogonal to tex2html_wrap_inline732 , tex2html_wrap_inline438 , tex2html_wrap_inline736 , it follows that

  equation122

and we therefore must bound tex2html_wrap_inline818 from below in terms of tex2html_wrap_inline820 . We will do this by applying Lemma 2.3, where Y will be tex2html_wrap_inline706 and Z is the span of tex2html_wrap_inline828 . To apply this lemma, it is necessary to show that the intersection of tex2html_wrap_inline706 and the span of tex2html_wrap_inline832 is trivial.

Suppose that tex2html_wrap_inline834 , i.e., that tex2html_wrap_inline836 for j=1, tex2html_wrap_inline438 , n. By equation 2.1, tex2html_wrap_inline844 for all i. Since the tex2html_wrap_inline804 's are chosen to be orthogonal to ker(A), we have tex2html_wrap_inline852 holding for all i. By the A-orthogonality of the tex2html_wrap_inline804 's and the assumption that the first k eigenvalues of B are negative, it follows that tex2html_wrap_inline864 . Thus the intersection of tex2html_wrap_inline706 and the span of tex2html_wrap_inline832 is the zero vector.

Since tex2html_wrap_inline870 , Lemma 2.3 yields a positive tex2html_wrap_inline872 so that tex2html_wrap_inline874 if tex2html_wrap_inline876 . By normalizing we obtain tex2html_wrap_inline878 for general tex2html_wrap_inline880 , where tex2html_wrap_inline872 does not depend x. Substituting this into equation 2.3 we obtain that

displaymath541

for tex2html_wrap_inline716 . This strong positivity on tex2html_wrap_inline706 implies that y is a strong constrained local minimum, as mentioned above.


next up previous
Next: Negative eigenvalues Up: Sufficient Conditions for Multiply Previous: Introduction.

Tom Vogel
Tue Aug 20 10:23:22 CDT 1996