# Bounding a Symmetric Matrix

Consider the following $n \times n$ matrix $A$, which has 1's on the superdiagonal and subdiagonal and 0's elsewhere, i.e.

$$\begin{pmatrix} 0 & 1 & 0 & \cdots & \cdots & \cdots & \cdots & 0\\ 1 & 0 & 1 & 0 & & & & \vdots\\ 0 & 1 & 0 & 1 & \ddots & & & \vdots\\ \vdots & 0 & \ddots & \ddots & \ddots & \ddots & & \vdots\\ \vdots & & \ddots & \ddots & \ddots & \ddots & 0 & \vdots\\ \vdots & & & \ddots & 1 & 0 & 1 & 0\\ \vdots & & & & 0 & 1 & 0 & 1\\ 0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 0\\ \end{pmatrix}$$

I want to show that the operator (spectral) norm of $A$ is bounded from above by $2$, namely $||A|| \leq 2$.

In trying to prove this statement I started by decomposing $A$ into a sum of two matrices $A_{\mbox{super}}$ and $A_{\mbox{sub}}$, where $A_{\mbox{super}}$ has 1's on the superdiagonal and 0's elsewhere. Similarly, I define $A_{\mbox{sub}}$to have 1's on the subdiagonal and 0's elsewhere. Thus, I write the norm of $A$ as

$$||A||= ||A_{\mbox{super}} + A_{\mbox{sub}}||$$

and then use the triangle equality to bound the norm from above, namely

$$||A_{\mbox{super}} + A_{\mbox{sub}}|| \leq ||A_{\mbox{super}}|| + ||A_{\mbox{sub}}||$$

It is at this point that I am unsure on how to proceed. My surmise would be to bound $A_{\mbox{super}}$ by 1 and similarly bound $A_{\mbox{sub}}$ by 1. But am not sure how this would work out.

• This is a Toeplitz tridiagonal matrix so its eigenvalues are known to be $$2\cos(k\pi/(n+1)) \quad k=1,2,\dots,n.$$ Its spectral norm is therefore $2\cos(\pi/(n+1))$. Now, that may not be an answer to your question, because you might need to prove this result instead! – Michael Grant Feb 23 '15 at 22:49
• Which norm do you mean? – Bernard Feb 23 '15 at 22:51
• @Bernard I'm considering the operator norm. I will make that explicit in the question – sunspots Feb 23 '15 at 22:53
• It's easier to prove the statement using Gershgorin disc theorem. To prove strict inequality, you may apply Perron-Frobenius theorem and consider $(1,\ldots,1)Av$ for the Perron vector $v$. – user1551 Feb 23 '15 at 23:47

If you are talking about basic standard matrix norm which is also equivalent to spectral norm, then just compute $A_{sub}^TA_{sub}$ and find the maximum absolute value eigenvalue of that, and take square root, which is equivalent to the basic standard matrix norm. You should find that the product matrix is all $1$ on the diagonal except for one zero, and everywhere else zero, so the maximum absolute value of eigenvalue is $1$ and you are done.
• You're not quite done, because that gives you a non-strict inequality. It remains to be proven that $\|A\|\neq 2\|A_{\text{sub}}\|.$ – Michael Grant Feb 23 '15 at 22:57