# Spectral norm of symmetric matrices only with the diagonal, the first column, and the first row non-zero

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

• 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|\}$. – Algebraic Pavel May 9 '14 at 0:36
• @PavelJiranek Thanks for mentioning the theorem. However, I think it can be tighter only if $b_i's$ are relatively large. – S.B. May 9 '14 at 2:11

## 1 Answer

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.

• 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? – S.B. May 13 '14 at 19:38
• 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$. – S.B. May 13 '14 at 19:47
• @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. – user1551 May 13 '14 at 19:51