Condition Numbers

Question

I'm working my way through a basic textbook on Numerical Linear Algebra, and one of the problems asks if the fact that an arbitrary invertible matrix $A \in \mathbb{R}^{m \times m}$ is perfectly conditioned in the 1-norm implies that it is perfectly conditioned in the $\infty$-norm. Formally:

cond$_{1}(A) = 1 \Longrightarrow \text{cond}_{\infty}(A) = 1$ ?

I can prove that this holds for symmetric matrices (i.e when $A = A^{T}$), but not for the general case. My intuition was to try to disprove this by contradiction, but I cannot think of/compute any non-symmetric matrix $B$ such that $det(B) \neq 0$ and $\text{cond}_{1}(B) = 1$. I've also been trying to come up with something utilizing $\text{cond}_{1}(A^{T}A)$, $\text{cond}_{1}(AA^{T})$, or $\text{cond}_{1}(A^{T})$, but so far have only succeeded in showing that the lower bound $1 \leq \text{cond}_{\infty}(A)$.

If anyone could offer any help with finding a suitable counterexample or give a hint on how to approach this, I would greatly appreciate it.

Answer 1

$$ B = \begin{pmatrix}0 & \sqrt{10} \\ -\sqrt{10} & 0 \end{pmatrix} $$

• $B$ is antisymmetric.
• $\det(B) = 10$.
• $\kappa_1(B) = \sqrt{10} \cdot \frac{1}{\sqrt{10}} = 1$.

This is the example you requested. It is not an example with $\kappa_\infty \neq 1$.

There is no example with $\kappa_\infty = 1$.

$||B||_1$ is the maximum absolute column sum of $B = \left( b_{ij} \right)_{i,j=1}^n$ and $||B||_\infty$ is the maximum absolute row sum of $B$. Then \begin{align*} ||B||_1 &= \max_{1 \leq j \leq n} \sum_{i=1}^n|b_{ij}| \\ ||B||_\infty &= \max_{1 \leq i \leq n} \sum_{j=1}^n|b_{ij}| \\ \end{align*} Observe that $||B^{-1}||_1$ is the quotient of the maximum absolute row sum of $B$ and the determinant of $B$. Observe that $||B^{-1}||_\infty$ is the quotient of the maximum absolute column sum of $B$ and the determinant of $B$. \begin{align*} ||B^{-1}||_1 &= \frac{1}{\det B} \max_{1 \leq i \leq n} \sum_{j=1}^n|b_{ij}| \\ ||B^{-1}||_\infty &= \frac{1}{\det B} \max_{1 \leq j \leq n} \sum_{i=1}^n|b_{ij}| \\ \end{align*}

Then \begin{align*} \kappa_1(B) &= ||B||_1 \, ||B^{-1}||_1 \\ &= \max_{1 \leq j \leq n} \sum_{i=1}^n|b_{ij}| \cdot \frac{1}{\det B} \max_{1 \leq i \leq n} \sum_{j=1}^n|b_{ij}| \\ &= \max_{1 \leq i \leq n} \sum_{j=1}^n|b_{ij}| \cdot \frac{1}{\det B} \max_{1 \leq j \leq n} \sum_{i=1}^n|b_{ij}| \\ &= ||B||_\infty \, ||B^{-1}||_\infty \\ &= \kappa_\infty(B) \text{.} \end{align*}

(Since you only ask for a hint, I won't explain why the formulas for the norms of the inverse matrices are correct.)