1

Reading about the condition number of a matrix I encountered the equality $\kappa (M^{-1}A) = \kappa(M^{-1/2}AM^{-1/2})$ for some invertible matrices $A,M\in\mathbb R^{n\times n}$ and $A$ symmetric positive definite. Why does this hold? And can one say in general that $M^{-1}A = M^{-1/2}AM^{1/2}$?

dinosaur
  • 2,252
  • Are you sure you write the equality correctly? As it stands, the equality does not always hold -- at least not with the operator 2-norm. What norm is used for calculating the condition number? And is $M$ positive definite too? – user1551 Oct 18 '13 at 16:27
  • The full line says: $\kappa(M^{-1}A)=\kappa(M^{-1/2}AM^{-1/2})=\frac{\lambda_\mathrm{max}(M^{-1/2}AM^{-1/2})}{\lambda_\mathrm{min}(M^{-1/2}AM^{-1/2})}$ whereas $\lambda_\mathrm{max}$ and $\lambda_\mathrm{min}$ are the biggest and smallest eigenvalues. $M$ is only given as invertible. – dinosaur Oct 18 '13 at 16:37
  • All depends on the definition of $\kappa(\cdot)$ the author(s) of the text in question use. If they use $\kappa(X)=\lambda_{\max}(X)/\lambda_{\min}(X)$ then the equality is perfectly fine. Since you read supposedly something about preconditioning of SPD systems, I'm pretty sure that $M$ is supposed to be SPD as well. – Algebraic Pavel Oct 18 '13 at 22:42

1 Answers1

2

You wrote in your comment that

The full line says: $\kappa(M^{-1}A)=\kappa(M^{-1/2}AM^{-1/2})=\frac{\lambda_\max(M^{-1/2}AM‌​^{-1/2})}{\lambda_\min(M^{-1/2}AM^{-1/2})}$ whereas $\lambda_\max$ and $\lambda_\min$ are the biggest and smallest eigenvalues. $M$ is only given as invertible.

From what it says, it seems that actually,

  1. $M$ is positive definite,
  2. the condition number is defined using the operator 2-norm, and
  3. $M$ commutes with $A$.

If the above conditions are satisfied, the equality does hold because $M^{-1}A=M^{-1/2}AM^{-1/2}$ and for positive definite matrices, the ordered singular values coincide with the ordered eigenvalues.

You should read the paper again to see if there is any implication or passing mention that the above conditions are satisfied. If not, then either there are some other unspecified conditions, or the authors are simply wrong, because the equality does not hold in general. For a counterexample, suppose $\kappa(X):=\|X^{-1}\|_2\|X\|_2$ and consider $$ M^{-1/2}=\pmatrix{2&1\\ 1&1},\ M^{-1}=\pmatrix{5&3\\ 3&2},\ A=\pmatrix{1&0\\ 0&2}. $$ In this counterexample, only condition 3 is violated. One can verify that $$\kappa(M^{-1}A)\approx 42.98 \ne 38.47\approx\kappa(M^{-1/2}AM^{-1/2})=\frac{\lambda_\max(M^{-1/2}AM‌​^{-1/2})}{\lambda_\min(M^{-1/2}AM^{-1/2})}.$$

user1551
  • 139,064
  • Thank you for your answer. I have one last question: Does $M^{-1}A=M^{-1/2}AM^{-1/2}$ hold because M commutes with A? – dinosaur Oct 18 '13 at 18:01
  • @dinosaur Yes. Commuting Hermitian matrices can be simultaneously and unitarily diagonalised. It follows that if $M^{-1}$ commutes with $A$, then $M^{-1/2}$ commutes with $A$ too. Hence $M^{-1/2}AM^{-1/2}=M^{-1/2}M^{-1/2}A=M^{-1}A$. – user1551 Oct 18 '13 at 18:10
  • 1
    Note that when $A$ and $M$ do not commute but $M$ is unitary, we can have $\kappa(M^{-1}A)=\kappa(M^{-1/2}AM^{-1/2})$ albeit $M^{-1}A\ne M^{-1/2}AM^{-1/2}$. So, conditions 1 and 3 can be replaced by another set of conditions: $M$ is unitary and $M^{-1/2}$ is a unitary square root of $M^{-1}$. At any rate, the equality in question does not hold in general and some conditions are needed. – user1551 Oct 18 '13 at 18:11
  • Why should $A$ and $M$ commute or $M$ to be unitary? – Algebraic Pavel Oct 18 '13 at 22:27
  • @AlgebraicPavel They are not necessary conditions. They are sufficient conditions for the first equality -- i.e. $\kappa(M^{-1}A)=\kappa(M^{-1/2}AM^{-1/2})$ -- to hold (provided that the operator 2-norm is used to define condition number). – user1551 Oct 18 '13 at 22:44
  • I see. IMHO the authors use the definition of $\kappa$ based on extremal eigenvalues. – Algebraic Pavel Oct 18 '13 at 22:45
  • @AlgebraicPavel Thanks. It didn't occur to me that the authors define the condition number using eigenvalues. That certainly explains why $\kappa(M^{-1}A)=\kappa(M^{-1/2}AM^{-1/2})$. Yet I find the idea of defining the condition number of a potentially nonnormal matrix ($M^{-1}A$) using eigenvalues a bit weird. – user1551 Oct 18 '13 at 23:11