Reduced row echelon form

[Robert Young-9]

Hi,

Is there a method in NumPy that reduces a matrix to it's reduced row echelon form? I'm brand new to both NumPy and linear algebra, and I'm not quite sure where to look.

Thanks
Rob

_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion

[Robert Kern-2]

On Tue, Nov 18, 2008 at 14:21, Robert Young <[hidden email]> wrote:
> Hi,
>
> Is there a method in NumPy that reduces a matrix to it's reduced row echelon
> form? I'm brand new to both NumPy and linear algebra, and I'm not quite sure
> where to look.

No, we don't have a function to do that. What do you need it for?
While many linear algebra books talk about it, I have never seen a
practical use for it outside of manual matrix computations.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless
enigma that is made terrible by our own mad attempt to interpret it as
though it had an underlying truth."
  -- Umberto Eco
_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion

[Anne Archibald-2]

2008/11/18 Robert Young <[hidden email]>:

> Is there a method in NumPy that reduces a matrix to it's reduced row echelon
> form? I'm brand new to both NumPy and linear algebra, and I'm not quite sure
> where to look.

Unfortunately, reduced row-echelon form doesn't really work when using
approximate values: any construction of the reduced row-echelon form
forces you many times to ask "is this number exactly zero or just very
small?"; if it's zero you do one thing, but if it's very small you do
something totally different - usually divide by it. With
floating-point numbers, every calculation is approximate, and such a
method will blow up completely. If you really need reduced row echelon
form, you have to start with exact numbers and use a package that does
exact computations (I think SymPy might be a place to start).

In practice, numerical linear algebra is rather different from linear
algebra as presented in math classes. In particular, problems that you
might solve on the chalkboard with row reduction or the like are
instead solved by matrix factorizations of special forms. For example
LU factorization writes a matrix as a product of a lower-triangular
matrix and an upper-triangular matrix. This allows, for example, very
easy calculation of determinants. (It also allows fast solution of
linear equations, just like reduced row echelon form.) But LU
factorization is much more resistant to the problems involved in
working with approximate numbers.

If you have a problem that is classically solved with something like
reduced row echelon form, you first need to think about how to make it
make sense in an approximate setting. For example, the rank of a
matrix: if two rows are exactly equal, the matrix is singular. But if
the rows are even slightly different, the matrix is non-singular.
There's just no way to make this work precisely using approximate
numbers. (Sometimes you can rephrase the problem in a way that does
work; singular value decomposition lets you deal with ranks in a
sensible fashion, by giving a reasonable criterion for when you want
to consider a linear combination equal to zero.) If, however, your
question makes sense with approximate numbers (solving Ax=b usually
does, for example) but your algorithm for getting the answer doesn't
work, look for a numerical matrix decomposition that will work. The
singular value decomposition is the swiss army knife for this sort of
problem, but others can work better in some cases.

Numerical Recipes is the traditional book to recommend in this sort of
case. Their algorithms may not be the best, and don't use their code,
but their descriptions do instill a sensible caution.

Good luck,
Anne
_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion

[Jason Grout-5]

Anne Archibald wrote:

> 2008/11/18 Robert Young <[hidden email]>:
>
>  
>> Is there a method in NumPy that reduces a matrix to it's reduced row echelon
>> form? I'm brand new to both NumPy and linear algebra, and I'm not quite sure
>> where to look.
>>    
>
> Unfortunately, reduced row-echelon form doesn't really work when using
> approximate values: any construction of the reduced row-echelon form
> forces you many times to ask "is this number exactly zero or just very
> small?"; if it's zero you do one thing, but if it's very small you do
> something totally different - usually divide by it. With
> floating-point numbers, every calculation is approximate, and such a
> method will blow up completely. If you really need reduced row echelon
> form, you have to start with exact numbers and use a package that does
> exact computations (I think SymPy might be a place to start).
>  

I also recommend Sage here (http://www.sagemath.org).  For example, here
is a session in which we calculate the reduced echelon form of a matrix
over the rationals (QQ):

sage: a=matrix(QQ,[[1,2,3],[4,5,6],[7,8,9]])
sage: a.echelon_form()
[ 1  0 -1]
[ 0  1  2]
[ 0  0  0]

Sage has quite a bit of advanced functionality for exact linear
algebra.  (It also uses numpy as a backend to provide some nice
functionality for approximate linear algebra).  Here is a short tutorial
on constructions in linear algebra:  
http://sagemath.org/doc/const/node28.html

Jason

_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion

[Stéfan van der Walt]

Hi Robert,

2008/11/18 Robert Young <[hidden email]>:
> Is there a method in NumPy that reduces a matrix to it's reduced row echelon
> form? I'm brand new to both NumPy and linear algebra, and I'm not quite sure
> where to look.

I use the Sympy package.  It is small, easy to install, runs on pure
Python, and gets the job done:

>>> x = np.random.random((3,3))
>>> import sympy
>>> sympy.Matrix(x).rref()
([1, 0, 0]
[0, 1, 0]
[0, 0, 1], [0, 1, 2])

If you are interested, I can also provide you with a version that runs
under pure NumPy, using the LU-decomposition.

Cheers
Stéfan
_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion

[Robert Young-9]

Excellent, thank you all for your input. I don't actually have a specific problem that I need it for I just wanted to be able to work through some book examples. I'll take a look at Sage and Sympy.

Thanks
Rob

On Wed, Nov 19, 2008 at 10:14 AM, Stéfan van der Walt <[hidden email]> wrote:

Hi Robert,

2008/11/18 Robert Young <[hidden email]>:

> Is there a method in NumPy that reduces a matrix to it's reduced row echelon
> form? I'm brand new to both NumPy and linear algebra, and I'm not quite sure
> where to look.

I use the Sympy package.  It is small, easy to install, runs on pure
Python, and gets the job done:

>>> x = np.random.random((3,3))
>>> import sympy
>>> sympy.Matrix(x).rref()
([1, 0, 0]
[0, 1, 0]
[0, 0, 1], [0, 1, 2])

If you are interested, I can also provide you with a version that runs
under pure NumPy, using the LU-decomposition.

Cheers
Stéfan

_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion

_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion