Matrix-vector norm inequalities in tridiagonal matrix

Question

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?

Answer 1

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.

Answer 2

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?