Finding the number of independent rows of a matrix 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)$?
(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 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 &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}

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