-3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 9
    $\begingroup$ Gaussian elimination? $\endgroup$
    – JBL
    Commented Dec 9, 2010 at 15:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Thierry Zell
    Commented Dec 9, 2010 at 19:41
  • 5
    $\begingroup$ After edit: Gaussian elimination? $\endgroup$
    – JBL
    Commented Dec 9, 2010 at 22:33
  • $\begingroup$ 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. $\endgroup$
    – dsimcha
    Commented Dec 10, 2010 at 0:05
  • $\begingroup$ This sort of question is better suited for math.stackexchange.com $\endgroup$
    – S. Carnahan ♦
    Commented Dec 10, 2010 at 4:46

1 Answer 1

Reset to default
2
$\begingroup$

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

The algorithm you're looking for is Gaussian elimination.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .