Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$

Question

I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional structure: each row of $A$ takes the form $v_i \otimes v_i$ for some $v_i \in \mathbb{R}^r$ (here $1 \le i \le n$). (I.e., each row is the tensor product of some vector with itself.) Furthermore, think of $r^2$ as being about the same magnitude as $n$, i.e., $n = \Theta(r^2)$.

There isn't any further structure. In particular, $A$ is likely dense. I will say that in my specific application, I am taking $b$ to be $\mathbf{0}$, and I want to find a nonzero vector in the kernel of $A$. Furthermore, this nonzero vector can't look (when converted to an $r \times r$ matrix) like a skew-symmetric matrix; it must have some symmetric component. This is because I am then projecting the solution onto the $r (r + 1)/2$-dimensional space of symmetric matrices (in $\mathbb{R}^{r^2}$), and I need it to still be nonzero. (But I thought it would be best to state the problem more generally above.)

I've spent a ton of time trying to figure out how to solve this faster than the naive $O(n^3)$. I've tried performing some version of Gaussian elimination on the rows, $QR$ decomposition, etc. I am currently looking back at iterative methods to see if I missed something that may be of use, but I'm not experienced in this area. Even pointing me towards things to possibly try would be extremely helpful! Thanks!

Edit: Per @Federico Poloni's comment, this could be better formulated as: find a symmetric matrix $X$ such that $v_i^T X v_i = 0$ for $1 \le i \le n, v_i \in \mathbb{R}^r, X \in \mathbb{R}^{r^2}$, where $r (r + 1) / 2 > n$ so that we know that there is a nonzero solution.

Answer 1

If each row is a tensor product $v_i \otimes v_i$, then any vector $x$ that is a column-stacked version of a skew-symmetric matrix is in the kernel of $A$. For any $x$, you have $$(v_i \otimes v_i)x = v_i X v_i^T,$$ where $x = \mathrm{vec}(X)$ (see: https://en.wikipedia.org/wiki/Kronecker_product). If $X = -X^T$ then $$v_i X v_i^T = -v_i X^T v_i^T = -v_i X v_i^T = 0.$$

Note that this Kronecker-product structure is not equivalent to each row being a flattened version of a symmetric matrix. A symmetric matrix of size $n$ is determined by $\frac{1}{2}n(n+1)$ numbers whereas a matrix whose flattened version is the Kronecker-product of a vector of size $n$ with itself is determined by $n$ numbers.