Relationship Between Determinant and Matrix Rank

Question

Let $n\in \mathbb{N}$, and $S\in \mathbb{R}^{n\times n}$ be a symmetric positive semi-definite (PSD) matrix with rank $r \triangleq \mathrm{rank(S)}\leq n$. Can $r$ be bounded in terms of the determinant of some function of $S$?

Answer 1

At least a lower-bound is possible; in fact, the following holds for any PSD matrix $S$: \begin{align} (1+\|S\|_{\mathrm{op}})^r \geq \det(I_n +S), \end{align} where $\|S\|_{\mathrm{op}} \triangleq \sup_{x\in \mathbb{R}^n\setminus\{0\}} \|S x\|_2/\|x\|_2$ is the operator norm of $S$.

Proof. Since $S$ is PSD, there exists an orthogonal matrix $U\in \mathbb{R}^{n\times n}$, and $\lambda_1\geq \dots \geq \lambda_n\geq 0$ such that $$S= U\mathrm{diag}(\lambda_1,\dots,\lambda_n) U^\top.$$ In this case, the eigenvalues of $S$ are $\lambda_1,\dots, \lambda_n$ in decreasing order. This implies that \begin{align} \det(I_n +S)&= \det(U (I_n+\mathrm{diag}(\lambda_1,\dots, \lambda_n) )U^\top), \\ &= \det(U) \det(I_n +\mathrm{diag}(\lambda_1,\dots, \lambda_n)) \det(U^\top),\\ &=\det(I_n +\mathrm{diag}(\lambda_1,\dots, \lambda_n)),\\ & =\prod_{i=1}^n(1+\lambda_i),\hspace{6cm} (1) \end{align} where the penultimate equality follows by the fact that $\det(U)\det(U^\top)=1$, since $U$ is orthogonal. Now, since $S$ has rank $r$, we must have $\lambda_{n-r+1}=\dots=\lambda_{n}=0$. Furthermore, by the definition of the operator norm, we have $\|S\|_{\mathrm{op}}=\lambda_1\geq \dots\geq \lambda_n$. This, together with (1) implies that \begin{align} \det(I_n +S) &=\prod_{i=1}^r(1+\lambda_i),\\ & \leq (1+\|S\|_{\mathrm{op}})^r. \end{align}

Answer 2

Along similar lines, you have an upper bound if you know the lowest non-zero eigenvalue of $S$ (or equivalently, the largest eigenvalue of the Moore-Penrose pseudoinverse $S^+$). If $\lambda_{\min}$ denotes this eigenvalue, then $$ (1 + \lambda_{\min})^r \leq \det(I_n + S). $$ That is, we have $$ \frac{\log\det(I + S)}{\log(1 + \|S\|_{\mathrm{op}})} \leq r \leq \frac{\log\det(I + S)}{\log (1 + \lambda_{\min})}. $$