Relation between $\infty$-norm and 2-norm condition number of PD matrix

469 Views Asked by At

Consider a positive-definite matrix $A$ in $\mathrm{R}^{n\times n}$ and let $\kappa_{\infty} = \|A\|_{\infty}\|A^{-1}\|_{\infty}$ and $\kappa_2 = \|A\|_2 \|A^{-1}\|_2$, with $\|A\| _p = \sup_{x \ne 0} \frac{\| A x\| _p}{\|x\|_p}$. It is known that

\begin{equation} \frac{1}{\sqrt{n}}\|A\|_\infty \leq \|A\|_2 \leq \sqrt{n} \|A\|_\infty \end{equation}

and therefore: \begin{equation} \kappa_\infty = \|A\|_{\infty}\|A^{-1}\|_{\infty} \leq \sqrt{n}\|A\|_2 \sqrt{n}\|A^{-1}\|_2 = n\cdot\kappa_2 \end{equation}

Is this the best relation that can possibly be found between $\kappa_\infty$ and $\kappa_2$? Does $A$ being positive definite allow to refine the bound somehow?

Edit 19/5/2020

With reference to this question, since a positive-definite matrix is symmetric (if the definition is strict), then $\|A\|_2 \leq \|A\|_\infty$, so at least a better lower bound is possible:

\begin{equation} \kappa_2 \leq \kappa_\infty \leq n\cdot \kappa_2 \end{equation}

Still no clue on an improved upper bound, though.

1

There are 1 best solutions below

2
On BEST ANSWER

About $\kappa_\infty(A) \leq n\cdot \kappa_2(A)$.

i) For the symmetric matrices $A$, you cannot do better than the factor $n$, at least for $n = 2,4$ as show these examples

enter image description here

ii) On the contrary for the $>0$ symm. matrices, the best bound is less than $n$.

In particular, the bound, for $n=2$, is $\dfrac{1}{12-8\sqrt{2}}\approx 1.4571$. This bound is not reached by a $>0$ matrix but is the limit associated to the sequence

$A_k=\begin{pmatrix}1&1-\sqrt{2}\\1-\sqrt{2}&3-2\sqrt{2}\end{pmatrix}+\dfrac{1}{k}I_2$ when $k\rightarrow +\infty$.

EDIT. About the case when $A=[a_{i,j}]$ is $>0$ symmetric and satisfies the supplementary conditions $a_{i,j}\geq 0$.

i) When $n=2$, the bound does not change; cf the matrix $\begin{pmatrix}1&\sqrt{2}-1\\\sqrt{2}-1&3-2\sqrt{2}\end{pmatrix}$.

ii) Since the $>0$ symm. matrices are dense in the closed set of $\geq 0$ symm. matrices, your original problem is equivalent to the following one. Find

$\max_{A\geq 0,||A||=1} \dfrac{||A||_{\infty}||Adjoint(A)||_{\infty}}{||A||_{2}||Adjoint(A)||_{2}}$, where $||.||$ is some norm.

When $n\geq 3$, the problem is much more difficult than when $n=2$. According to computational tests, we can guess

$\textbf{Conjecture.}$ The above $\max$ is reached for some $\geq 0$ matrix $A$ s.t. $\det(A)=0$. Moreover, amongst these matrices, there is at least one with $\geq 0$ entries (that is, it seems that the bound does not change).

For $n=3$, the bound seems to be close to $1.852$.