0
$\begingroup$

Suppose I have a matrix that I know to be singular. This means that there is at least one row in the matrix which is a linear combination of the other rows. What is the fastest way to identify which row that is or which rows they are?

I'm aware that the solution to this problem is not unique in general. The goal is to determine a set of rows which, if removed, leave only linearly independent rows. Then, more linearly independent rows can be added to get a non-singular matrix. Obviously I'm leaving out a bit of context regarding why I would be doing this, but I believe I have included everything relevant to the question.

My thinking is basically to attempt to attempt Gram Schmitt and just mark whatever step returns a zero vector. I doubt there's a faster approach than this, but suspect this problem has been studied to the point that a definitive answer exists.

Edit: To be clear, I only want to find a minimal set of rows such that, if they are removed, I get back a linearly independent set of vectors.

Also, let me give an example of the algorithm that I am proposing. I'm using an example given by nir shahar but slightly modified.

Suppose I have a matrix with rows (1, 0, 0), (0, 1, 0), (1, 0, 0)

The Gram Schmitt algorithm returns first: (1, 0, 0) second: (0, 1, 0) - 0 * (1, 0, 0) third: (1, 0, 0) - 1 * (1, 0, 0) - 0 * (0, 1, 0)

I'm not actually returning this set of vectors. All I care about is the fact that the third step returns the zero vector. So, I flag the third row as being a "problem."

$\endgroup$
6
  • $\begingroup$ You can return just all of the rows. Obviously, they are linearly dependent and when you remove all of them you are left with linearly independent vectors (since $\emptyset$ is linearly independent by the definition). Of course this isn't what you are looking for, so I assume you wanted the smallest linearly dependent set? $\endgroup$
    – nir shahar
    Feb 17 at 19:57
  • $\begingroup$ If this is what you meant, then also your approach wont work. Consider the following vectors: (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0) as the rows of your matrix. Its easy to see that the smallest linearly dependent set consists only of the first and last rows. But your approach will return the entire set of vectors instead. Even if you try to modify Gram Schmidt a bit so it won't fail in this way, it still will be easy enough to construct a contradicting example. $\endgroup$
    – nir shahar
    Feb 17 at 20:01
  • $\begingroup$ @nirshahar To your first comment, my answer is yes. I'll edit in a moment to clarify. I guess I wasn't explicit. To your second comment, I'm not sure I agree. If you apply Gram Schmitt to this set, the first three steps should just return the first three rows. While doing the fourth step, you would add - 1 * (1, 0, 0) - 0 * (0, 1, 0) - 0 * (0, 0 , 1), which would return the 0 vector. So, I would flag that row as problematic and remove it - leaving the rest be. $\endgroup$
    – user37344
    Feb 17 at 20:08
  • $\begingroup$ @nirshahar I have attempted to clarify the question on both of your points. $\endgroup$
    – user37344
    Feb 17 at 20:16
  • $\begingroup$ You can obtain it by doing LU factorization or Gauss elimination. If, for example, you do only column transformations, then the non-zero rows of the $U$ factor tell you a maximal set of rows that are independent. Gram-Schmidt has the same asymptotic complexity, but it often suffers from numerical instability. $\endgroup$
    – plop
    Feb 17 at 21:49
2
$\begingroup$

This is not an answer, but a response to this comment.

Assume that $A$ is the matrix which columns are the rows that we want to test for linear independence. I am putting them are columns for no other reason than personal comfort.

Doing the row transformations required in Gaussian elimination correspond to multiplying $A$ from the left by some elementary matrices. Assume that $T$ is the product of all elementary matrices corresponding to the row transformations needed to put $A$ in echelon form. So, $TA$ is is echelon form.

If each column has an echelon then the system $TAx=0$, with $x$ a column vector of the right size, has only the solution $x=0$. Since $T$ is invertible, we have that $Ax=0$ has only the solution $x=0$. Since $Ax$ is nothing else than a linear combination of the columns of $A$ using the components of $x$ as coefficients, what we got is that the columns of $A$ are linearly independent.

Now assume that some columns of $TA$ don't have echelons. Let's call these the dependent columns. You can give any values you want to the components of $x$ corresponding to the positions of the dependent columns and then solve the resulting system $TAx=0$ for the remaining components, by backward substitution. In particular we can put non-zero values to the components of $x$ corresponding to the dependent columns of $TA$. This gives you a solution of $TAx=0$. Since $T$ is invertible, it is also a solution of $Ax=0$. For this $x$ the expression $Ax$ is a linear combination of the columns of $A$ that is equal to zero and the coefficients of the dependent columns are non-zero. So, the equation $Ax=0$ expresses each of the dependent columns in terms of all the other columns.

So, the dependent columns are linearly dependent of the columns with echelon in them (independent columns).

$\endgroup$
2
  • $\begingroup$ Thanks for the extended explanation. $\endgroup$
    – user37344
    Feb 18 at 16:36
  • $\begingroup$ Though you did not answer the question, this was very helpful to me in implementing my solution in a better way. $\endgroup$
    – user37344
    Feb 24 at 18:39

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.