This is a question from an exam on deep learning that I took not so long ago, and I'd like to know the answer.
The Setting
There is a Gaussian distribution from which we sample $x \in \mathbb{R}^{2}$ values, but what we observe is $y \in \mathbb{R}^{2}$, where $y = A x$. We have an oracle that takes as input a number $n \in \mathbb{N}$ and returns $n$ different $x$ values sampled from the Gaussian and $n$ $y$ values corresponding to the $x$ values, but they are unpaired (meaning that if we label the $x, y$ values as
$$\begin{array}{c} x_{1},\ldots,x_{n}\\ y_{1},\ldots,y_{n} \end{array}$$
there is some permutation $\pi$ such that for all $i$ we have $y_{i}=Ax_{\pi\left(i\right)}$.
The Question
What is the minimal number $n$ that we need to give to the oracle, in order to determine $A$ (prove your answer). If it isn't possible with any finite (or even infinite) number of samples - prove it. Are the cases where $A$ is invertible different from the case where it isn't?
My Attempt
My initial gut feeling was that it's impossible, but then I had the following Idea.
Clearly, if we had two paired samples $\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right)$ we could determine $A$ easily. But since they are unpaired, what we could maybe do is choose $n=3$ and go over all different permutations, using the first two pairs to determine $A$ and check if it fits the 3rd pair. However, I am not sure if this is correct, as perhaps I could find two permutations yielding different $A$'s.
I wasn't able to prove this nor find a counter-example
With the sampling from the Gaussian distribution, I feel it ends up being a trick question where the answer is that we can't even guarantee that we'll get any linearly independent samples.
But even if we get samples $x_1,...,x_n$ that span $\mathbb R^2$, we can't always uniquely determine $A$. For this, let $R_\alpha$ be the matrix that clockwise rotates a point by $\alpha$ degrees.
Now define $x_i=R_{360/n}^{i-1} \pmatrix{0\\1}$, and $y_i:=x_i$. Then for each $k\in\{0,...,n-1\}$ the matrix $R_{360/n}^{k}$ is a possible solution for some permutation $P$.
More generally, this works for any matrix $A$ with $A^k=I$ for some $k\in\mathbb N$.
If $A$ has rank 1, the points $y_1,...,y_n$ lie on a 1-dimensional subspace. That is, after choosing a suitable base, we can write $x_1,..,x_n\in\mathbb R^2, y_1,...,y_n\in\mathbb R$ and $A=(a,b)$ for some $a,b\in\mathbb R$.
(More specifically, the $y_i$ would have as second component 0, so we omit it)
So, the solutions are
$$ \{a,b\in\mathbb R\mid \pmatrix{x_1^T\\\vdots\\ x_n^T} \pmatrix{a\\b} =P\pmatrix{y_1\\\vdots\\ y_n} \land P \text{ is a permutation matrix} \} $$
Now, the Rouché–Capelli theorem tells us that to end up with exactly one solution, all permutations of $\pmatrix{y_1\\\vdots\\ y_n}$ need to be linearly independent to the columns of $\pmatrix{x_1^T\\\vdots\\ x_n^T}$.
So, one can get a generic counterexample by choosing $\pmatrix{y_1\\\vdots\\ y_n}$ and the columns of $\pmatrix{x_1^T\\\vdots\\ x_n^T}$ such that all are permutations of one another. One can generalize the Rouché–Capelli theorem to matrix equations to obtain a similar criterion for generic $A\in\mathbb R^{m\times m}$.
To make it concrete, let the first column of $\pmatrix{x_1^T\\\vdots\\ x_n^T}$ be $\pmatrix{1\\\vdots\\n}$, and the second $\pmatrix{2\\1\\3\\4\\\vdots\\n}$, that is the first column, but the first and second elements have been permuted.
Now, if $y_i=\pmatrix{i\\0}$, then $A$ can e.g. either be $\pmatrix{1&0\\0&0}$ or $\pmatrix{0&1\\0&0}$.
Finally, if the rank of $A$ is 0, then if we get samples $x_1,...,x_n$ that span $\mathbb R^2$, then for any $n\ge 2$ we can uniquely determine that $A=0$.