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.


1 Answer 1


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

  • $\begingroup$ Is this over finite fields? $\endgroup$
    – Turbo
    Commented Sep 25, 2017 at 14:07
  • $\begingroup$ What is the complexity of row echelon form over $\Bbb F_q$? $\endgroup$
    – Turbo
    Commented Sep 25, 2017 at 14:09
  • $\begingroup$ You can computed RREFs in $O(n^3)$ arithmetic operations over any field using Gaussian elimination. I edited to state this more explicitly. $\endgroup$ Commented Sep 25, 2017 at 14:13
  • $\begingroup$ Can you post a reference for RREF computation over $\Bbb F_q$ with complexity? So is the complexity $O(n^3\log q)$? $\endgroup$
    – Turbo
    Commented Sep 25, 2017 at 14:13
  • 1
    $\begingroup$ 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 $\endgroup$ Commented May 19, 2022 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.