Minimal realizations exist and are unique up to isomorphism

Let $V={\mathbb{C}}^n$ have basis $v_i$, and define $p_0:V\to {\mathbb{C}}^n$ by $p_0(v_i)=(a_{i1},\dots ,a_{in})$. Choose a complement $C$ of $\mathrm{im}{p}_0$ by finite elimination. On $H=V\oplus C$ put $p(v,c)=p_0(v)+c$, $h_i=(v_i,0)$ and ${\alpha }_j={\mathrm{pr}}_{j}p$. The map $p$ is onto, so its coordinate functionals are independent; the $h_i$ are independent and have the prescribed evaluations. Moreover $\dim H=n+(n-r)$.

In any realization with independent roots, $p:H\to {\mathbb{C}}^n$, $h\mapsto ({\alpha }_j(h){)}_j$, is onto. Its restriction to $V=\mathrm{span}(h_i)$ has rank $r$, so $\dim (H\mathrm{/}V)\ge n-r$. This proves the lower bound. At equality, $\ker p\subset V$, because $\dim \ker p=n-r=\dim \ker (p{\mathrm{\mid }}_V)$.

For two minimal realizations choose the same complement $C$ of the common row image in ${\mathbb{C}}^n$. Lift a basis of $C$ to each $H$ using surjectivity of $p$. The resulting linear sections $s:C\to H$ give $H=V\oplus s(C)$: an intersection vector has image both in $C$ and in the row image, hence zero; injectivity of $p$ on $s(C)$ then kills it. Dimensions give spanning. The map $h_i\mapsto h_i^{\mathrm{\prime }}$, $s(c)\mapsto s^{\mathrm{\prime }}(c)$ is invertible and commutes with $p$, so preserves every ${\alpha }_j$. All selections are finite Gaussian elimination.