0
$\begingroup$

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]; 
  • 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.2011-10-18

3 Answers 3

2

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

  • 0
    $A$h, 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"...)2011-10-19
3

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.

2

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.

  • 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$.2011-10-18