# Matrix-vector norm inequalities in tridiagonal matrix

Let's consider the linear system $$A\vec{x}=\vec{b}$$, with $$A$$ being a diagonally dominant by columns and tridiagonal matrix, that is:

$$A=\begin{pmatrix} d_1&& c_2 && && && \\ a_1&& d_2 && c_3 && && \\ && \ddots && \ddots && \ddots && \\ && && a_{n-2}&& d_{n-1}&& c_{n}\\ && && && a_{n-1}&& d_n \end{pmatrix}$$

with $$a_n=c_1=0$$. Prove that $$K\|\vec{x}\|_{\infty} \leq \|\vec{b}\|_{\infty}$$ is satisfied, where $$K = \min\limits_{1 \leq i \leq n} \left\{|d_i|-|a_i|-|c_i| \right\}$$

I've tried using the property $$\|\vec{b}\|_{\infty} = \|A\vec{x}\|_{\infty} \leq \|A\|_{\infty} \|\vec{x}\|_{\infty}$$ but I don't get anywhere near the answer. Any suggestions?

I've been thinking about the problem and I got here:

Let's consider $$K||x||_{\infty}\leq ||b||_{\infty}=||Ax||_{\infty}\leq||A||_{\infty}·||x||_{\infty}$$ Simplifying, it results in: $$K\leq||A||_{\infty}$$ or $$1\leq \dfrac{||A||_{\infty}}{K}$$ Given that $$||A||_{\infty}=\text{max}_{i\leq j \leq n}\sum_{j=1}^n|a_{ij}|=|d_j|+|a_j|+|c_j|$$ for some $$j\in\mathbb{N}$$ and that $$K = \min\limits_{1 \leq i \leq n} \left\{|d_i|-|a_i|-|c_i| \right\}=|d_i|-|a_i|-|c_i|$$ for some $$i\in\mathbb{N}$$

We can rewrite the third inequality as $$1\leq\dfrac{|d_j|+|a_j|+|c_j|}{|d_i|-|a_i|-|c_i|}$$ We know that because A is a tridiagonal matrix that $$|d_i|\geq |a_i|+|c_i|$$ for all $$i\in\mathbb{N}$$

That is $$|d_i|-|a_i|-|c_i|\geq 0$$

Then we have two possibilities $$i=j$$ or $$i\neq j$$

If $$i=j$$ then $$|d_j|+|a_j|+|c_j|\geq |d_j|-|a_j|-|c_j|$$

Now, $$K$$ is defined as the minimum of the difference of $$|d_i|-|a_i|-|c_i|$$ so it follows that if $$i\neq j$$ then $$|d_j|+|a_j|+|c_j|\geq |d_i|-|a_i|-|c_i|$$.

So we have proven that $$1\leq \dfrac{||A||_{\infty}}{K}$$ and thus the first statement.

Is this solution correct?

• That looks fine to me.
– KBS
Commented May 29, 2022 at 15:55
• Your expression for $\Vert A\Vert_{\infty}$ is incorrect. That's actually $\Vert A\Vert_1$. As I said in my answer, I think the statement is incorrect. I managed to prove it but for $A^\top \vec{x}=\vec{b}$. Commented May 29, 2022 at 17:11
• I see, the correct version would be ∥A∥∞=d_i+c_{i+1}+a_{i−1}?
– user879314
Commented May 29, 2022 at 18:13
• Correct. ====== Commented May 29, 2022 at 20:02
• Also, there's a small oversight: the statement "We know that because A is a tridiagonal matrix that" should be "We know that because A is diagonally dominant by columns that". Commented May 29, 2022 at 20:05

I think there's something wrong in the description. As it is, the statement is false and a counter example is provided by $$A=\begin{pmatrix}1 & 2 & 0\\ 0 & 3 & 0\\ 0 & 0 & 1\end{pmatrix}, \quad \vec{x} = \begin{pmatrix}2\\ -\frac12\\ 0 \end{pmatrix},$$ which gives $$K=1$$, $$\Vert\vec{x}\Vert_{\infty} = 2$$ and $$\Vert\vec{b}\Vert_{\infty} = \frac32$$.

Conversely, if one considers $$A^{\top}\vec{x}=\vec{b}$$, then one can prove the inequality as follows. If $$K=0$$, the inequality is trivially satisfied. We can therefore assume $$K>0$$ in the following, which means that $$A^\top$$ is strictly diagonally dominant (by row) and therefore invertible [1]. Hence we can write $$\Vert\vec{x}\Vert_{\infty} = \Vert A^{-\top}\vec{b}\Vert_{\infty} \le \Vert A^{-\top}\Vert_{\infty} \, \Vert\vec{b}\Vert_{\infty},$$ where the inequality follows from the standard property of matrix norms induced by vector norms [2]. We then use Theorem 1 in [3], which states: "Assume $$A$$ is diagonally dominant by rows and set $$\alpha = \min_k(\vert a_{kk} \vert - \sum_{j\neq k} \vert a_{kj} \vert)$$. Then $$\Vert A^{-1}\Vert_{\infty}<1/\alpha$$" (note: they must have a typo because the inequality is actually not strict). We apply their theorem to our $$A^\top$$ and obtain that $$\Vert A^{-\top}\Vert_{\infty} \le 1/K.$$ This gives $$\Vert\vec{x}\Vert_{\infty} \le \frac1K \Vert\vec{b}\Vert_{\infty}.$$ Rearranging proves the (modified, i.e. for $$A^\top$$ rather than $$A$$) statement of the question.

• Is A a tridiagonal matrix? For it to be it must have non zero values in the main diagonal and in the 2 subdiagonals over and under it. I think this does not fulfill the requirements of the exercise.
– user879314
Commented May 29, 2022 at 12:09
• It is tridiagonal. There's no requirement for the main diagonal and two subdiagonals to be nonzero. For example a diagonal matrix is also tridiagonal (as well as upper and lower triangular, although the strictly triangular parts are zero). Anyway, even with your more restrictive definition, you can take my example and set elements (2,1), (2,3) and (3,2) to 0.001 and see that the claim is still false. Commented May 29, 2022 at 17:02