Hard instances of matrix factorization Are there any hard problems related to matrix factorization?
Suppose $E$ is hermitian with public eigenvectors such that $U^T\Lambda U = E$ with $U$ public but $E,\Lambda$ secret. Given $X$ secret, we would &quot;encrypt&quot; it as $EX = U^T\Lambda UX$ can you create instances such that $f(U,EX) \rightarrow X$ is not polynomial time?
I believe matrix inversion is polytime, but I am not sure if this is worst case or average case. First thing you can do is knock off the first term so $UEX = \Lambda UX$, and with $U$ public, but $\Lambda,X$ chosen perhaps to make the problem hard, is this still possible in polytime?
This is not related to your particular factorization problem (I believe), but is related to a hard matrix factorization problem (I believe). It is known as the &quot;Lattice Isometry Problem&quot; (or perhaps it is the &quot;Lattice isomorphism problem&quot; --- I will call it LIP either way). Stated in matrix terms, this problem is, given two matrices $\mathbf{B}_1, \mathbf{B}_2\in\mathbb{R}^{n\times k}$, determine if they generate isometric lattices.
A lattice generated by some basis $\mathbf{B}\in\mathbb{R}^{n\times k}$ is defined as:
$$\mathcal{L}(\mathbf{B}) = \{\vec x\in\mathbb{R}^n\mid \exists \vec y\in\mathbb{Z}^k\text{ s.t. }\vec x = \mathbf{B}\vec y\} = \mathbf{B}\mathbb{Z}^k$$
As defined, basis of a given lattice are specified up to multiplication by an (integer) change-of-basis matrix on the right, i.e. if $\mathbf{B}\in\mathbb{R}^{n\times k}$ is the basis of a lattice, and $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, then $\mathbf{BU}$ is a basis of the same lattice.
Two lattices $L, L'$ are said to be isometric if they are related by an orthogonal transformation of determinant 1.
In terms of matrices, $\mathcal{L}(\mathbf{B})$ is isometric to $\mathcal{L}(\mathbf{B}')$ if there exists some $\mathbf{O}\in SO(n)$ such that $\mathbf{O}\mathbf{B} = \mathbf{B}'$.
All combined, this means that the lattice isometry problem takes as input two matrices $\mathbf{B}, \mathbf{B}'$, and attempts to factor $\mathbf{B}' = \mathbf{OBU}$ for $\mathbf{O}\in SO(n)$, $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, so can be seen as a certain matrix factorization problem.
I don't know precise results for the hardness of LIP, but a certain &quot;natural&quot; extension of it to the ideal lattice setting becomes easier than one would hope for. This is the content of the Gentry-Szydlo algorithm, which determines whether a certain ideal lattice is isometric to $\mathbb{Z}^k$, which can also be described as &quot;having an orthonormal basis&quot;.