确定矩阵$A\in\mathbb{R}^{2\times2}$所需的未配对$x$、$y$样本最小数量求解

最近我参加了一场深度学习考试，碰到这么个问题，一直没搞明白正确答案，想请教下：

问题设定 #

我们有一个高斯分布，从中采样$x \in \mathbb{R}^{2}$，但实际观测到的是$y \in \mathbb{R}^{2}$，满足$y = A x$（$A$是我们要确定的$2\times2$矩阵）。

我们可以调用一个“预言机（oracle）”：输入一个自然数$n$，它会返回$n$个独立采样自该高斯分布的$x$值，以及对应的$n$个$y$值——但**$x$和$y$是未配对的**。具体来说，如果把返回的$x$标记为$x_1,\ldots,x_n$，$y$标记为$y_1,\ldots,y_n$，那么存在某个排列$\pi$，使得对所有$i$都有$y_i = A x_{\pi(i)}$。

核心问题 #

我们需要给预言机输入的最小$n$是多少，才能唯一确定矩阵$A$？请证明你的结论。如果任何有限（甚至无限）数量的样本都无法确定$A$，也请给出证明。另外，$A$可逆的情况和不可逆的情况有区别吗？

我的思路尝试 #

一开始我的直觉是这事儿可能办不到，但后来想到一个方向：

• 如果能拿到两组配对的样本$(x_1,y_1),(x_2,y_2)$，那确定$A$简直是小菜一碟。但现在样本是未配对的，我想是不是可以选$n=3$，然后遍历所有可能的排列组合：先用前两组“假设配对”的样本算出$A$，再用第三组样本验证这个$A$是否符合。不过我拿不准这个思路对不对，因为说不定存在两种不同的排列，算出的$A$完全不一样，但都能满足第三组样本的对应关系？我既没法证明这个思路可行，也找不到能反驳它的反例。

备注：内容来源于stack exchange，提问作者Ariel Yael