[Math] Proving a norm is lipschitz

continuitylinear algebralipschitz-functionsnormed-spaces

Let $M\in\mathbb{R}^{n\times n}$. Define the function $f\colon\mathbb{R}^n\to\mathbb{R}$ by $f(x)=\Vert Mx\Vert$. Show that $f$ is Lipschitz.


Let $x,y\in\mathbb{R}^n$, then we want to find a $L>0$ such that

$$\Vert f(x)-f(y)\Vert \le L\Vert x-y\Vert$$


We have

\begin{align}
\Vert f(x)-f(y)\Vert &= \big\Vert \Vert Mx\Vert-\Vert My\Vert\big\Vert\\
&\le \Vert Mx- My\Vert&\text{reverse triangle ineq.}\\
&\le \Vert M\Vert\Vert x-y\Vert\\
\end{align}

Taking $L=\Vert M\Vert$ we find $f$ is Lipschitz.


I have a few questions here, some related to Lipschitz continuity and others related to norms.

  • Firstly, is this working correct?

  • I notice that we take $L=\Vert M\Vert$ but could we take anything greater than our chosen $L$, in other words, is the Lipschitz constant unique?

  • On a side note, is $\Vert \Vert Mx\Vert \Vert=\Vert Mx\Vert$? In general can we say that $\Vert\Vert a\Vert\Vert = \Vert a\Vert$?

Best Answer

1) A conditional yes. Your proof of the Lipschitz continuity of $f$ is correct, provided you play it completely safe by stating specifically that the matrix norm is induced by the vector norm, i.e. \begin{equation} \|M\| = \sup \{ \|Mx\| \: : \: \|x\| \leq 1 \} \end{equation} and that $\|z\|$ is merely the absolute value of $z$ when $z \in \mathbb{R}$.

2) Yes, any value larger than $L$ would also serve as a Lipschitz constant for $f$. But $L=\|M\|$ is the smallest value which will work. Simply pick $x \in \mathbb{R}^n$ such that $\|Mx\| = \|M\|$, $\|x\| = 1$ and $y = 0$.

3) It depends! $Mx \in \mathbb{R}^n$ whereas $\|Mx\| \in \mathbb{R}$, so you are overloading the notation for $\|\cdot\|$. Refer to the remark I made for point 1).

Related Question