2
$\begingroup$

I'm having trouble with some maths regarding the expression of the matrix quadratic form (i.e. $x^TAx$) and the proof that, where the eigenvalues $\lambda_1,\lambda_2,...,\lambda_n$ are all positive, the quadratic form is positive definite.

My understanding is that the definition of positive-definiteness is when $x^TAx>0$ for all x where at least one element of $x \neq 0$.

My textbook produces the following proof, but I don't understand the last line:

Where $s_i$ = a normalized eigenvector of A, $\lambda_i$ = the corresponding eigenvalue, and $C = [s_1|s_2|...|s_n]$, $C^{-1}AC=D=$ the "diagonalization" of A.

Since the eigenvectors of A are orthonormal, $C^{-1} = C^T$.

Suppose we define a transformation $x=CX$. Then the equation becomes: $x^TAx = (CX)^{T}ACX = X^TDX = \lambda_1X_1^2 + \lambda_2X_2^2+...+\lambda_nX_n^2$.

It follows from this that a quadratic form is positive-definite if and only if all its eigenvalues are positive.

So, in summary, I don't understand why the following derivation true:

$x^TAx = \lambda_1X_1^2 + \lambda_2X_2^2+...+\lambda_nX_n^2$ therefore, for $x^TAx > 0$ for all x where at least one element of $x_i \neq 0$ to be true, $\lambda_1, \lambda_2, ..., \lambda_n > 0$.

Can someone please help with the derivation of the last step?a

Thanks in advance for your help.

  • 1
    I think your definition of positive definiteness may be the source of your confusion. The correct definition is that $A$ is positive definite if $x^TAx>0$ for **all** vectors $x$ other than the zero vector.2012-04-30
  • 0
    @WillOrrick that is what I mean by at least one element of x is not zero. To restate: for all x except x = [0;0]. Thanks for you comment though.2012-04-30
  • 0
    "...therefore, for $x^TAx\gt0$ with at least one element of $x_i\ne0$ to be true, $λ_1$, $λ_2$,...,$λ_n\gt0$." --- I still think you really need to change this to "...for $x^TAx\gt0$ to be true **for all** $x$ having at least one element $x_i\ne0$..." The "for all $x$" allows you to choose an $x$ that will help you reach the conclusion. Since $x^TAx\gt0$ has to be true for any $x$, you can choose $x$ in such a way that only one of the eigenvalues contributes. Then you can conclude that that eigenvalue must be positive. Repeat for every eigenvalue.2012-04-30
  • 0
    Thanks for adding that. I think you also need to correct it in the second gray box. This may help clarify the logic of the proof.2012-04-30
  • 0
    @WillOrrick no problem and fixed in the second gray box too :)2012-05-01
  • 0
    The statement in the second gray box is becoming a little bit hard to parse. I hope this is a fair phrasing: "From $x^TAx=\lambda_1X_1^2+\ldots+\lambda_nX_n^2$, it follows that the statement '$x^TAx\gt0$ for all $x$ with at least one element $x_i\ne0$' implies the statement '$\lambda_1,\ \lambda_2\ ,\ldots,\ \lambda_n\gt0$'." The contrapositive of this is '$\lambda_i\le0$ for at least one $i$ implies that $x^TAx$ is zero or negative for some $x$.' It may be easier to see why the contrapositive is true, which is essentially what leonbloy's answer shows.2012-05-02
  • 0
    correction: ...zero or negative for some **non-zero** $x$.2012-05-02

3 Answers 3

2

For the "if" part: if all of the $\lambda_j$ are positive then $\lambda_1X_1^2+\ldots+\lambda_nX_n^2$ is positive for all non-zero vectors $X$ and hence for all non-zero vectors $x$.

For the "only if" part: Suppose that $\lambda_1X_1^2+\ldots+\lambda_nX_n^2$ is positive for all non-zero vectors $x$. Then in particular, it is positive for the vector $x$ corresponding to the $X$ with $X_j=1$ and $X_k=0$ for all $k\ne j$. Therefore $\lambda_j$ is positive.

  • 0
    Thanks for your response. I don't understand how the latter is an "only if" proof - it seems to only prove that the expression is positive in the particular (not general) case where X is any vector with a single element equal to one and the others equal to zero. Consider the case where $X = [1, 1, 0]$ (which appears to be legal). Now we have $\lambda_1 + \lambda_2 > 0$ which isn't constrained to all $\lambda_i > 0$. Presumably this is a valid counter-example?2012-04-30
  • 0
    The eigenvalues are fixed numbers, depending only on $A$. They are what they are. One thing that we know about them is that $\lambda_1X_1^2+\ldots+\lambda_nX_n^2$ is positive for all $X$ except $X=0$. What conclusions about the values of $\lambda_j$ can we draw from this fact? Both your conclusion, $\lambda_1+\lambda_2\gt0$, and my conclusion, $\lambda_1\gt0$, are valid inferences. Mine just happens to be a stronger conclusion. For every non-zero choice of $X$ we get a conclusion. All of these conclusions are true statements about the $\lambda_j$.2012-04-30
  • 0
    My understanding is that we want to classify A (as positive-definite, negative-definite, etc) on the basis of its eigenvalues. In that case, we don't know that $\lambda_1X_1^2+\ldots+\lambda_nX_n^2$ is positive. We wish to determine this based on its eigenvalues. What you have given is a case where all the eigenvalues are positive and the matrix is positive definite, but not a general, proven rule for this.2012-04-30
  • 0
    @JonaGik The goal stated in your original post was to prove that a quadratic form is positive-definite if and only if all its eigenvalues are positive. In a previous comment, you questioned the proof of the "only if" part: a quadratic form is positive-definite only if all its eigenvalues are positive. This part is logically equivalent to the statement that if a quadratic form is positive-definite, then all of its eigenvalues are positive. In order to prove this, we take a positive-definite form. By definition of positive-definite, $x^TAx\gt0$ for all non-zero $x$. The manipulations...2012-04-30
  • 0
    (continued) ...in the proof quoted in your post establish that $\lambda_1X_1^2+\ldots+\lambda_nX_n^2\gt0$ for all non-zero $X$. This is not an assumption; it follows from the definition of positive-definiteness. We may then choose particular values for the $X_j$ in order to draw inferences about the $\lambda_j$.2012-04-30
  • 0
    The idea that we can choose a vector X to draw inference about the eigenvectors seems fallacious. Presumably we need to draw inferences about the eigenvectors _for all X_ which isn't necessarily the same as for some particular X.2012-05-08
  • 0
    @JonaGik : From the way we keep going back and forth, I would guess that you don't yet have a clear idea as to what the "only if" statement to be proved actually is. Please try to formulate that statement first. A clear conception should help you to get past the idea that the eigenvalues could be all positive for some $X$ and not all positive for other $X$. For a given $A$, the eigenvalues are particular numbers, and don't depend on $X$. Either they are all positive or they aren't.2012-05-08
  • 0
    The stement to be proved is: "A matrix is positive-definite if, and only if, it has, and only has, positive eigenvalues." Is that what you're looking for? Thanks again for your help.2012-05-17
  • 0
    @JonaGik: I think that it is clarifying to separate if-and-only-if statements into two separate statements, an "if" part, and an "only if" part. My suspicion is that your trouble stems from conflating the two. I have rephrased the "only if" part in the two-part comment about five comments above this one. Try to come up with your own phrasing. Then compare with mine and see whether we agree.2012-05-17
1

I misread the question. @WillOrrick's comment is relevant, if $A$ is positive definite, then you must have $x^T Ax > 0$ for any $x \neq 0$ (which is equivalent to at least one $x_i \neq 0$).

To illustrate why the 'for any' is important, consider the matrix $B = \left( \begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array} \right)$. Then $e_1^T B e_1 > 0$, but $B$ is not positive definite. The 'for any $x \neq 0$' is important.

Since you have $x^TAx = \sum_{i=1}^n \lambda_i X_i^2$ (with $x = CX$), we may choose $x=C e_k$, where $e_k$ is the $k$th basis vector (ie, $x$ is an eigenvector corresponding to $\lambda_k$). It follows that for this choice of $x$, we have $x^TAx = \sum_{i=1}^n \lambda_i X_i = \lambda_k X_k = \lambda_k$. Since $A$ is positive definite, it follows that $\lambda_k>0$. Since $k$ was arbitrary, we have that all eigenvalues are strictly positive.

  • 0
    Thanks very much for your response. This seems like its definitely on the right track. For $\sum_{i-1}^n X_i^2 = \underline \lambda \sum_{i-1}^n x_i^2$, I'm having trouble proving that to myself. Do you think you could prove it? Thanks again!2012-04-30
  • 0
    As far as I can tell, your proof assumes that A is a diagonal matrix so that the eigenvectors are [1, 0, ..., 0], [0, 1, 0, ..., 0], ..., [0, ..., 0, 1] and thus $x^TAx = \sum_{i=1}^n \lambda_i X_i = \lambda_k X_k = \lambda_k$ is true. It is possible for more than one $\lambda_iX_i^2$ combination to be non-zero in the general case. Is this right? If so, this doesn't produce a general proof. Also, does this proof prove only that if all eigenvectors are positive, the matrix is positive-definite, not if and only if all eigenvectors are positive the matrix is positive-definite?2012-04-30
  • 0
    Since $C$ is a basis of orthonormal eigenvectors, the matrix $C^T A C $ is diagonal. Note the distinction between $x$ and $X$ in the proof. We have $x^T Ax = (CX)^T A (CX) = X^T (C^T A C) X$.2012-04-30
  • 0
    Your question asked for elaboration of the last step, not an 'iff' proof? The elaboration shows that if $A$ is positive definite, then you must have $\lambda_i > 0$.2012-04-30
  • 0
    Are you saying that $e_k$ is some arbitrary eigenvector of $D = C^TAC$? Because then I can see this working. However, overall, the proof seems to still only prove that if (but not iff) all the eigenvectors are positive, the matrix is positive-definite. Is this right?2012-04-30
  • 0
    No, I am explaining why the derivation you mentioned in your question is true. This statement is 'if $x^T A x > 0$ whenever $x \neq 0$, then all eigenvalues are strictly positive'. This is the 'only if' part of your last comment.2012-04-30
0

The "only if" part (if $A$ is pos.def, then all eigenvalues are positive) can be proved more easily by absurd. Suppose that $x^t A x>0$ for all $x\ne 0$, but we have some $\lambda_i <0 $. The, calling $p_i$ ($\ne 0$) the associated eigenvector, we have $A p_i = \lambda_i p_i$ and multipliyin by $p_i^t$ we get $ p_i^t A p_i = \lambda_i |p_i|^2 <0 $ which contradicts the initial assumption.

  • 0
    Unless I'm missing something, this only proves that this is inconsistent when x is the negative eigenvalue's eigenvector - it isn't a proof for the general case.2012-05-08
  • 0
    No, it's general. Given the assumption ("Suppose that... for all $x$") we find one $x$ that contradicts that assumption. That's enough to prove that the assumption is false.2012-05-08