Lowest upper bound on matrix norm

matricesmatrix-normsspectral-normupper-lower-bounds

Let $A \in \mathbb{R}^{d \times d}$ be an invertible real matrix and $A'$ the matrix obtained from $A$ by setting all diagonal elements to $0$, namely
$$A'_{ij} = \begin{cases} A_{ij} & \text{if } i \neq j \\
0 & \text{otherwise.}
\end{cases}$$
I can prove that $\lVert A' \rVert_2 \leq \min(2, \sqrt{d})\lVert A \rVert_2$ where $\lVert \cdot \rVert_2$ is the $2$-norm (operator norm), but I don't think the bound is tight. I ran $20$ million samples with entries of $A$ generated both uniformly across integers from $-10$ to $10$ and from a standard normal distribution, and got
$$\lVert A' \rVert_2 \leq \begin{cases} \lVert A \rVert_2 & \text{for } d=2 \\
\approx 1.29 \lVert A \rVert_2 & \text{for } d=3 \\
\approx 1.339 \lVert A \rVert_2 & \text{for } d=4 \\
\approx 1.346 \lVert A \rVert_2 & \text{for } d=5 \\
\approx 1.28 \lVert A \rVert_2 & \text{for } d=6.
\end{cases} $$
Any ideas on what the lowest upper bound would be as a function of $d$?

Best Answer

We consider the results for $d=3,4,5$. The bounds $k_d$ are (at least, I think so)

$k_3=4/3,k_4=3/2,k_5=1.6$ and are reached for

enter image description here

The matrices $A_d$ are symmetric and $spectrum(A_d)=\{1,\cdots,1,-1\}$. Moreover, the entries of $A_d$ are fractions in $]-1,1[$ with denominators $d$.

I did not look for a proof, but I did your job. That is important

  1. It's not the value of the bound, but the form of the matrices that perform the best during the random tests.

  2. To have a minimum of intuition (or experience); after random tests, we feel that the matrices are not very far from being symmetrical and not very far from having eigenvalues ​​with same modulus. Then we randomly test these special matrices and we approach the correct bound much faster...

EDIT. Using the above results, we can formulate

$\textbf{Conjecture}$. Let $U$ be the $n\times n$ matrix of ones. For each $n$, the considered bound is reached for $A=I_n-\dfrac{2}{n}U$, that is $B=\dfrac{2}{n}(I_n-U)$.

It is easy to see that $||A||_2=1,||B||_2=2\dfrac{n-1}{n}$.

Related Question