# How difficult is inverting a non-square matrix?

Partially inspired by ring learning with errors (RLWE), I am trying to construct a cryptosystem that requires the use of a non-invertible matrix.

Of the methods I've thought of to generate a matrix of determinant $0$, erasing a row/column or two seems the easiest, but I have no idea on how non-invertible this is.

I would like to know about known methods of reconstructing an unknown square matrix with known structure from its product with a non-square matrix.

• You have a matrix equation $\rm A X = B$ and want to solve for $\rm X$? – Rodrigo de Azevedo Sep 15 '17 at 9:54
• @RodrigodeAzevedo I have a non-square A and B, and I want to make sure nobody can find any X. – DannyNiu Sep 16 '17 at 4:01
• Over what field? – Rodrigo de Azevedo Sep 16 '17 at 8:40
• Suppose $\rm X$ is $n \times n$. Then you have $n$ linear systems $\rm A x_k = b_k$. If $\rm A$ is fat, these linear systems are underdetermined. If the null space is sufficiently high-dimensional, searching over all possible solutions may be sufficiently expensive. – Rodrigo de Azevedo Sep 16 '17 at 11:04
• Computing the "pseudoinverse" of non-square matrices is done all the time when fitting linear regression models: en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse EDIT: Point being, there is some existing work in linear algebra on computing "inverses" of non-square matrices. – pg1989 Sep 18 '17 at 4:14