# Upper bound on condition number in linear preconditioning

I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $$A = M-N$$, where $$A,M,N$$ are all symmetric and positive definite matrices. Define iteration matrix $$C=I-M^{-1}A$$. We aim to show that the condition number $$\kappa(I-C)=\kappa(M^{-1}A)$$ is not too large, which ensures that iterative method converges fairly fast. Wikipedia gives the following bound on $$\kappa(M^{-1}A)$$: $$\kappa(M^{-1}A) \leq \frac{1+\rho(C)}{1-\rho(C)}$$ where $$\rho(C)$$ denotes the spectral radius of matrix $$C$$. Here we are taking the condition number with respect to the Euclidean 2-norm. That is to say, we have $$\kappa(M^{-1}A) = \frac{\sigma_{max}(M^{-1}A)}{\sigma_{min}(M^{-1}A)}$$, where $$\sigma_{max},\sigma_{min}$$ denote the largest/smallest singular value of any matrix, respectively.
Any ideas on proving this upper bound? Any help/hint would be greatly appreciated!
• Hint: $\kappa(M^{-1}A)=\kappa(I-(I-M^{-1}A))$. Dec 10, 2020 at 5:05
• HI Professor Bangerth, Thank you so much for your response! I have tried to use the expression you gave above. However, it seems that I still can't find an ideal upper bound for $\kappa(I-C)$. FYI, I have even tried more advanced tools like Weyl's inequality (bounding the singular values of matrix sums). It seems that it's still pretty hard to characterize $\sigma_{max}(I-C)$ and $\sigma_{min}(I-C)$. I guess here I probably need to use some properties related to $C$? (AS $C$ is a product of two symmetric and positive definite matrices, $C$ probably has some really nice properties?) Dec 10, 2020 at 5:36
• For instance, I can show that all eigenvalues of $C$ are in the interval $(0,1)$. My guess is that this might imply that the 2-norm $||I-C||$ can't be too large? (ideally upper bounded by $1+\rho(C)$)? Dec 10, 2020 at 5:42