Under what condition is a linear mapping contractive in the sup-norm?

1.6k Views Asked by At

Let $T: \mathbb{R}^n \to \mathbb{R}^n$ be a linear mapping represented by the matrix $A \in \mathbb{R}^{n \times n}$

Then $T$ is said to be contractive in the sup-norm if for all $x,y$

$$\|Ax-Ay\|_\infty \leq l\|x-y\|_\infty$$ $l \in [0,1)$

Are there other sufficient condition that characterizes for when $T$ is contractive in the sup-norm? I am thinking along the line of $\|A\|_\infty < 1$ where $\|\cdot\|_\infty$ is the sup matrix norm. I would be glad if someone can provide a reference to these results

Can someone offer an example of such a linear map?

1

There are 1 best solutions below

4
On BEST ANSWER

Proof: (of your guess)

Note that $$ \|Ax-Ay\|_\infty \leq l\|x-y\|_\infty \quad \forall x,y \in \Bbb R^n \quad \iff\\ \|A(x-y)\|_\infty \leq l\|x-y\|_\infty \quad \forall x,y \in \Bbb R^n \quad \iff\\ \|Ax\|_\infty \leq l\|x\|_\infty \quad \forall x \in\Bbb R^n \quad \iff\\ \frac{\|Ax\|_\infty}{\|x\|_\infty} \leq l \quad \forall x \in\Bbb R^n \quad \iff\\ \sup\left\{ \frac{\|Ax\|_\infty}{\|x\|_\infty} : x \in \Bbb R^n, x \neq 0\right\}\leq l \quad \iff\\ \|A\|_\infty \leq l $$ where the last equivalence is merely an application of the definition of $\|A\|_\infty$.


As is explained in this wiki page, the $\infty$-norm can be nicely characterized by $$ \|A\|_\infty = \max_{1 \leq i \leq n}\sum_{j=1}^n |a_{ij}| $$ which is to say that the norm is simply the maximum absolute row-sum. So, in order to construct examples, it suffices to find vectors $(a_1,\dots,a_n)$ with $\sum |a_i|<1$, and make those the rows of your matrix.