4
$\begingroup$

Consider a real symmetric matrix $$\mathbf{M}=\left[\array{a_0&a_1&a_2&\cdots&a_n\\ a_1&b_1&0&\cdots&0\\ a_2&0& b_2&\cdots&0\\ \vdots &\vdots &\vdots&\ddots&\vdots\\ a_n&0&0&\cdots&b_n}\right].$$ Deriving bounds -- probably loose ones -- for the spectral norm is not that difficult. I wonder if there an explicit formula that gives the spectral norm of $\mathbf{M}$ (i.e., $\left\|\mathbf{M}\right\|)$ in terms of $a_i$s and $b_i$s?

If necessary, $a_i$s and $b_i$s may assumed to be non-negative as well. Also, finding reasonably tight bounds would be fine.

Update: The simplest bound I can think of is $$\left\|\mathbf{M}\right\|\leq \max\{|a_0|,|b_1|,|b_2|,\dotsc,|b_n|\}+\sqrt{a_1^2+a_2^2+\dotso+a_n^2}.$$

$\endgroup$
  • 2
    $\begingroup$ Gershgorin theorem might give a tighter bound: $\|\mathbf{M}\|\leq\max\{|a_0|+\cdots+|a_n|,|a_1|+|b_1|,\ldots,|a_n|+|b_n|\}$. $\endgroup$ – Algebraic Pavel May 9 '14 at 0:36
  • $\begingroup$ @PavelJiranek Thanks for mentioning the theorem. However, I think it can be tighter only if $b_i's$ are relatively large. $\endgroup$ – S.B. May 9 '14 at 2:11
1
$\begingroup$

Let's perform a simulation experiment. We consider "the simplest bound" (denoted by $\rho_s$ below) the OP mentions, the bound arisen from Gershgorin's disc theorem (denoted by $\rho_g$ in the sequel; see the comment of Pavel Jiranek below the question body), and also the following bound which is obtained by considering the eigenvectors of $M$ (proof omitted): $$ \rho_e(M)=\max\left\{ \max_j|b_j|,\ \frac{-(a_0+b) + \sqrt{(a_0-b)^2 + 4A}}2, \ \frac{(a_0+B) + \sqrt{(a_0-B)^2 + 4A}}2\right\}, $$ where $b=\min_j b_j,\ B=\max_j b_j$ and $A=\sum_{j\ge1}a_j^2$.

To measure how sharp the upper bounds are, for each selected value of $n$, we generate, 100,000 random matrices with $a_i$s and $b_j$s lying between $-1$ and $1$. For each random matrix, we calculate the ratio $\rho(M)/\rho_s(M)$. The maximum and mean of the 100,000 instances are then taken and these statistics are also computed for $\rho(M)/\rho_g(M)$ and $\rho(M)/\rho_e(M)$. The greater these ratios, the sharper the bound. Here are the results. \begin{array}{c|ccc|ccc} &&\text{max. }\frac{\rho(M)}{\rho_?(M)}&&&\text{mean } \frac{\rho(M)}{\rho_?(M)}\\ n&\text{simplest}&\text{Gershgorin}&\text{eigenvector} &\text{simplest}&\text{Gershgorin}&\text{eigenvector}\\ \hline 2&0.9996&1.0000&1.0000&0.7837&0.8133&0.9311\\ 4&0.9923&0.9998&1.0000&0.7549&0.6603&0.9018\\ 8&0.9810&0.9389&0.9948&0.7654&0.4576&0.9009\\ 16&0.9527&0.4600&0.9795&0.7974&0.3152&0.9160\\ 32&0.9339&0.2803&0.9738&0.8355&0.2181&0.9342\\ 64&0.9339&0.1802&0.9742&0.8718&0.1516&0.9507 \end{array} From the above results, we see that while the bound from Gershgorin disc theorem performs fairly well for very small matrices ($n\le4$), its performance deteriorates very quickly when $n$ is getting large. In contrast, "the simplest bound" performs surprisingly well. It is worth notice that while the maximum ratio $\frac{\rho(M)}{\rho_s(M)}$ deterioriates slowly, the mean of $\frac{\rho(M)}{\rho_s(M)}$ actually increases with $n$. In other words, the average performance of $\rho_s$ is getting better and better for larger matrices. While it is interesting to see whether the performance of $\rho_s$ will surpass the performance of $\rho_e$ at some point, this simulation exercise is too time consuming and I will leave it to the readers to investigate.

$\endgroup$
  • $\begingroup$ Thank you very much for the time you spent on my problem. It is an insightful numerical result. I have a question regarding $\rho_e$. What's the approximation that leads to $\rho_e$ as an upper bound? $\endgroup$ – S.B. May 13 '14 at 19:38
  • $\begingroup$ Never mind! I think you derived the expression of $\rho_e$ using the norm compression bound, right? If that is correct, then you can show that $\rho_s$ will always be greater than $\rho_e$. $\endgroup$ – S.B. May 13 '14 at 19:47
  • 1
    $\begingroup$ @S.B. No, I use a very naive derivation. Let $(\lambda,x)$ be an eigenpair of $M$. If $x_0=0$, then $\lambda$ has to be some $b_j$. Hence the $\max_j|b_j|$ in the formula of $\rho_e$. If $x_0\ne0$ and $\lambda\ne b_j$ for every $j$, let $x_0=1$. The equation $Mx=\lambda x$ then implies that $a_0 + \sum_j a_j^2/(\lambda-b_j) = \lambda$. By replacing the $b_j$s in the denominators by $b$ or $B$, we can obtain bounds on $|\lambda|$ as roots of quadratic equations. I don't know how $\rho_s$ and $\rho_e$ compare. $\endgroup$ – user1551 May 13 '14 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.