Elliptic Curve Isogenies, Frobenius endomorphism relation to characteristic equation In Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i) states:

Let $\mathbb{E}$ be an elliptic curve over $\mathbb{F}_p$. Suppose that its $j$-invariant is not supersingular and that $j\neq 0 $ or $1728$.
Then the modular polynomial $\Phi_l(j,T)$ has a zero  $\tilde{\jmath} \in \mathbb{F}_{p^r}$ if and only if the kernel $C$ of the corresponding isogeny $E \mapsto E/C$ is a one-dimensional eigenspace of $\phi^r_p$ in $E[l]$, with $\phi_p$ the Frobenius endomorphism of $E$.

From the proof:

If $\Phi_l(j,\tilde{\jmath} )=0$, then there exists a cyclic subgroup $C$ of $E[l]$ such that the $j$ invariant of $E/C$ is equal to $\tilde{\jmath}\in \mathbb{F}_{p^r} $. Let $E^1$ be an elliptic curve over $\mathbb{F}_{p^r}$ with $j$ invariant equal to $\tilde{\jmath}$. Let $E/C \mapsto E^1$ be an $\bar{\mathbb{F}}_p$ isomorphism and let $f: E \mapsto E/C \mapsto E^1$ be the composite isogeny. It has kernel $C$.

I can see $f$ is defined over $\mathbb{F}_{p^r}$, so this implies existence of an isogeny $E \mapsto E^1$ over $\mathbb{F}_{p^r}$.

How does this imply that $C$ is an eigenspace of $\phi^r_p$?

How does the statement &quot;The Frobenius endomorphism over $\mathbb{F}_{p^r}$ satisfies the same characteristic equation&quot; imply that $C$ is an eigenspace of $\phi^r_p$?


Please help me to understand this.
I have struggled with this proof, but here is how I tried to reason through it:

The Frobenius endomorphism can be represented by a $2 \times 2$ matrix over the torsion group $\mathbb{E}[\ell]$.  You may as well raise $\phi$ to some $r$ power, $\phi_q^r$, and get an eigenvalue equation for this matrix.

You get a subgroup $C$ of $\mathbb{E}[\ell]$ such that $\phi_q^r (P) = \kappa P$ if the characteristic equation has a root $\kappa$. From Vélu's formulas, we can build an isogeny from $\mathbb{E}$ to another elliptic curve $\mathbb{E}'$ such that the kernel of the isogeny is $C$. The Frobenius endomorphism only permutes the points in $C$, leaving the $j$-invariant of $\mathbb{E}'$, well...invariant. 

So the $\phi_q^r$ define a subgroup / eigenspace that can, via Vélu, generate an isogeny where it's the kernel.



More discussion:


Are you familiar with Vélu's formulas? They may be the missing link for you. Basically: assume you have an elliptic curve $\mathbb{E}$ over some field $\bar{K}$, and let $C$ be a finite subgroup of  $\mathbb{E}(\bar{K})$. Then, Vélu tells you that there is another group $\mathbb{E}'$ and an isogeny $\chi:  \mathbb{E} \rightarrow \mathbb{E}'$ such that $C = \text{Ker}(\chi)$. They even explicitly give you a formula for the isogeny!
A homomorphism from  $\mathbb{E}[\ell] \rightarrow  \mathbb{E}[\ell]$ is represented as a $2 \times 2$ matrix (the points of $\mathbb{E}[\ell]$ are "$\ell$-torsion points") (page 233)
If the number points on a curve satisifies $ \#\mathbb{E}(\mathbb{F}_p) = p + 1 - a$, then the Frobenius endomorphism $\phi_q$ satisfies $\phi_q^2 - a \phi_q + q = 0$ (page 234).


So, the Frobenius endomorphism acting on the $\ell$-torsion, $\phi_{q;\ell}$ can be represented as a matrix:

$$ \phi_{q;\ell} = \begin{pmatrix}
\lambda &amp; b \\
0 &amp; \mu \\
\end{pmatrix}$$

Its characteristic polynomial is 

$$ \begin{vmatrix}
\lambda - T &amp; b \\
0 &amp; \mu - T \\
\end{vmatrix} = (T-\mu)(T-\lambda) \equiv 0 \bmod \ell$$

So a root $\lambda$ here satisfies a subgroup of $\mathbb{E}[\ell]$, $C$, such that for all the points in $C$, $\phi(P) = \lambda P$. Raising $\phi_q$ to some $r$ power will just give you another eigenvalue equation, say $\phi_q^r(P) = \kappa P$. From Velu's formulas, we can define an isogeny such that $C$ is the kernel of the isogeny, and $\phi_q^r$ just permutes all the coordinates of points in $C$, leaving the parameters of the equation for $\mathbb{E}'$ alone. That means the $j$-invariant of $\mathbb{E}'$ is left alone too.