# Solve for $A$ and $B$ in $AXB=Y$

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?

-
Do you mean $\mathbb{Z}$-linear combinations ? – Dietrich Burde May 7 '13 at 17:18
Yes. $\mathbb{Z}$-linear. – Turbo May 7 '13 at 18:35
Do you mean that $A$ and $B$ have entries in $\Bbb Z$? – Daniele Zuddas May 8 '13 at 9:45
Yes in case of $\mathbb{Z}$-linear combinations. – Turbo May 8 '13 at 16:31

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}$ 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$.

-
Could you elaborate? – Turbo May 11 '13 at 5:47
thanks for editing, Emil ! – Tom May 13 '13 at 19:14
If (after evaluating $x_1,\dots,x_r$ at some points in $\mathbb Z$ or $\mathbb R$) the rank of $X$ is smaller than the rank of $Y$ there can be no solution. So there is a gap in your proof. – Peter Michor May 14 '13 at 12:13
I have to admit that I am puzzled now. Peter, could you be so kind to give a short example ? Furthermore, wouldn't that make your comment the desired answer ? btw I just clarified the notation above. – Tom May 14 '13 at 13:05
I guess we are not on the same page. But, if I take $X$ to be a non-zero number -denoted by $x$- and $Y$ to be $x \cdot I_n$, then there is a solution, although $x$ has rank 1 and $Y$ rank n. Indeed, denoting by $e_i$ the i-th basis vector we have $$Y=\sum_i e_i \cdot x \cdot e_i^t=\sum_i x \cdot e_i \cdot e_i^t.$$ I hope haven't made new mistakes now. – Tom May 14 '13 at 20:07

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$.

-