<p>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.</p>

<p>Example:
$$M = \begin{bmatrix}2 &amp; 2 &amp; 12 \\ 3 &amp; 1 &amp; 12 \\ 4 &amp; -1 &amp; 9\end{bmatrix} \sim \begin{bmatrix}1 &amp; 0 &amp; 3\\ 0 &amp; 1 &amp; 3 \\ 0 &amp; 0 &amp; 0\end{bmatrix}$$
has rank 2. Set
$$M_2 = \begin{bmatrix}1 &amp; 0 &amp; 3 \\ 0 &amp; 1 &amp; 3\end{bmatrix}$$
The RREF has the identity submatrix in the first two columns, so set
$$M_1 = \begin{bmatrix}2 &amp; 2 \\ 3 &amp; 1 \\ 4 &amp; -1 \end{bmatrix}$$
It's easy to see that $M_1M_2 = M$.</p>

CC BY-SA 3.0
2017-09-25T14:07:57.547Z
Is this over finite fields?
Turbo
CC BY-SA 3.0
2017-09-25T14:09:11.283Z
What is the complexity of row echelon form over $\Bbb F_q$?
Turbo
CC BY-SA 3.0
2017-09-25T14:13:17.663Z
You can computed RREFs in $O(n^3)$ arithmetic operations over any field using Gaussian elimination. I edited to state this more explicitly.
Andrew Morgan
CC BY-SA 3.0
2017-09-25T14:13:20.063Z
Can you post a reference for RREF computation over $\Bbb F_q$ with complexity? So is the complexity $O(n^3\log q)$?
Turbo
CC BY-SA 4.0
2022-05-19T17:49:12.523Z
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 https://dl.acm.org/doi/abs/10.5555/1873601.1873640
Joshua Grochow
CC BY-SA 3.0
2017-09-25T14:07:28.757Z
2017-09-25T14:12:23.130Z
2017-09-25T14:12:23.130Z
Andrew Morgan
<blockquote>
  <ol>
  <li>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&gt;0$ way to find $A,B$ (up to scale (notice $aA,a^{-1}B$ also works))?</li>
  </ol>
</blockquote>

<p>Refer <a href="https://en.wikipedia.org/wiki/Outer_product#Vector_multiplication" rel="nofollow noreferrer">outer product of vectors</a>.</p>

<blockquote>
  <ol start="2">
  <li><p>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?</p></li>
  <li><p>What is the best randomized complexity algorithm?</p></li>
  </ol>
</blockquote>

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

<cc.complexity-theory><ds.algorithms><linear-algebra><matrices><algebraic-complexity>
Decomposing outer product or general rank factorization over $\Bbb F_q$
Turbo
# Decomposing outer product or general rank factorization over $\Bbb F_q$

(Asked by: username_0 on 2017-09-25)

> 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](https://en.wikipedia.org/wiki/Outer_product#Vector_multiplication).

> 2. 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?
> 3. What is the best randomized complexity algorithm?

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

**Tags:** cc.complexity-theory, ds.algorithms, linear-algebra, matrices, algebraic-complexity

---

## 1 answers

### Answer by username_1 on 2017-09-25. Score: 2

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

> **Comments:**
> **username_0**: Is this over finite fields?  
> **username_0**: What is the complexity of row echelon form over $\Bbb F_q$?  
> **username_1**: You can computed RREFs in $O(n^3)$ arithmetic operations over any field using Gaussian elimination. I edited to state this more explicitly.  
> **username_0**: Can you post a reference for RREF computation over $\Bbb F_q$ with complexity? So is the complexity $O(n^3\log q)$?  
> **username_2**: 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 https://dl.acm.org/doi/abs/10.5555/1873601.1873640  

---

