1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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! $\endgroup$ – Michael Grant Feb 23 '15 at 22:49
  • $\begingroup$ Which norm do you mean? $\endgroup$ – Bernard Feb 23 '15 at 22:51
  • $\begingroup$ @Bernard I'm considering the operator norm. I will make that explicit in the question $\endgroup$ – sunspots Feb 23 '15 at 22:53
  • 1
    $\begingroup$ 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$. $\endgroup$ – user1551 Feb 23 '15 at 23:47
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}}\|.$ $\endgroup$ – Michael Grant Feb 23 '15 at 22:57
  • $\begingroup$ @MichaelGrant I could have sworn the original question had weak inequality, but now it is written as strict. Ok fair enough, now there is a gap I will try to fill. $\endgroup$ – user2566092 Feb 23 '15 at 22:58
  • 1
    $\begingroup$ @user2566092 the question should be less than or equal to and I will change it now. $\endgroup$ – sunspots Feb 23 '15 at 23:00
  • $\begingroup$ Then you are done! $\endgroup$ – Michael Grant Feb 23 '15 at 23:01

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.