# Prove that the normal cone $N_{\text{gph}(f)}$ of the graph of the affine function $f$ has the given form.

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.

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.