# 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. – Federico Poloni Dec 3 '20 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. – nkyraf33 Dec 3 '20 at 15:49
• related – Federico Poloni Dec 12 '20 at 8:21
• How large is N for the problems you're interested in? – Richard Dec 14 '20 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. – nkyraf33 Dec 15 '20 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.