Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have an NxN matrix of linear constraints that is not of full rank. In other words, some of the constraints are linear combinations of other constraints. The "standard" linear algebra tools (determinants, matrix inversion, etc.) seem to only be useful for testing for linear dependence. I'd like to not only discover the existence of redundant constraints but figure out which constraints can be written as linear combinations of other constraints and remove the redundant constraints to obtain the largest linearly independent set of constraints possible. What's a reasonable algorithm to do this?

Edit: Since a lot of the details of my problem seem to be more relevant than I thought they would be (I only use linear algebra occasionally and am not very good at discussing it), here they are:

  1. I have a concrete matrix, i.e. one with actual numbers, no variables.

  2. If the matrix is viewed as a system of linear equations, i.e. ax = b, all the numbers in my a matrix are either 1 or 0.

  3. I want an algorithm that's easy to implement in computer code, preferably one that reduces to a few Numpy calls, though I'm willing to write from-scratch code if necessary.

  4. Ideally, it should work for an NxM matrix where N >= M, not just where N = M.

share|improve this question
Gaussian elimination? –  JBL Dec 9 '10 at 15:58
Determinants are not the standard toolkit when grappling with a concrete matrix: row and column operations are. Now, your question is not clear, because you did not specify whether you're dealing with a concrete matrix or with a genuine NxN matrix for arbitrary N, so it's hard to give you a helpful answer. –  Thierry Zell Dec 9 '10 at 19:41
After edit: Gaussian elimination? –  JBL Dec 9 '10 at 22:33
Researched Gaussian elim more, does what I need. Thanks. Too bad you didn't make it a full answer, or I would have accepted it. –  dsimcha Dec 10 '10 at 0:05
This sort of question is better suited for math.stackexchange.com –  S. Carnahan Dec 10 '10 at 4:46
add comment

closed as too localized by Ryan Budney, Andres Caicedo, Andy Putman, Pete L. Clark, S. Carnahan Dec 10 '10 at 3:29

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 2 down vote accepted

At sort-of request of the author, I'm making my comment into an answer:

The algorithm you're looking for is Gaussian elimination.

share|improve this answer
add comment

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