<p><em>(what follows solves the question for columns, easily adapted to rows either by transposing or by doing a column echelon instead of a row one)</em></p>

<p>You can do the following: put your matrix in <a href="https://en.wikipedia.org/wiki/Row_echelon_form" rel="nofollow">reduced echelon form</a> by the Gauss-Jordan elimination method. Note that this preserves $N(A)$.</p>

<p>Let's say we work on a 5x5 matrix and that we get:</p>

<p>\begin{bmatrix}
1 &amp; a_1 &amp; 0  &amp; 0 &amp; b_1 \\
0 &amp; 0 &amp; 1 &amp; 0 &amp; b_2 \\
0 &amp; 0 &amp; 0 &amp; 1 &amp; b_3 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0
\end{bmatrix}</p>

<p>From this form you can read $N(A)$ immediately: the only columns that can be independent are the ones holding the $1$s (the pivots of the elimination). Now it is obvious that they actually are independent <em>iff.</em> the coefficients on the right of the $1$ they hold are all $0$. </p>

<p>(in our example: the 1st column is independent <em>iff.</em> $a_1=0$ and $b_1=0$; the 3rd column is independent <em>iff.</em> $b_2=0$;
the 4th column is independent <em>iff.</em> $b_3=0$)</p>

<p>This way you get $N(A)$ in $O(n^e)$ where $n^e$ is the complexity of computing the echelon form. (the naive algorithm gives $e=3$).</p>

CC BY-SA 3.0
2015-11-19T20:52:55.820Z
Thank you, it works indeed! The key thing is to notice that linear operations with the rows do not change the dependencies between the columns, and vice versa. So, just need to transpose the matrix before performing Gaussian elimination.
xivaxy
CC BY-SA 3.0
2015-11-19T21:18:40.747Z
Oh indeed I mixed up rows and columns, sorry. I'll add a word about that in my answer.
Marc
CC BY-SA 3.0
2015-11-22T09:10:31.573Z
Rank is computable in $n^{2.373}$ operations. Unclear to me that reduced echelon form has also this operation count.
Ryan Williams
CC BY-SA 3.0
2015-11-23T13:15:05.623Z
Good point. I do not know much about this. Is there a known bound for echelon form better than $n^3$? I'll edit the answer accordingly.
Marc
CC BY-SA 3.0
2015-11-19T19:33:21.230Z
2015-11-23T15:40:45.173Z
2015-11-23T15:40:45.173Z
Marc
<p>There is a $n\times n$ matrix $A$, and we are asked to find the number $N(A)$ of independent rows in it, i.e. rows that are not a linear combination of the other rows. Clearly, if $rank(A)=n$, then $N(A)=n$, but for $rank(A)=n-1$  $N(A)$ can be anywhere between $0$ and $n-1$.</p>

<p>A straightforward way to check if a row is independent is to check if removing it from $A$ lowers the rank of $A$. Assuming calculating rank requires $O(n^\alpha)$ operations, calculating $N(A)$ this way would require $O(n^{\alpha+1})$. Are there more efficient ways to find $N(A)$?</p>

<linear-algebra>
Finding the number of independent rows of a matrix
xivaxy
# Finding the number of independent rows of a matrix

(Asked by: username_0 on 2015-11-18)

There is a $n\times n$ matrix $A$, and we are asked to find the number $N(A)$ of independent rows in it, i.e. rows that are not a linear combination of the other rows. Clearly, if $rank(A)=n$, then $N(A)=n$, but for $rank(A)=n-1$ $N(A)$ can be anywhere between $0$ and $n-1$.

A straightforward way to check if a row is independent is to check if removing it from $A$ lowers the rank of $A$. Assuming calculating rank requires $O(n^\alpha)$ operations, calculating $N(A)$ this way would require $O(n^{\alpha+1})$. Are there more efficient ways to find $N(A)$?

**Tags:** linear-algebra


---

## 1 answers

### Answer by username_1 on 2015-11-19. Score: 6 | Accepted answer

*(what follows solves the question for columns, easily adapted to rows either by transposing or by doing a column echelon instead of a row one)*

You can do the following: put your matrix in [reduced echelon form](https://en.wikipedia.org/wiki/Row_echelon_form) by the Gauss-Jordan elimination method. Note that this preserves $N(A)$.

Let's say we work on a 5x5 matrix and that we get:

\begin{bmatrix}
1 & a\_1 & 0 & 0 & b\_1 \\
0 & 0 & 1 & 0 & b\_2 \\
0 & 0 & 0 & 1 & b\_3 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}

From this form you can read $N(A)$ immediately: the only columns that can be independent are the ones holding the $1$s (the pivots of the elimination). Now it is obvious that they actually are independent *iff.* the coefficients on the right of the $1$ they hold are all $0$.

(in our example: the 1st column is independent *iff.* $a\_1=0$ and $b\_1=0$; the 3rd column is independent *iff.* $b\_2=0$;
the 4th column is independent *iff.* $b\_3=0$)

This way you get $N(A)$ in $O(n^e)$ where $n^e$ is the complexity of computing the echelon form. (the naive algorithm gives $e=3$).

> **Comments:**
> **username_0**: Thank you, it works indeed! The key thing is to notice that linear operations with the rows do not change the dependencies between the columns, and vice versa. So, just need to transpose the matrix before performing Gaussian elimination.  
> **username_1**: Oh indeed I mixed up rows and columns, sorry. I'll add a word about that in my answer.  
> **username_2**: Rank is computable in $n^{2.373}$ operations. Unclear to me that reduced echelon form has also this operation count.  
> **username_1**: Good point. I do not know much about this. Is there a known bound for echelon form better than $n^3$? I'll edit the answer accordingly.  

---

