# Is it possible to construct this Matrix from the given information?

I am having some difficulty with Matrix multiplication properties, and I was wondering if someone could assist? Here is the problem:

Suppose there is an unknown Matrix $A\in\mathbb{R}^{2n\times 2n}$.
Also, there are two known Matrices $X\in\mathbb{R}^{n\times 2n}$ and $Y\in\mathbb{R}^{n\times 2n}$, both non-zero.

If we are given the following:

• $Z_1 = XAX^T$
• $Z_2 = XAY^T$
• $Z_3 = YAX^T$

Is it possible to construct $Z_4 = YAY^T$ from this information? If not, can you prove that it isn't possible, and what other information would be required?

Thank you.

--

Example:

X = [ 0.5 0.5 0 0; 0 0  0.5 0.5];
Y = [-0.5 0.5 0 0; 0 0 -0.5 0.5];

-
I totally misread your question so deleted my answer. Sorry for that. –  user13838 Oct 18 '11 at 12:21
@percusse: No problem. I didn't even see it. Thanks. –  user807566 Oct 18 '11 at 12:25
Those products aren't defined. I suspect you mean $X,Y\in\mathbb{R}^{n\times 2n}$? –  joriki Oct 18 '11 at 12:36
Consider the map $R^{4n^2} \rightarrow R^{3n^2}, A \mapsto (XAX^T,XAY^T,YAX^T)$, then this map can't be injective (look at dimensions). But the map $R^{4n^2} \rightarrow R^{4n^2}, A \mapsto (XAX^T,XAY^T,YAX^T,YAY^T)$ may be bijective with good choice of $(X,Y)$. –  user10676 Oct 18 '11 at 12:45
@user807566: A good way to remember this is to remember that you can multiply two matrices if their "adjacent" dimensions coincide, that is, you can do $k\times m$ times $m\times n$. Thus, the first dimension is the number of rows and the second one is the number of columns. –  joriki Oct 18 '11 at 12:46

This cannot work in general. For example, for $X=0$, $Z_1$, $Z_2$ and $Z_3$ are all zero independent of $A$, so you have no information about $A$ at all, and thus no idea what $Z_4$ might be.

-
Would anything change if we made the condition X != 0 and Y != 0? –  user807566 Oct 18 '11 at 12:44
@user807566: No. user10676's comment under the question really says it all. For suitable $X$ and $Y$, $Z_1$ to $Z_4$ contain all the information about $A$, which has $4n^2$ degrees of freedom, and this can't be compressed into the $3n^2$ degrees of freedom in $Z_1$ to $Z_3$. To see this more concretely, consider $X$ and $Y$ such that together they form the identity matrix. Then $Z_1$ through $Z_4$ together form $A$, and you obviously can't reconstruct one block of $A$ from the other three blocks of $A$. –  joriki Oct 18 '11 at 13:07

In my comment, I explained that it is more interesting to also consider $YAY^T$.

I claim that the map $$f : M_{2n}(R) \rightarrow M_n(R)^4, A \mapsto (XAX^T,XAY^T,YAX^T,YAY^T).$$ is bijective if and only if $rank(X,Y)=2n$ (as predicted by joriki).

Proof : write $X=[x_1,x_2]$, $Y=[y_1,y_2]$ and $A=\left(\begin{matrix} a&b\\c&d \end{matrix}\right)$ (all small letters are $n\times n$-matrices). Then $f$ is $$f(\begin{matrix} a&b\\c&d \end{matrix})=(x_1 a x_1^T + x_1 b x_2^T + x_2 c x_1^T + x_2 d x_2^T,...).$$

Consider the map $$g : M_{2n}(R) \rightarrow M_{2n}(R), A \mapsto [X,Y].A.[X,Y]^T = (\begin{matrix} x_1 a x_1^T + x_1 b x_2^T + x_2 c x_1^T + x_2 d x_2^T&\cdots\\\cdots&\cdots \end{matrix}).$$

Then $f$ and $g$ are the same map. But we know that $g$ is the Kronecker product $[X,Y] \otimes [X,Y]^T$ (http://en.wikipedia.org/wiki/Kronecker_product), and we know that it is invertible iff $[X,Y]$ is invertible.

-

joriki comments that one would need stronger conditions on $X$ and $Y$ to make this work, such as "the matrix formed by $X$ and $Y$ being of full rank". However, consider the following counter-example,

$A=\left( \begin{array}{cc} a & b \\ c & x \end{array} \right)$

$X=\left( \begin{array}{cc} 1 & 0 \end{array} \right)$

$Y=\left( \begin{array}{cc} 1 & 1 \end{array} \right)$

Then $XAX^T=a$, $XAY^T=a+b$, $YAX^T=a+c$. Note that none of these depend on $x$, while $YAY^T=a+b+c+x$. Thus, there exist infinitely many matrices $A_i$ such that,

$(1, 0)A_i(1, 0)^T=p$,

$(1, 0)A_i(1, 1)^T=q$,

$(1, 1)A_i(1, 0)^T=r$,

but,

$(1, 1)A_i(1, 1)^T=s_i$ is different for each $A_i$.

(I may have made a mistake with my interpretations of stuff...I don't think I have though...)

-
Can you clarify? My answers to your example were: $XAY^T = b$, and $YAX^T = c$, and $YAY^T = x$ I'm not sure how you got $a + b$, etc. --Nevermind, I think you have a typo, and should be $Y=(1 1)$ –  user807566 Oct 18 '11 at 14:12
Yeah, sorry, I've fixed it now. –  user1729 Oct 18 '11 at 15:24
I think there's a misunderstanding here (which I may have helped bring about with my ill-advised comment, which I retracted shortly after I'd written it because I realized that @user10676's dimensionality argument is correct). user10676 proves that the map $f$ is bijective, and this proves that the problem posed in the question can not be solved, since $YAY^T$ is not determined by the other three blocks -- which is also what you prove. user10676 further proves that $A$ can be determined from all four blocks if and only if $(X,Y)$ has full rank. Sorry if I contributed to the confusion. –  joriki Oct 18 '11 at 20:19
Ah, sorry, I was half-way through typing this up when user10676 posted his response, so I only skimmed it and seemingly got the wrong end of the stick! (Actually, I probably just read the word "bijection"...) –  user1729 Oct 19 '11 at 8:47