let's say $M_{n\times n}$ is a matrix, I know the following theorem:
if $Mx+d=x$ has a unique solution ($x^*$) then we have: the sequence $x_0,f(x_0),f(f(x_0)),\dots$ is convergent to $x^*$ for all $x_0$ if and only if the spectral radius of M is less than $1$
if $f(x) = Mx+d$ is a contraction under the euclidean distance then that means (if we take $y$ to be zero) $\| Mx+d -M0-d\|=\|Mx\|<\|x\|$, which means $\frac{\|Mx\|}{\|x\|}<1$, therefore the spectral radius also has to be less than one.
what I want to know is the relationship between the spectral radius and the lipschitz constant(using euclidean distance). if the spectral radius is less than $1$ can I claim $f(x)$ is a contraction? can I also claim that spectral radius is the smallest possible lipschitz constant?
I know if eigenvectors of M ($v_1,\dots,v_n$) make a basis for $\mathbb{R}^n$ and $\{\lambda_1,\dots,\lambda_n\}$ are its eigenvalues which I assume to be positive, then:
$(|\lambda^*|=max\{|\lambda_1|,\dots,|\lambda_n|\})$
$$\|Mx+d-My-d\|=\|M(x-y)\|=\|M(\alpha_1v_1+\dots+\alpha_nv_n)\|\\=\|\lambda_1\alpha_1v_1+\dots+\lambda_n
\alpha_nv_n\|\le|\lambda^*|\|x-y\|$$
so $f(x)$ has to be a contraction as $|\lambda^*|<1$. is this proof correct? what if the eigenvectors don't make a basis or the eigenvalues aren't positive?
Best Answer
To summarize the discussion so far: The theorem is true, if $\rho(M)<1$ then the sequence converges to the fixed point.
The smallest Lipschitz constant of $f$ in the euclidean norm is the induced operator norm of $M$ is the largest singular value $\sigma_1(M)=\sqrt{\rho(M^TM)}$. As you maybe hinted at, the spectral radius is smaller than any operator norm.
Other vector norms exist, some can be constructed as $\|x\|=\|Ax\|_2$ or $\|x\|=\|Ax\|_\infty$. In the latter case $A$ can have a very high number of rows and its unit ball can approximate any point-symmetric convex shape arbitrarily closely.
Varying over all possible vector norms, it turns out that the spectral radius is the largest lower bound, even if it is not always itself contained in that set, example $M=\pmatrix{0&1\\0&0}$. As all vector norms in finite dimension are equivalent, it is sufficient to have one induced operator norm to be smaller than $1$ to get convergence.
The example shows that the euclidean norm is not always optimal, as with $M^TM=\pmatrix{0&0\\0&1}$ the largest singular value is $1$, while the spectral radius is $0$.
Another approximation theorem states that independent of the vector norm chosen, $$\lim_{n\to\infty}\sqrt[n]{\|M^n\|_{op}}=\rho(M).$$ So even with fixing the euclidean norm one can find an $n$ so that $f^n(x)$ has a Lipschitz constant smaller than $1$. It is a standard argument that under uniqueness the fixed point of $f^n$ is also the unique fixed point of $f$.