Provided the shape $(m, n)$ of an unknown matrix $A$, as well as the value of the matrix $(A^T A) * (A A^T)$, could you find the initial matrix $A$?

Question

Problem

Consider a matrix, $\mathbf{A}$, of shape $m \times n$.

Now, let $\mathbf{A_1}$ equal the matrix multiplication of the transposition of $\mathbf{A}$, a.k.a. $\mathbf{A}^T$, by $\mathbf{A}$ itself. In addition, let $\mathbf{A_2}$ equal the same product, simply performed in reverse:
$\mathbf{A_1} = \mathbf{A}^T\mathbf{A}$
$\mathbf{A_2} = \mathbf{A} \mathbf{A}^T$

Now, let $C$ equal the convolution of $A_1$ and $A_2$, using padding = same:
$\mathbf{C} = \mathbf{A_1} * \mathbf{A_2}$

Now, suppose we were provided solely the following pieces of information:

• The shape of A, or in other words, the values of $m$ and $n$
• The matrix, $\mathbf{C}$

Provided we are given only these, can we (and, if so, how can we) determine the original matrix, $\mathbf{A}$.

Further Emphasis

For example, say $\mathbf{A}$ is a $3 \times 4$ matrix as follows:

$\mathbf{A} = \begin{bmatrix}3&7&1&9\\2&6&5&4\\8&8&2&3\end{bmatrix}$

Of, course, in the problem, we will not actually know these values in the cells of $\mathbf{A}$; all we know directly about $\mathbf{A}$ is its shape. In addition (as I stated previously) we will, indeed, be provided with the values of the cells of $\mathbf{C}$.

Now, let's compute $\mathbf{A_1}$ and $\mathbf{A_2}$ (we won't be provided with these):

$\mathbf{A_1} = \mathbf{A}^T \mathbf{A} = \begin{bmatrix}3&2&8\\7&6&8\\1&5&2\\9&4&3\end{bmatrix} \begin{bmatrix}3&7&1&9\\2&6&5&4\\8&8&2&3\end{bmatrix} = \begin{bmatrix}77&97&29&59\\97&149&53&111\\29&53&30&35\\59&111&35&106\end{bmatrix}$

$\mathbf{A_2} = \mathbf{A} \mathbf{A}^T = \begin{bmatrix}3&2&8\\7&6&8\\1&5&2\\9&4&3\end{bmatrix} \begin{bmatrix}3&7&1&9\\2&6&5&4\\8&8&2&3\end{bmatrix} = \begin{bmatrix}140&89&109\\89&81&86\\109&86&141\end{bmatrix}$

Okay, now lets compute the convolution $\mathbf{C} = \mathbf{A_1} * \mathbf{A_2}$. In general, the convolution operation is commutative, so it typically doesn't matter which order the operation is performed in. However, in this case, since we are using padding = same, the convolution is not necessarily a commutative operation). In this problem, however, $\mathbf{A_2}$ is going to be the convolutional kernel/filter. If you don't know how same padding works, I suggest referring to the second answer to this question on Stack Overflow. Anyways, here is the properly-padded matrix, $\mathbf{A_1}$ (We got lucky because it happens to be much easier in this case, it's just a padding of thickness 1 around all edges. Note, however, that this is not always the case. Same padding ensures that the shape of the resulting convolution is the same as the shape of the input matrix. It makes sure to make the padding as even as possible on the right/left and top/bottom sides. If an odd number of padding layers are required, there will be 1 extra on the right and/or bottom side(s), while the left and/or top side(s) will have one less layer). Okay, now for the convolution (Sorry if I make a mistake somewhere here. I did type it into Python, but It's always possible I could have made a typo somewhere. Anyways, you get the point):

$\mathbf{C} = \mathbf{A_1} * \mathbf{A_2} = \begin{bmatrix}0&0&0&0&0&0\\0&77&97&29&59&0\\0&97&149&53&111&0\\0&29&53&30&35&0\\0&59&111&35&106&0\\0&0&0&0&0&0\end{bmatrix} * \begin{bmatrix}140&89&109\\89&81&86\\109&86&141\end{bmatrix} = \begin{bmatrix}44363&48314&52440&22929\\48314&59566&62935&29097\\52440&62935&77823&35683\\22929&29097&35683&18836\end{bmatrix}$

Okay, now, if I gave you the following information (say you didn't just read the answer above, but only the below info):

• $\mathbf{C} = \begin{bmatrix}44363&48314&52440&22929\\48314&59566&62935&29097\\52440&62935&77823&35683\\22929&29097&35683&18836\end{bmatrix}$
• $m = 3$
• $n = 4$

Could you (and if so, how can you) determine every value in $\mathbf{A}$?