Proof of A Nonzero Positive Semidefinite Matrix Factors as BBᵀ with BᵀB Invertible

Throughout, matrix products are associative and transposes reverse products (Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (i), Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (vii)), and two matrices of the same size are equal when they have the same columns $Me_{k}$ (Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (vi)).

Step 1 (diagonalization and the rank $r$). By The Spectral Theorem for Real Symmetric Matrices (i) there are $Q\in\mathrm{O}(d)$ and $\lambda\in\mathbb{R}^{d}$ with $\lambda_{1}\ge\dots\ge\lambda_{d}$ and

$$\Sigma=Q\operatorname{diag}(\lambda)Q^{\top};$$

every $\lambda_{k}\ge0$ by Every Positive Semidefinite Matrix Has Exactly One Positive Semidefinite Square Root (ii), and $Q^{\top}Q=I_{d}$ by Orthogonal Real Matrices (i). Some $\lambda_{k}$ is nonzero: otherwise $\operatorname{diag}(\lambda)=0_{d}$ and $\Sigma=Q\,0_{d}\,Q^{\top}=0_{d}$, contrary to the hypothesis. If no $\lambda_{k}$ vanishes, let $r=d$. Otherwise let $k_{0}$ be the least $k\in[d]$ with $\lambda_{k}=0$, which exists because the natural numbers are well-ordered (The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor (i)); then $k_{0}\ge2$, since $\lambda_{1}=0$ would force $0\le\lambda_{k}\le\lambda_{1}=0$ for all $k$; and we let $r=k_{0}-1$. In both cases $r\in[d]$ and

$$\lambda_{k}\neq0\quad(k\le r),\qquad\lambda_{i}=0\quad(r<i\le d),$$

the first by the choice of $k_{0}$, the second because $0\le\lambda_{i}\le\lambda_{k_{0}}=0$ for $i\ge k_{0}$.

Step 2 (the factor). By Every Positive Semidefinite Matrix Has Exactly One Positive Semidefinite Square Root (i) there is a positive semidefinite $R\in\mathcal{S}(d)$ with $RR=\Sigma$. By Every Positive Semidefinite Matrix Has Exactly One Positive Semidefinite Square Root (ii), $R=Q\operatorname{diag}(s)Q^{\top}$ with $s=(\sqrt{\lambda_{1}},\dots,\sqrt{\lambda_{d}})$. Using $Q^{\top}Q=I_{d}$ and the rules for diagonal matrices of Eigenvalues: the Determinant Criterion, Diagonal Matrices, Orthogonal Similarity and Orthogonality of Eigenvectors of Symmetric Matrices (ii),

$$\operatorname{diag}(s_{1}^{2},\dots,s_{d}^{2})=\operatorname{diag}(s)\operatorname{diag}(s)=Q^{\top}RRQ=Q^{\top}\Sigma Q=\operatorname{diag}(\lambda),$$

so $s_{k}^{2}=\lambda_{k}$ for every $k\in[d]$.

Let $J\in\mathbb{R}^{d\times r}$ have the entries $J_{ij}=1$ if $i=j$ and $J_{ij}=0$ otherwise, and put

$$B=Q\operatorname{diag}(s)J\in\mathbb{R}^{d\times r}.$$

As $\operatorname{diag}(s)^{\top}=\operatorname{diag}(s)$,

$$BB^{\top}=Q\bigl[\operatorname{diag}(s)JJ^{\top}\operatorname{diag}(s)\bigr]Q^{\top}.$$

We compare the bracket with $\operatorname{diag}(\lambda)$ column by column. For $i\in[d]$, the vector $J^{\top}e_{i}$ is $e_{i}\in\mathbb{R}^{r}$ if $i\le r$ and $0$ if $i>r$, so $JJ^{\top}e_{i}=e_{i}$ if $i\le r$ and $JJ^{\top}e_{i}=0$ if $i>r$ (Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (vi), Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (v)). Since $\operatorname{diag}(s)e_{i}=s_{i}e_{i}$,

$$\operatorname{diag}(s)JJ^{\top}\operatorname{diag}(s)e_{i}=\begin{cases}s_{i}^{2}e_{i}=\lambda_{i}e_{i}, & i\le r,\\ 0=\lambda_{i}e_{i}, & i>r,\end{cases}$$

using $\lambda_{i}=0$ for $i>r$ from Step 1. Also $\operatorname{diag}(\lambda)e_{i}=\lambda_{i}e_{i}$, so the bracket equals $\operatorname{diag}(\lambda)$, and $BB^{\top}=Q\operatorname{diag}(\lambda)Q^{\top}=\Sigma$.

Step 3 ($B^{\top}B$ is invertible). Using $Q^{\top}Q=I_{d}$ and $\operatorname{diag}(s)\operatorname{diag}(s)=\operatorname{diag}(\lambda)$ from Step 2,

$$B^{\top}B=J^{\top}\operatorname{diag}(s)Q^{\top}Q\operatorname{diag}(s)J=J^{\top}\operatorname{diag}(\lambda)J .$$

For $k\in[r]$ we have $Je_{k}=e_{k}\in\mathbb{R}^{d}$, $\operatorname{diag}(\lambda)e_{k}=\lambda_{k}e_{k}$ and $J^{\top}e_{k}=e_{k}\in\mathbb{R}^{r}$, so $B^{\top}Be_{k}=\lambda_{k}e_{k}$; comparing columns,

$$B^{\top}B=\operatorname{diag}(\lambda_{1},\dots,\lambda_{r}).$$

If $B^{\top}Bx=0$ for some $x\in\mathbb{R}^{r}$, then $\lambda_{k}x_{k}=0$ for every $k\in[r]$ (Eigenvalues: the Determinant Criterion, Diagonal Matrices, Orthogonal Similarity and Orthogonality of Eigenvectors of Symmetric Matrices (ii)), and $\lambda_{k}\neq0$ by Step 1, so $x=0$. Hence $B^{\top}B$ has trivial kernel and is invertible by Criteria for Invertibility of a Square Real Matrix (vi) (with Criteria for Invertibility of a Square Real Matrix (i)).