GIVEN
Let $f : \mathbb{R}^n \longrightarrow \mathbb{R}^m$ be the affine function defined by $f(x) = Mx + b$ where $M$ is an $m \times n$ matrix and $b$ is a vector in $\mathbb{R}^m$. Prove that for $(x_0,y_0) \in \text{gph}(f)$:
$$
N_{\text{gph}(f)}(x_0,y_0)=\big\{ (u,v)\in\mathbb{R}^n \times \mathbb{R}^m:u+M^Tv=0 \big\}.
$$
USEFUL DEFINITION
Normal Cone
The normal cone of a nonempty, closed, and convex set $K$ at a point $x_0 \in K$ is:
$$
N_K(x_0)=\big\{ z:\langle z, \;x-x_0 \rangle \leq 0,\; \forall x \in K\big\}
$$
ATTEMPT
By applying the above definitions I was able to reach
$$
\langle u + M^Tv , \; x – x_0\rangle \leq 0
$$
I am not sure how to prove that $u + M^Tv = 0$.
One thing that might help: the subdifferential of $f$ is $\partial f = \{ \nabla f \} = \{ M^T \}$.
Any help is greatly appreciated.
Best Answer
You are on a good way towards proving $u+M^\top v=0$.
If you have $$ \langle u+M^\top v,\;x-x_0\rangle \leq 0 $$ for all $x\in\mathbb R^n$, then (by substituting $x$ with $x+x_0$) it follows that $$ \langle u+M^\top v,\;x\rangle \leq 0 $$ for all $x\in\mathbb R^n$. By substituting $x$ with $-x$, we get $$ \langle u+M^\top v,\;x\rangle =0 $$ for all $x\in\mathbb R^n$. This implies (by linear algebra) that $u+M^\top v=0$.
This would complete the "$\subset$" part of the proof.
The other "$\supset$" part is easier in my opinion, so you should give it a try.