Consider a regular matrix $A \in \mathbb{R}^{n \times n}$. The normal $\infty$-norm of $A$ is given by
$$ \|A\|_{\infty} = \max_{\|x\|_{\infty} = 1} \|Ax\|_{\infty} = \max_{i \in [n]} \sum_{j \in [n]} |a_{i,j}|, $$
where the vector $x$ achieving the maximum in the second part of the formula has entries of $\pm 1$ depending on the the sign of the entries in the row achieving the maximum. $\|A\|_{\infty}$ is obviously fairly easy to compute based on the last part of the formula.
I am however instead interested in the value of $\|A^{-1}\|_{\infty}$. One way to compute the norm would be to invert the matrix and compute the norm as above. This is of course computationally challenging and tells me little about the dependency of the norm on the coefficients $a_{i,j}$. I am looking for a simpler approach, preferable a closed formula. It holds that
$$ \|A^{-1}\|_{\infty} = \left( \min_{\|x\|_{\infty} = 1} \|Ax\|_{\infty} \right)^{-1}, $$
Intuitively, this formula revolves around a normalized vector $x$ such that the positive and negative entries in each row $i$ to approximately cancel each other out when weighted with $x$, ensuring that $\sum_{j \in [n]} a_{i,j} x_j$ has small absolute values for all rows $i$. My questions are:
- Is there a "simple" formula to compute the norm of the inverse in the spirit of the equation above (based on the $\min$ formulation or something different)?
- If not, can we find at least find a nontrivial upper bound on $\|A^{-1}\|_{\infty}$ based on the coefficients $a_{i,j}$?