Preservation of Positive-Definiteness from Small Perturbations

Question

Let $A$ with real positive entries be a Hermitian positive definite matrix. I'm wondering if one perturbs $A$, e.g., $\hat{A}=A+\Delta A$, would the matrix still be positive definite? I'm told this is particularly true so long as the perturbation satisfies the condition number bound $$\frac{\|\Delta A\|}{\|A\|} < \frac{1}{K(A)},$$ where $K(A)$ is the condition number $K(A)=\|A^{-1}\|\|A\|$ (all in the Frobenius norm). I'm stuck figuring out how to prove this. Since $A$ is positive definite, it has a unique Cholesky decomposition $A=LL^*$ and so $\hat A=LL^*+\Delta A$. But this leads me nowhere in proving that $\hat A$ too has unique Cholesky decomposition dependent on the condition number.

Answer 1

The condition you've given will follow from the weaker bound $$ \|\Delta A\|_2 < \|A^{-1}\|^{-1}_2 $$ where $\|\cdot\|_2$ is the induced norm from the Euclidean metric.

We can argue as follows. For $t > 0$ sufficiently small, $A_t = A + t \Delta A$ is going to be PD by some general considerations (this is a good exercise). Assume that $\Delta A$ obeys the bound given, and for the sake of contradiction, assume that for some $t \leq 1$, $A_t$ is not positive definite.

I claim that there is a $t' \leq 1$ such that $A_{t'}$ has a zero eigenvalue. Pursuing this, let $v \in \ker A_{t'}$ be a unit vector. Then $A_{t'} v = 0 = A v + t'\Delta A v$ and so $$ \|A^{-1}\|_2^{-1} \leq \|A v\|_2 = t' \|\Delta A v\|_2 \leq \|\Delta A\|_2 $$ which is a contradiction.

Something to consider: this proof uses the connectedness of the set of PD matrices and the fact that when crossing continuously from the PD region to the SPD region, you necessary hit an SPD matrix with nontrivial kernel.

---

EDIT: Below is a simpler proof that doesn't use any topology.

Let $A$ be PD with eigenvalues $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n > 0$, counted with multiplicity. In particular, $\sigma_1 = \|A\|_2$ and $\sigma_n = \|A^{-1}\|_2^{-1}$. Writing the eigenvalues of the perturbation $\Delta A$ as $\{\eta_i\}_{1 \leq i \leq n}$ (with multiplicity) we have $\|\Delta A\|_2 = |\eta_j| = \max\{\eta_i \mid 1 \leq i \leq n\}$ for some $j$, which we take to be $1$ by re-indexing. Our condition ensures that $$|\eta_1| < \sigma_n$$.

Let $A' = A + \Delta A$ and assume that $(A'v, v) \leq 0$ for some unit vector $v$. We have $$ (A v, v) \leq - (\Delta A v, v) $$ Notice that $(Av, v) \geq \sigma_n$ and that $(\Delta Av, v) \leq |\eta_1|$ (this amounts to checking the Raleigh quotient and applying an appropriate minmax principle, if you like). Thus $\sigma_n \leq |\eta_1|$, which is a contradiction to our initial estimate.