0

Let $A, B ∈ \mathbb{R}^{n×n}$ symmetric. Show that conditional number $$κ(B^{−1}A) ≤ \frac{µ_1}{µ_0}$$ holds, if $B ∈ \mathbb{R}^{n×n}$ is a symmetric positive definite matrix satisfying $$µ_0(Bx, x) ≤ (Ax, x) ≤ µ_1(Bx, x), ∀x ∈ R^n$$ for some $0 < µ_0, µ_1 ∈ R$, $(\cdot,\cdot)$ is dot Euclidean product.

I have seen the proof of above statement in my lecture note. However, there is a mistake in the proof since they use the fact $κ(B^{−1}A) = \frac{\lambda_{\max}(B^{−1}A)}{\lambda_{\min}(B^{−1}A)}$. But its not correct because matrix $B^{−1}A$ is not symmetric. I was wonder is the above statement true or false. Can anyone give me a proof or a counter example? Thank you in advance !

David Li
  • 379

1 Answers1

2

Use the matrix $B^{-\frac12}AB^{-\frac12}$ instead of $B^{-1}$, where $B^{-\frac12}$ is the unique positive definite square root of the positive definite $B^{-1}$.

Note that if $B^{-1}Av=λv$, then also $$ B^{-\frac12}Av=λB^{\frac12}v \iff (B^{-\frac12}AB^{-\frac12})(B^{\frac12}v)=λ(B^{\frac12}v) $$ so that the eigenvalues of both matrices are the same.

The claim as presented is slightly wrong, since the condition number in the 2-norm is the quotient of the largest and smallest singular values, not the eigenvalues. For SPD matrices these are equal, but not for other matrices.

To approach the problem, re-interpret the original inequalities as a statement about an elliptical norm $$ (x,y)_B=(B^{\frac12}x,B^{\frac12}y)_2 $$ Then changing variables to $y=B^{\frac12}x$, this inequality reads as $$ µ_0\le\frac{(y, B^{-\frac12}AB^{-\frac12}y)_2}{(y,y)_2}\le µ_1 $$ which bounds the singular values of the symmetric $B^{-\frac12}AB^{-\frac12}$. Thus for the elliptical condition number related to the elliptical norm you get $$ κ_B(A) =κ_2(B^{-\frac12}AB^{-\frac12}) =\frac{σ_{\rm max}(B^{-\frac12}AB^{-\frac12})}{σ_{\rm min}(B^{-\frac12}AB^{-\frac12})} =\frac{λ_{\rm max}(B^{-\frac12}AB^{-\frac12})}{λ_{\rm min}(B^{-\frac12}AB^{-\frac12})} =\frac{λ_{\rm max}(B^{-1}A)}{λ_{\rm min}(B^{-1}A)} \le\frac{µ_1}{µ_0} $$

This should capture what was actually intended to be claimed about the condition number and thus the applications of it.

Lutz Lehmann
  • 126,666
  • Hi @Lutzl If two matrix has the same eigenvalues. Does it imply that they have same conditional number? – David Li Jan 27 '16 at 09:48
  • See this link for the detail http://math.stackexchange.com/questions/531161/condition-number-of-a-product-of-matrices – David Li Jan 27 '16 at 10:39
  • Yes, the condition number of $B^{-1}A$ is about the singular values of that matrix, which are the square roots of the eigenvalues of $B^{-1}A^2B^{-1}$ or $AB^{-2}A$. – Lutz Lehmann Jan 27 '16 at 12:22
  • Hi @Lutzl what is condition number of $B^{-1}A$? – David Li Jan 27 '16 at 14:24
  • That is the question. The quoted text assumes the max. quotient of eigenvalues, but in general $κ(M)=|M|·|M^{-1}|=σ{max}(M)/σ{min}(M) = \sqrt{λ{max}(M^*M)/λ{min}(M^*M)}$. – Lutz Lehmann Jan 27 '16 at 15:12