In my understanding a matrix $A$ is $PSD$ iff there is a matrix $B$, so that $A=B^TB$.
If I have a square matrix $X$, which is singular (because of eigenvalues = 0) and I calculate the inner product $K = X^TX$, the resulting matrix $K$ has eigenvalues < 0.
Does this mean that K is not PSD?
The background of this question is to show that $K$ is invertible, which should be guaranteed with being PSD. This yields to the subsequent question: Is the inner product of a matrix invertible, even if the matrix itself is singular?
Example Code:
import numpy as np
from sklearn.datasets import load_digits
data = load_digits()
X = data['data']
X = X[0:X.shape[1]]
K = [email protected]
print("All eigenvalues of K >= 0:")
print(np.all(np.linalg.eigvals(K) >= 0))
Thank you in advance!
Consider $A\in\mathbb{R}^{m\times n}$ and define $K = A^\top A$. Then since $K^\top = (A^\top A)^\top = A^\top A = K$, we have that $K$ is symmetric. Furthermore, note that $x^\top Kx = x^\top A^\top Ax = (Ax)^\top Ax = \|Ax\|_2^2 \ge 0$ for all $x\in\mathbb{R}^n$. Therefore, we conclude that $K$ is positive semidefinite. As a corollary, all eigenvalues of $K$ must be nonnegative.
Now, to answer your question on invertibility, note that a positive semidefinite matrix is invertible if and only if it is positive definite, i.e. all of its eigenvalues are strictly positive. Therefore, $K = A^\top A$ is invertible if and only if $\text{rank}(K) = n$, which in turn holds when $\text{rank}(A) = n$. Since $\text{rank}(A)\le\min\{m,n\}$, this shows us that in order for $K$ to be invertible, it must be that $A$ is a narrow matrix ($n\le m$) with full column rank. In the case that $A$ is a strictly wide matrix ($m<n$), there is no possibility for $K$ to be invertible. You can also come to this conclusion by denoting a singular value decomposition of $A$ by $A = U\Sigma V^\top$ and noting that \begin{equation*} K = A^\top A = V\Sigma^\top U^\top U \Sigma V^\top = \sum_{i=1}^r \sigma_i^2 v_iv_i^\top, \end{equation*} where $\{\sigma_1,\sigma_2\dots,\sigma_r\}$ is the set of the $r=\text{rank}(A)$ nonzero singular values of $A$. In this case, we are summing $r$ rank-1 matrices, and therefore $\text{rank}(K)=n$ only if $r=n$.