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

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.

• I have edited the title to bring in the reformulation suggested in the solution, which seems to be also OP's original one, given the edit with remarks on symmetry. Dec 3, 2020 at 9:17
• @FedericoPoloni Thanks! I also added a bit to the question at the end to go along with the change in the title. Dec 3, 2020 at 15:49
• related Dec 12, 2020 at 8:21
• How large is N for the problems you're interested in? Dec 14, 2020 at 6:50
• @Richard Very large I guess, as I am looking at it from a theoretical standpoint. (Not actually trying to implement it.) So cutting down the time by a factor of 2 would be interesting, but I'm really looking for better asymptotic guarantees. Dec 15, 2020 at 0:33

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.