Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the matrix $A$ which is of size $m \times n$, with $m > n$. Let $Q = A^T A$.

How do I determine, if $Q$ is Semi-Positive-definite?

share|improve this question
    
Such $Q = A^T A$ is always positive semi-definite. Did you perhaps mean how to tell if it is not positive definite? –  hardmath Jan 18 '11 at 22:21

1 Answer 1

up vote 3 down vote accepted

Recall that $B$ is semi-positive-definite iff $x^T B x\ge 0$ for all vectors $x$, where the superscript $T$ denotes the transpose. In this case, $$x^TQx=x^T A^T A x.$$ Now, recall that $(Bv)^T=v^T B^T$, so $$x^TQ x=(Ax)^T(Ax).$$ Finally, note that the square of the norm $\|v\|$ of a vector $v$ is just $\|v\|^2=v^T v$, so $$x^T Qx=\|Ax\|^2 \ge0,$$ and this gives you that $Q$ is as wanted.

Note that in general this won't be positive definite, because there may be values of $x\ne0$ such that $Ax=0$. (This would be guaranteed if $m<n$. If $m>n$, it may or may not happen, it depends on $A$.)

share|improve this answer
    
Hi Andres. Can you explain why it's guaranteed to be positive definite for m<n? –  user1736 Jan 19 '11 at 0:44
    
@user1736: I believe Andres is saying it would be guaranteed not positive definite if $m \lt n$. This is because Q is nxn and rank(Q) is at most $min(m,n)$. –  hardmath Jan 19 '11 at 1:10
    
user1736: One way of seeing that $A$ is not positive definite if $m<n$ is noticing that when you solve $Ax=0$ by reducing the matrix to row-echelon form, you have at most $m$ pivots, so you have at least $n-m$ degrees of freedom left. –  Andres Caicedo Jan 19 '11 at 1:11
    
If $A$ is a matrix of zeros, Q is singular whether $m < n$ or not! In general, even if $m > n$, $A$ must have full row rank for $Q$ to be nonsingular. When $m < n$, $Q$ is always singular. –  Dominique Oct 26 '11 at 3:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.