我想解决一个欠定的线性方程组$A x = b$和$A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. 矩阵$A$具有以下附加结构：每一行$A$采取形式$v_i \otimes v_i$对于一些$v_i \in \mathbb{R}^r$（这里$1 \le i \le n$）。（即，每一行都是某个向量与其自身的张量积。）此外，想想$r^2$与$n$， IE，$n = \Theta(r^2)$.

没有任何进一步的结构。特别是，$A$很可能是稠密的。我会说，在我的具体申请中，我正在服用$b$成为$\mathbf{0}$，我想在内核中找到一个非零向量$A$. 此外，这个非零向量不能看（当转换为$r \times r$矩阵）像一个斜对称矩阵；它必须有一些对称的分量。这是因为我将解决方案投影到$r (r + 1)/2$对称矩阵的维空间（在$\mathbb{R}^{r^2}$)，我需要它仍然是非零的。（但我认为最好在上面更笼统地说明问题。）

我花了很多时间试图弄清楚如何比天真更快地解决这个问题$O(n^3)$. 我试过在行上执行一些版本的高斯消除，$QR$分解等。我目前正在回顾迭代方法，看看我是否遗漏了一些可能有用的东西，但我在这方面没有经验。即使将我指向可能尝试的事情也会非常有帮助！谢谢！

编辑：根据@Federico Poloni 的评论，这可以更好地表述为：找到一个对称矩阵$X$这样$v_i^T X v_i = 0$为了$1 \le i \le n, v_i \in \mathbb{R}^r, X \in \mathbb{R}^{r^2}$， 在哪里$r (r + 1) / 2 > n$这样我们就知道有一个非零解。