# Solution to a system of linear equations with an unknown matrix product

Consider the system of equations $$Xy=Ab$$ where $X$ and $A$ are $m \times m$ invertible matrices and $y$ and $b$ are $m \times n$ matrices. The matrices $X$ and $y$ are unknown and the matrices $A$ and $b$ are given. Under what restrictions on $X$ (with the same restrictions on $A$) and / or $y$ (with the same restrictions on $b$) do $X=A$ and $y=b$? For example, if we restrict $X$ (and $A$) to be the identity matrix then $X=A$ and $y=b$. What if we impose that $X$ and $A$ must be some band matrices with ones on the diagonal or some sparse matrix?

A necessary condition is the number of unknowns is less than or equal to $m \times n$ because $Ab$ provides $m \times n$ equations.

For instance, if $m=2,n=1$, take $X,A\in E$, $y,b\in F$ where $E=\{\begin{pmatrix}x&u\\v&w\end{pmatrix};v\not= 0,xw\not=uv\}$,$F=\{[z,d]^T;z\not= 0\}$ and $u,v,w,d$ are fixed.
EDIT: we can generalize for $m\geq 3,n=1$ as follows. Take $X,A\in E$, $y,b\in F$ where $E=\{C=[c_{i,j}]\in M_{m,m};c_{1,1}=x_1,\cdots,c_{m-1,m-1}=x_{m-1},\det(C)\not= 0\}$, $F=\{[x_m,d_2,\cdots,d_m]^T;x_m\not= 0\}$ where the $(c_{i,j})$ that are not some $x_i$ and the $(d_i)_i$ are fixed s.t. $c_{m,1}\not= 0$ and $d_2\cdots d_{m-1}\not=0$;
• Yes, this seems like a general condition for $m=2$ and $n=1$. Did you just set up a system of equations and think about how to solve them? Is it possible to find a general condition for $m=M$ and $n=1$? I will try for $m=3$ and $n=1$. – user103828 Dec 15 '14 at 14:15
(Wasn't sure if to post this as a partial solution or edit the question). Building on @loup blanc, let $m=2$ and $n=1$, then
\begin{align*} x_{11}y_{11}+x_{12}y_{21} &=a_{11}b_{11}+a_{12}b_{21}\\ x_{21}y_{11}+x_{22}y_{21} &=a_{21}b_{11}+a_{22}b_{21} \end{align*} At most two elements of $(X,y)$ are unknown and the rest must be fixed. We simply go through all the possible cases and solve for the unknowns using the equations above: If $y_{11}$ and $y_{21}$ are unknown then they can be solved for as long as $x_{22}x_{11}-x_{21}x_{12} \neq 0$; if $x_{11}$ and $x_{21}$ are unknown then they can be solved for as long as $y_{11} \neq 0$; etc.
Finally, the only cases where it is not possible to solve is when $x_{11}$ and $x_{12}$ are unknown or $x_{21}$ and $x_{22}$ are unknown.