- Given matrix $M\in\Bbb F_q^{n\times n}$ with the promise that there are two matrices $A\in\Bbb F_q^{n\times 1}$ and $B\in\Bbb F_q^{1\times n}$ such that $AB=M$ is there a deterministic $O((n\log q)^c)$ at some $c>0$ way to find $A,B$ (up to scale (notice $aA,a^{-1}B$ also works))?
Refer outer product of vectors.
What if $A\in\Bbb F_q^{n\times r}$ and $B\in\Bbb F_q^{r\times n}$ at some $1\leq r\leq n$ holds? Can we have a deterministic $O((nr\log q)^c)$ algorithm?
What is the best randomized complexity algorithm?
Over $\Bbb R$ we have SVD that achieves an analog of this time complexity.