TransWikia.com

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

Computational Science Asked by nkyraf33 on December 4, 2020

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}^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.

One Answer

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.

Answered by Amit Hochman on December 4, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP