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