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?

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

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.

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

  • $\begingroup$ Could you elaborate? $\endgroup$
    – Mr.
    May 11 '13 at 5:47
  • 2
    $\begingroup$ 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. $\endgroup$ May 14 '13 at 12:13
  • $\begingroup$ 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. $\endgroup$
    – Tom
    May 14 '13 at 13:05
  • $\begingroup$ 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. $\endgroup$
    – Tom
    May 14 '13 at 20:07
  • $\begingroup$ @Tom: Your last example is a sum of matrix products, not one product. Note that the rank of $AXB$ is $\le$ the minimum of the ranks, since it is the dimension of the image. $\endgroup$ May 15 '13 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.