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

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

$$$$\frac{1}{\sqrt{n}}\|A\|_\infty \leq \|A\|_2 \leq \sqrt{n} \|A\|_\infty$$$$

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

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:

$$$$\kappa_2 \leq \kappa_\infty \leq n\cdot \kappa_2$$$$

Still no clue on an improved upper bound, though.

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

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$$.

• Thank you! This really helped me. Do you think that imposing the additional condition of all elements $A_{ij} \geq 0$ may allow a better upper bound? – jackphen May 30 '20 at 6:49
• Thanks for the bonus. See my edit. – user91684 Jun 3 '20 at 10:09