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:

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

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

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

notthe 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