Ax = b using Banach fixed-point theorem

Question

Let $A\in \mathbb{R} ^{n, n}$ be a matrix with $\sup _{j\in \left\{ 1,\ldots ,n\right\} } \sum ^{n}_{i=1}\left| \delta _{ij}-a_{ij}\right| <1 $, where $\delta _{ij}$ are the entrys of the identity matrix and $a_{ij}$ are the entrys of $A$.
Let $\mathbb{R} ^{n}$ be equipped with the norm $||\cdot || _{1}$.

I want to show, using the Banach fixed-point theorem, that for every $b\in \mathbb{R} ^{n}$ there is exactly one $x\in \mathbb{R} ^{n}$ with $Ax=b$.
How can i do that?

Answer 1

You want to convert your equation into a fixed point problem. One simple way to do so is to rewrite the equation $$ Ax = b $$ as $$ (I - A)x + b = x $$

Exercise check that the two equations are equivalent

Now define the mapping $F(x) = (I-A)x + b$ as a mapping of the normed space $\mathbb{R}^n$ equipped with the $\ell_1$ norm to itself. You want to check that this is a contraction mapping.

By definition $$ F(x) - F(y) = (I-A)(x-y) $$ so $F$ being a contraction mapping is equivalent to the linear operator $$ I-A: \mathbb{R}^n \to \mathbb{R}^n$$ having the $\ell_1 \to \ell_1$ operator norm $< 1$.

Exercise Check that this indeed holds.