# Condition number of a tridiagonal Toeplitz matrix is independent of the size

If we have the tridiagonal matrix

$$A = \begin{bmatrix} 4 & 1 & & & \\ 1 & 4 & 1 & & \\ & \ddots & \ddots & \ddots & \\ & & 1 & 4 & 1\end{bmatrix}$$

then no matter the size of $$A$$, its condition number, using the infinity norm, is $$\kappa (A) = 3$$. Is this correct? If so, why does this happen? Why doesn't the condition number change?

• By "infinity norm", do you mean $\max\{|A_{kj}|:\ k,j\}$? The condition number is usually calculated for an operator norm, as far as I can tell. Nov 24, 2013 at 16:57
• I mean this: $\left \| A \right \|_{oo}=max_{1\leq i\leq n }\sum_{j=1}^{n} \left | a_{ij} \right |$ Nov 24, 2013 at 17:12
• @evinda: I see you haven't accepted any answers to any of the questions you've asked. It might encourage people to help you if you do so. Take a look here. Nov 28, 2013 at 18:12

As Evinda stated, $$\|A\|_\infty := \sup\{\|Ax\|_\infty : \|x\|_\infty \le 1 \} = \max_{1\le i\le n} \sum_{j=1}^n |A_{ij}| .$$
I think I can show that $K_\infty(A) \le 3$. Clearly $\|A\|_\infty = 6$. Now write $A = 4 (I + B)$, where $B$ has diagonal entries equal to $0$ and the upper and lower diagonal entries equal to $\frac14$. So $\|B\|_\infty = \frac12 < 1$. Hence we can compute $A^{-1}$ using the geometric series $$A^{-1} = \frac14 \sum_{k=0}^\infty (-1)^k B^k$$ and hence $$\|A^{-1}\|_\infty \le \frac14 \sum_{k=0}^\infty \|B\|_\infty^k = \frac14 \cdot \frac1{1-\frac12} = \frac12 .$$ Therefore the condition number of $A$ is less than or equal to $6 \times \frac12 = 3$.
Next, I did some numerical experiments using Mathematica and 50 digit arithmetic. The condition number at $n=100$ is not exactly $3$, rather it is roughly $2.9999999999999999999999999999038729245836257932320$. My guess is that as a function of $n$ it converges monotonically to $3$. Matlab would get $3$ as its answer because it uses IEEE double precision which is only about 17 digits of accuracy.
• I think it is rather amazing that the geometric series upper bound gives such a sharp answer. Either I made a mistake (but I think the proof will still show $K_\infty(A)$ is uniformly bounded), or some amazing coincidences are going on. Nov 24, 2013 at 19:49