I am currently working on a problem about matrix reconstruction. I am given a theorem and I either need to prove it or disprove it (ideally by a counterexample).
The theorem is the following:
Let $n,m\ge 1$ and $M_1,M_2\in \mathbb{N}^{n\times m}$ be two matrices such that $$M_1*M_1^T = M_2*M_2^T$$ and $$M_1^T*M_1 = M_2^T*M_2.$$ Then there are two permutation matrices $P\in \mathbb R^{n\times n}$ and $Q\in \mathbb R^{m\times m}$ such that $P M_1 Q = M_2$.
In other words: A matrix $M\in \mathbb N^{n\times m}$ can be reconstructed from $M*M^T$ and $M^T*M$ up to a permutation of rows and columns.
Until now I was not able to find a counterexample to this theorem, but I also could not find a proof. If it turns out that there is a counterexample to this theorem, is there also a counterexample with $M_1,M_2\in \{0,1\}^{n\times m}$?
------Edit 1-------
$$M_1 = \begin{pmatrix}0 & 180 & 90 \\ 180 & 45 & 0 \\ 90& 0& 45\end{pmatrix},\quad M_2 = \begin{pmatrix}200& 20&10\\20&173&64\\10&64&77\end{pmatrix}$$ is a counterexample, since $$M_1^T*M_1 = M_2^T*M_2 = M_1*M_1^T = M_2*M_2^T = \begin{pmatrix}40500&8100&4050\\8100&34425&16200\\4050&16200&10125\end{pmatrix}.$$
However, now I am desperately looking for a counterexample with matrix entries in $\{0,1\}$. Or of course a proof that there is no counterexample.
You have to allow $P$ and $Q$ to be rotation matrices, not just permutation matrices. As you've worded it, $M_1=I, M_2=\frac 1 {\sqrt{2}}\begin{bmatrix}1 & 1\\-1&1\end{bmatrix}$ constitutes a counterexample.
The inverse of a rotation matrix is its transpose (https://en.wikipedia.org/wiki/Rotation_matrix), so given any rotation matrix $R$ and arbitrary matrix $M$, $(RM)^TRM=M^TR^TRM=M^TM$.