7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xivaxy Nov 19 '15 at 20:52
  • $\begingroup$ Oh indeed I mixed up rows and columns, sorry. I'll add a word about that in my answer. $\endgroup$ – Marc Nov 19 '15 at 21:18
  • 1
    $\begingroup$ Rank is computable in $n^{2.373}$ operations. Unclear to me that reduced echelon form has also this operation count. $\endgroup$ – Ryan Williams Nov 22 '15 at 9:10
  • $\begingroup$ 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. $\endgroup$ – Marc Nov 23 '15 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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