# 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 "encrypt" 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 "Lattice Isometry Problem" (or perhaps it is the "Lattice isomorphism problem" --- 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 "natural" 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 "having an orthonormal basis".

• Thank you very much. This gives me a place to start googling. Apr 14, 2021 at 20:41