MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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