Let $R = \mathbb{Z}[x_{1}, \dots, x_{r}]$. Let $X$ be $n \times n$ matrix with entries in $R$. Let $Y$ be $m \times m$ matrix with entries in $R$ formed from $\mathbb{Z}$-linear or $\mathbb{R}$-linear combinations of entries in $X$. Let $m \ge n$ and $r \ge n^{2}$.
Do there always exist $A$ and $B$ such that $AXB = Y$?
If so, what is the best way to compute matrices $A$ and $B$ such that $AXB = Y$?
Any linear algebra tools useful here?
This is not possible. Let each entry of $X$ be a distinct monomial. Then we can write each entry of $Y$ as a $\mathbb Z$-linear combination of these $n^2$ monomials, then the set of possible $Y$ can be seen as $(\mathbb Z^{n^2})^{m^2}= \mathbb Z^{n^2m^2}$. The possible values of $A$ and $B$ are both $\mathbb Z^{nm}$, so together they are $\mathbb Z^{2nm}$. The function which takes $A$ and $B$ to $Y$ is algebraic. Unless $2nm \geq n^2 m^2$, an algebraic function from $\mathbb Z^{2nm}$ to $\mathbb Z^{n^2m^2}$ cannot be surjective.
Also we can check that the cases $n=2,m=1$ and $n=1,m=2$ are impossible, so the only case where this is possible is the trivial $n=m=1$.
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.
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}$ where $x_{ij}= (X)_{ij} $.
Well, the embedding $$\iota\colon 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_{ij}\cdot 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$ and $y_{kl}=(Y)_{kl}$ 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 permute
$$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$.
