Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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];
share|improve this question
    
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
2  
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
1  
@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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Would anything change if we made the condition X != 0 and Y != 0? –  user807566 Oct 18 '11 at 12:44
1  
@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.

share|improve this answer

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

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

Your Answer

 
discard

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.