# Determine if a matrix is Semi-Positive-definite

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?

-
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

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$.)
@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. – Andrés E. 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