# Decomposing outer product or general rank factorization over $\Bbb F_q$

1. 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.

1. 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?

2. What is the best randomized complexity algorithm?

Over $\Bbb R$ we have SVD that achieves an analog of this time complexity.

There might be faster algorithms, but it is easy to compute such a factorization (for any $r$) from the reduced row-echelon form of $M$: set $M_2$ to be the RREF with zero rows removed, and $M_1$ to be the columns of $M$ corresponding to the identity submatrix of the RREF. RREFs can be computed efficiently over any field ($O(n^3)$ arithmetic operations using Gaussian elimination), and the rest of the algorithm can be implemented in $O(n^2)$ time.
Example: $$M = \begin{bmatrix}2 & 2 & 12 \\ 3 & 1 & 12 \\ 4 & -1 & 9\end{bmatrix} \sim \begin{bmatrix}1 & 0 & 3\\ 0 & 1 & 3 \\ 0 & 0 & 0\end{bmatrix}$$ has rank 2. Set $$M_2 = \begin{bmatrix}1 & 0 & 3 \\ 0 & 1 & 3\end{bmatrix}$$ The RREF has the identity submatrix in the first two columns, so set $$M_1 = \begin{bmatrix}2 & 2 \\ 3 & 1 \\ 4 & -1 \end{bmatrix}$$ It's easy to see that $M_1M_2 = M$.
• What is the complexity of row echelon form over $\Bbb F_q$? Commented Sep 25, 2017 at 14:09
• You can computed RREFs in $O(n^3)$ arithmetic operations over any field using Gaussian elimination. I edited to state this more explicitly. Commented Sep 25, 2017 at 14:13
• Can you post a reference for RREF computation over $\Bbb F_q$ with complexity? So is the complexity $O(n^3\log q)$? Commented Sep 25, 2017 at 14:13
• Naively you can do Gaussian elimination in time $O(n^2 r)$ arithmetic operations (each of which costs $\tilde O(\log q)$ over $\mathbb{F}_q$), where $r$ is the rank, because after $r$ rows the rest are zero. But in fact you can do better, namely $O(n^2 r^{\omega-2})$, see Yuster SODA 2010 dl.acm.org/doi/abs/10.5555/1873601.1873640 Commented May 19, 2022 at 17:49