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
    Sep 25, 2017 at 14:07
  • $\begingroup$ What is the complexity of row echelon form over $\Bbb F_q$? $\endgroup$
    – Turbo
    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$ 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
    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$ May 19, 2022 at 17:49

Your Answer

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

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