Why $X^TX$ not always positive semidefinite using numpy.linalg.eig?

Question

We can use $z^T (X^TX)z = (Xz)^T(Xz)=||Xz||^2_2 \geq 0$ to prove $X^TX$ is positive semidefinite. However, when I use numpy.linalg.eig to compute the eigenvalues of dot product matrix, I cannot get all positive eigenvalues. How to explain for it?

import numpy as np
import math
np.random.seed(33)
X = np.random.randint(10, size=(2,6))
print(X)
Kernel_Matrix = np.dot(X.T,X)
eigenvalue, eigenvector = np.linalg.eig(Kernel_Matrix)
print(eigenvalue > 0)
print(eigenvalue)

Output:

[[4 7 8 2 2 9]
 [9 3 6 3 3 1]]
[[ 97  55  86  35  35  45]
 [ 55  58  74  23  23  66]
 [ 86  74 100  34  34  78]
 [ 35  23  34  13  13  21]
 [ 35  23  34  13  13  21]
 [ 45  66  78  21  21  82]]
[ True  True False False  True False]
[ 3.12680220e+02  5.03197805e+01 -9.39575362e-15 -1.44635182e-14
  1.43755791e-16 -7.87904824e-32]

Answer 1

As Ben Grossmann pointed out, for this matrix, it is actually easy to calculate by hand the eigenvalues and convince yourself that the error lies within the floating arithmetic.

First, you should calculate the rank of the matrix, and you'll see that it is 2 (I doublechecked it with some online software and the rank is indeed 2). Note that this can be calculated by hand, and it does not involve any approximation, while the numerical computation of eigenvalues of large matrices involves errors.

The above means that $\lambda=0$ is an eigenvalue of multiplicity 4 [you can even calculate the eigenspace]. Anyhow, at this point you can already see that there is a mistake with the output: 4 of your eigenvalues are 0

Then $$\det(xI-A)= (x^2+ax+b)x^4$$

You can easily figure out what $a,b$ are by simply plugging in two values for $x$ and solving. Or even better, you can recall that $a=-\operatorname{tr}(A)$ and then you only need to figure out what $b$ is.

Answer 2

You've printed out the result of computing 6 numbers using IEEE floating point arithmetic; you have not printed out the 6 eigenvalues of $X^t X$ for any real matrix $X$, because those are all nonnegative real numbers.

Notice that your "negative" fourth eigenvalue is smaller in absolute value than $10^{-14}$; that's pretty much the IEEE float world whispering in your ear "this is zero, but disguised by roundoff errors."

There's a difference between computers and mathematics, and it's good to know (and embrace) that as early as possible.

I recommend a read-though of Trefethen and Bao's section on floating-point arithmetic in Numerical Linear Algebra; it's wonderfully compact and informative.