Is $A^TA$ positive semi-definite for any real matrix $A$?

Question

The question is written in title.

I read a theorem saying:

Suppose $A\in \mathbb R^{n\times n}$ is symmetric. Then the following are equivalent.

$A$ is positive semidefinite.
Eigenvalues of $A$ are all non-negative.
$A$ can be factored as $A=G^TG$ where $G$ is an $p\times n$ matrix for some $p$.

The reason why I am asking is that I have a matrix $X$ and get some negative eigenvalues of $X^TX$ using either MatLab or R.

$A^\top A$ is always positive semi-definite. Simply consider the any vector $x$, and then $\langle A^\top Ax,x\rangle = \langle Ax,Ax\rangle = |Ax|^2 \geq 0$. — Yousuf Soliman, Jul 07 '17 at 05:49
@Covvar Recall that the definition of the Euclidean inner product is given by $\langle x,y\rangle := x^\top y$. The first equality then follows from basic properties of the transpose and since matrix vector multiplication is associative. — Yousuf Soliman, Jul 07 '17 at 07:40

Robert Israel · Accepted Answer · 2017-07-07T06:01:41.727

The theorem is correct. If $A$ is a real matrix, $A^T A$ is indeed positive semidefinite, and its eigenvalues are all nonnegative. Matlab and R are using numerical methods, and roundoff error can cause some eigenvalues that should be $\ge 0$ to become negative.

For a simple example, let's suppose you're using floating-point decimal arithmetic with only two digits, and let $$ A = \pmatrix{41 & 29\cr 91 & 70\cr}$$ In exact arithmetic, $$A^T A = \pmatrix{9962 & 7559\cr 7559 & 5741\cr}$$ which is positive definite. But since we're only using two-digit arithmetic, those entries have to be rounded.
The rounded version is $$ \pmatrix{1.0 \times 10^4 & 7.6 \times 10^3\cr 7.6 \times 10^3 & 5.7 \times 10^3}$$ which is not positive semidefinite.

Thank you for clarifying. – Maggie Mak Jul 07 '17 at 05:56 — Maggie Mak, Jul 07 '17 at 05:56

Is $A^TA$ positive semi-definite for any real matrix $A$?

1 Answers1