This should be a comment but I haven't got enough rep, sorry. I don't know how you want to apply the result. So, I'm wondering whether a linear polynomial whose coefficients are $m\times n$ and $n \times m$ matrices would be sufficient for your application. This can be easily achieved by using elementary matrices in order to extract $X$'s entries. 

EDIT for elaboration
--

Let $E_{ij}=E_{ij}^{(n)}$ denote the $n\times n$ matrix that has got zero entries everywhere except for the i-th row and j-th column, i.e. $ \left( E_{ij} \right)_{kl}= \delta _{ik} \delta _{jl} $ .

 Then $ E_{ii}\cdot X \cdot E_{jj} $ equals $x_{ij}E_{ij}$.

Well, the embedding 
'$$\iota : M(n,R) \to M(m,R) \quad ; \quad M \mapsto \begin{pmatrix} M & 0 \\ 0 & 0 \end{pmatrix}$$'
 can be described by the matrix $J=(I_n \ 0_{m-n})$, i.e. $\iota(M)=J^t\cdot  M\cdot J$.

Let me just steal the next definition from wikipedia http://en.wikipedia.org/wiki/Elementary_matrices

$$T_{i,j} = \begin{bmatrix} 1 & & & & & & & \\ & \ddots & & & & & & \\ & & 0 & & 1 & & \\ & & & \ddots & & & & \\ & & 1 & & 0 & & \\ & & & & & & \ddots & \\ & & & & & & & 1\end{bmatrix}$$

So ''T<sub>ij</sub>⋅A'' is the matrix produced by exchanging row ''i'' and row ''j'' of ''A''.

Suppose $ y_{kl} = \sum_{ij} z_{kl}^{ij} \cdot x_{ij} $ where $z_{kl}^{ij}$ lies in $\mathbb Z$ then

$$Y=\sum_{ijkl} z_{kl}^{ij} \cdot T_{ik}^{(m)} \cdot J^t \cdot E_{ii}^{(n)} \cdot X \cdot E_{jj}^{(n)} \cdot J \cdot T_{jl}^{(m)} . $$

Or, as I just realized we can permuatate

$$Y=\sum_{ijkl} z_{kl}^{ij} \cdot T_{ik}^{(m)} \cdot E_{ii}^{(m)}\cdot J^t\cdot  X\cdot J \cdot E_{jj}^{(m)} \cdot T_{jl}^{(m)} . $$

But both formulas give the exact same shortened version

$$ Y = \sum_{ijkl} A_{kl}^{ij} \cdot X \cdot B_{l}^{ij} $$

where $B_{kl}^{ij}$ is independent of $k$.