[proofplan]
We prove the formula by comparing the defining inequalities for the two normal cones. The inclusion $A^\top N_C(Ax) \subset N_{A^{-1}(C)}(x)$ follows directly by pulling back the normal inequality through $A$. For the reverse inclusion, a normal vector to $A^{-1}(C)$ first annihilates $\ker A$, hence lies in $\operatorname{Range}(A^\top)$; after representing it as $A^\top v_0$, the remaining task is to modify $v_0$ by an element of $\ker A^\top$ so that it becomes normal to $C$ at $Ax$. The relative-interior hypothesis is exactly the qualification condition that gives the normal-cone intersection formula for $C \cap A(\mathbb{R}^n)$.
[/proofplan]
[step:Record the basic geometry of the preimage]
Define the preimage set $D \subset \mathbb{R}^n$ by
\begin{align*}
D := A^{-1}(C) = \{z \in \mathbb{R}^n : Az \in C\}.
\end{align*}
Since $C$ is convex and $A$ is linear, $D$ is convex. Since $C$ is closed and $A$ is continuous, $D$ is closed. The relative-interior assumption implies that there exists $u \in A(\mathbb{R}^n) \cap C$, so $u = Ax_0$ for some $x_0 \in \mathbb{R}^n$, and therefore $x_0 \in D$. Hence $D$ is nonempty.
For a closed convex set $K \subset \mathbb{R}^d$ and a point $p \in K$, we use the normal-cone convention
\begin{align*}
N_K(p) := \{w \in \mathbb{R}^d : w \cdot (q - p) \le 0 \text{ for every } q \in K\}.
\end{align*}
All displayed equations in this proof are written without TeX row separators.
[/step]
[step:Pull normals to $C$ back through $A$]
Let $x \in D$ and let $v \in N_C(Ax)$. Define $y := A^\top v \in \mathbb{R}^n$. For every $z \in D$, we have $Az \in C$, so the defining inequality for $v \in N_C(Ax)$ gives
\begin{align*}
v \cdot (Az - Ax) \le 0.
\end{align*}
Using the transpose identity $A^\top v \cdot (z - x) = v \cdot A(z - x)$, this becomes
\begin{align*}
y \cdot (z - x) \le 0.
\end{align*}
Thus $y \in N_D(x)$, and therefore
\begin{align*}
A^\top N_C(Ax) \subset N_D(x).
\end{align*}
[guided]
Define $D := A^{-1}(C) = \{z \in \mathbb{R}^n : Az \in C\}$. For a closed convex set $K \subset \mathbb{R}^d$ and $p \in K$, the normal cone used here is
\begin{align*}
N_K(p) := \{w \in \mathbb{R}^d : w \cdot (q - p) \le 0 \text{ for every } q \in K\}.
\end{align*}
Fix $x \in D$ and start with a normal vector $v \in N_C(Ax)$. The goal is to show that its pullback $A^\top v$ satisfies the defining inequality for membership in $N_D(x)$.
By definition of $D$, every $z \in D$ satisfies $Az \in C$. Since $v$ is normal to $C$ at $Ax$, we have
\begin{align*}
v \cdot (Az - Ax) \le 0
\end{align*}
for every $z \in D$. The transpose map is precisely the device that rewrites this inequality on $\mathbb{R}^m$ as an inequality on $\mathbb{R}^n$: for every $z \in \mathbb{R}^n$,
\begin{align*}
(A^\top v) \cdot (z - x) = v \cdot A(z - x) = v \cdot (Az - Ax).
\end{align*}
Therefore
\begin{align*}
(A^\top v) \cdot (z - x) \le 0
\end{align*}
for every $z \in D$. This is exactly the definition of $A^\top v \in N_D(x)$. Hence every vector in $A^\top N_C(Ax)$ lies in $N_D(x)$.
[/guided]
[/step]
[step:Represent every normal to the preimage as the pullback of a normal to $C \cap A(\mathbb{R}^n)$]
Let $y \in N_D(x)$. Define the kernel of $A$ by
\begin{align*}
\ker A := \{h \in \mathbb{R}^n : Ah = 0\}.
\end{align*}
Define the range of $A^\top$ by
\begin{align*}
\operatorname{Range}(A^\top) := \{A^\top v : v \in \mathbb{R}^m\}.
\end{align*}
If $h \in \ker A$, then $A(x+h) = Ax \in C$ and $A(x-h) = Ax \in C$, so $x+h \in D$ and $x-h \in D$. Applying the normal inequality to these two points gives
\begin{align*}
y \cdot h \le 0
\end{align*}
and
\begin{align*}
-y \cdot h \le 0.
\end{align*}
Hence $y \cdot h = 0$ for every $h \in \ker A$, so
\begin{align*}
y \in (\ker A)^\perp = \operatorname{Range}(A^\top).
\end{align*}
Choose $v_0 \in \mathbb{R}^m$ such that
\begin{align*}
A^\top v_0 = y.
\end{align*}
Let $L := A(\mathbb{R}^n) \subset \mathbb{R}^m$. For every $w \in C \cap L$, choose $z \in \mathbb{R}^n$ such that $Az = w$. Then $z \in D$, and therefore
\begin{align*}
v_0 \cdot (w - Ax) = v_0 \cdot (Az - Ax) = A^\top v_0 \cdot (z - x) = y \cdot (z - x) \le 0.
\end{align*}
Thus
\begin{align*}
v_0 \in N_{C \cap L}(Ax).
\end{align*}
[/step]
[step:Use the relative-interior qualification to split the intersection normal]
We need the following finite-dimensional normal-cone intersection formula.
[claim:Normal cone to a qualified intersection with a subspace]
Let $E \subset \mathbb{R}^m$ be closed and convex, let $M \subset \mathbb{R}^m$ be a linear subspace, and suppose
\begin{align*}
\operatorname{ri}(E) \cap \operatorname{ri}(M) \ne \varnothing.
\end{align*}
Then for every $p \in E \cap M$,
\begin{align*}
N_{E \cap M}(p) = N_E(p) + N_M(p).
\end{align*}
[/claim]
[proof]
The inclusion $N_E(p)+N_M(p) \subset N_{E \cap M}(p)$ follows by adding the defining inequalities for $E$ and $M$: if $a \in N_E(p)$ and $b \in N_M(p)$, then for every $q \in E \cap M$,
\begin{align*}
(a+b) \cdot (q-p) = a \cdot (q-p) + b \cdot (q-p) \le 0.
\end{align*}
Thus $a+b \in N_{E \cap M}(p)$.
For the reverse inclusion, we use the finite-dimensional normal-cone intersection rule under the relative-interior qualification: for closed convex sets whose relative interiors intersect, the normal cone to the intersection is the Minkowski sum of the normal cones. The hypotheses of that rule are satisfied here because $E$ is closed and convex, $M$ is a closed convex set as a linear subspace of $\mathbb{R}^m$, and the assumed qualification gives $\operatorname{ri}(E) \cap \operatorname{ri}(M) \ne \varnothing$. Therefore, for every $r \in N_{E \cap M}(p)$, there exist $a \in N_E(p)$ and $b \in N_M(p)$ such that
\begin{align*}
r = a+b.
\end{align*}
This proves $N_{E \cap M}(p) \subset N_E(p)+N_M(p)$, and hence the claimed equality.
[/proof]
Here $L := A(\mathbb{R}^n) \subset \mathbb{R}^m$ is a linear subspace, so $\operatorname{ri}(L)=L$. The assumed condition gives
\begin{align*}
\operatorname{ri}(C) \cap \operatorname{ri}(L) \ne \varnothing.
\end{align*}
Applying the claim with $E := C$, $M := L$, and $p := Ax \in C \cap L$, and using $v_0 \in N_{C \cap L}(Ax)$, there exist $v \in N_C(Ax)$ and $q \in N_L(Ax)$ such that
\begin{align*}
v_0 = v + q.
\end{align*}
Since $L$ is a linear subspace and $Ax \in L$,
\begin{align*}
N_L(Ax) = L^\perp.
\end{align*}
Because $L = A(\mathbb{R}^n)$, we have
\begin{align*}
L^\perp = \ker A^\top.
\end{align*}
Hence $q \in \ker A^\top$, and therefore
\begin{align*}
y = A^\top v_0 = A^\top(v+q) = A^\top v.
\end{align*}
Since $v \in N_C(Ax)$, this proves
\begin{align*}
y \in A^\top N_C(Ax).
\end{align*}
[/step]
[step:Combine the two inclusions]
The second step proved
\begin{align*}
A^\top N_C(Ax) \subset N_D(x),
\end{align*}
and the preceding two steps proved
\begin{align*}
N_D(x) \subset A^\top N_C(Ax).
\end{align*}
Since $D = A^{-1}(C)$, we conclude that for every $x \in A^{-1}(C)$,
\begin{align*}
N_{A^{-1}(C)}(x) = A^\top N_C(Ax).
\end{align*}
This is the desired normal-cone formula.
[/step]
