Assume to have a Positie Semi Definite matrix $A\in\mathbb{R}^{d\times d}$ , defined as
$$A = \sum_{i=1}^n \alpha_i x_i x_i^\top$$
such that $\alpha_i \in [0,1]: \sum_{i = 1}^n \alpha_i = 1$, $x_i \in \mathbb{R}^d$, $n>d$.
Further, assume that $A$ is a singular matrix: $rank(A)<d$, and to have control over the terms $\alpha_i$, for $i = 1,…,n$.
Can we make $A$ invertible by removing one or more term ($\alpha_i = 0$) in the sum, or for some other choice of $\alpha_i$?
Best Answer
Since $\textrm{rank}(A) < d$, there is a non-trivial kernel or null space of $A$. Let $\mathbf{v}$ be in that null space: $A\mathbf{v} = \mathbf{0}$, the zero vector. Now consider $\mathbf{v}^{\mathsf{T}}A\mathbf{v}$. \begin{equation} \mathbf{v}^{\mathsf{T}}A\mathbf{v} ~=~ \mathbf{v}^{\mathsf{T}}\mathbf{0} ~=~ 0, \end{equation} but also \begin{eqnarray} \mathbf{v}^{\mathsf{T}}A\mathbf{v} &=& \mathbf{v}^{\mathsf{T}}\left(\sum_{i=1}^{n}\alpha_i\mathbf{x}_i\mathbf{x}_i^{\textsf{T}}\right)\mathbf{v}\\ &=& \sum_{i=1}^{n}\alpha_i(\mathbf{v}^{\mathsf{T}}\mathbf{x}_i)(\mathbf{x}_i^{\textsf{T}}\mathbf{v})\\ &=& \sum_{i=1}^{n}\alpha_i(\mathbf{v}^{\mathsf{T}}\mathbf{x}_i)^2, \end{eqnarray} because $\mathbf{v}^{\mathsf{T}}\mathbf{x}_i = \mathbf{x}_i^{\mathsf{T}}\mathbf{v}$. Since all the $\alpha_i$ are positive, every term in the sum in the final line is non-negative. In particular, there are no negative terms canceling out positive terms. That means that every single term in the sum is zero, so each dot-product (inner product) is zero. Removing an $\mathbf{x}_i$ will not fix that.
This shows that removing an $\mathbf{x}_i$ does not yield a new matrix with a trivial null space.