# 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 ? May 7 '13 at 17:18
• Yes. $\mathbb{Z}$-linear.
– Mr.
May 7 '13 at 18:35
• Do you mean that $A$ and $B$ have entries in $\Bbb Z$? May 8 '13 at 9:45
• Yes in case of $\mathbb{Z}$-linear combinations.
– 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$.

• Could you elaborate?
– Mr.
May 11 '13 at 5:47
• 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. 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
• @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. May 15 '13 at 5:29
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9547435641288757, "perplexity": 156.35897176270183}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-43/segments/1634323584554.98/warc/CC-MAIN-20211016074500-20211016104500-00503.warc.gz"}