Message Boards

WOLFRAM COMMUNITY

13522 Views

7 Replies

3 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Mathematics Algebra Wolfram Language

Gaussian elimination to row echelon form, not reduced row echelon form?

D P

Posted 10 years ago

Hi all. How can I get Mathematica to perform Gaussian elimination on a matrix to get it to row echelon form, but not reduced row echelon form? I don't want all the leading variables to be 1. Mathematica seems to only have the "RowReduced" function, which results in a reduced row echelon form. Thanks in advance. D

POSTED BY: D P

7 Replies

Sort By:

Daniel Lichtblau

Daniel Lichtblau, Wolfram Research

Posted 10 years ago

You can use `LUDecomposition`. I'll show a simple example. mat = RandomInteger[{-10, 10}, {3, 5}] {lu, p, c} = LUDecomposition[mat] u = Normal[luSparseArray[{i_, j_} /; j >= i -> 1, Dimensions[mat]]] ( Out[417]= {{-8, 0, 2, 6, -7}, {1, -1, 10, 4, -2}, {9, -1, 0, -7, 4}} Out[418]= {{{1, -1, 10, 4, -2}, {-8, -8, 82, 38, -23}, {9, -1, -8, -5, -1}}, {2, 1, 3}, 0} Out[419]= {{1, -1, 10, 4, -2}, {0, -8, 82, 38, -23}, {0, 0, -8, -5, -1}} ) The result will be dependent on the permutation that was used in forming the LU decomposition. --- edit 2024-06-14 --- We now have UpperTriangularDecomposition in the Wolfram Function Repository. It returns an upper-triangularized form and the corresponding conversion matrix. Example: mat = RandomInteger[{-10, 10}, {3, 5}] {uu, conv} = ResourceFunction["UpperTriangularDecomposition"][mat] ( Out[125]= {{-10, 3, 8, 3, 9}, {8, 9, -3, 1, -5}, {-1, -8, 2, 2, -7}} Out[126]= {{{-10, 3, 8, 3, 9}, {0, -114, -34, -34, -22}, {0, 0, -419, -476, 718}}, {{1, 0, 0}, {-8, -10, 0}, {-55, -83, -114}}} ) Check: conv . mat == uu ( Out[127]= True *) --- end edit ---

You can use LUDecomposition. I'll show a simple example.

mat = RandomInteger[{-10, 10}, {3, 5}]
{lu, p, c} = LUDecomposition[mat]
u = Normal[lu*SparseArray[{i_, j_} /; j >= i -> 1, Dimensions[mat]]]

(* Out[417]= {{-8, 0, 2, 6, -7}, {1, -1, 10, 4, -2}, {9, -1, 0, -7, 4}}

Out[418]= {{{1, -1, 10, 4, -2}, {-8, -8, 82, 
   38, -23}, {9, -1, -8, -5, -1}}, {2, 1, 3}, 0}

Out[419]= {{1, -1, 10, 4, -2}, {0, -8, 82, 38, -23}, {0, 
  0, -8, -5, -1}} *)

The result will be dependent on the permutation that was used in forming the LU decomposition.

--- edit 2024-06-14 ---

We now have UpperTriangularDecomposition in the Wolfram Function Repository. It returns an upper-triangularized form and the corresponding conversion matrix. Example:

mat = RandomInteger[{-10, 10}, {3, 5}]
{uu, conv} = ResourceFunction["UpperTriangularDecomposition"][mat]

(* Out[125]= {{-10, 3, 8, 3, 9}, {8, 9, -3, 1, -5}, {-1, -8, 2, 2, -7}}

Out[126]= {{{-10, 3, 8, 3, 9}, {0, -114, -34, -34, -22}, {0, 0, -419, -476, 718}}, {{1, 0, 0}, {-8, -10, 0}, {-55, -83, -114}}} *)

Check:

conv . mat == uu

(* Out[127]= True *)

--- end edit ---

POSTED BY: Daniel Lichtblau

D P

Posted 10 years ago

Thanks a lot for your reply, Daniel. It would be great if Mathematica had a Gaussian elimination function, as well as a Gauss-Jordan elimination function. Maple has both of these options. Gaussian elimination stops once the matrix is in row echelon form(back substitution can be used to solve for variables, if necessary), Gauss-Jordan continues until the matrix is in reduced row echelon form.

POSTED BY: D P

Daniel Lichtblau

Daniel Lichtblau, Wolfram Research

Posted 10 years ago

But why might such a function be useful? It's not a unique form and moreover I'm not sure what one might do with the result. The RREF, by contrast, can be (and, internally, is) used for finding solutions to linear equations, null space generators, inverses, and maybe more. I guess what I am asking is in what way does the non-reduced echelon form offer any advantage over an LU decomposition?

POSTED BY: Daniel Lichtblau

D P

Posted 10 years ago

Sometimes it is not necessary to have a matrix in RREF, only in REF. So if I am doing a matrix reduction by hand and stop at REF, then I would like Mathematica to be able to also stop at REF, so that I can check my calculations. In what instances would I stop at REF when doing calculations by hand? 1. Sometimes it is faster for me to use back substitution(to get the solution) than to get a matrix to RREF. 2. Another example is for finding the basis for a column space or row space . 3. To deduce whether a system of equations has 0, 1 or infinitely many solutions I want to use Mathematica to check calculations that I've done by hand(I don't want Mathematica give me a reduced answer). But if I stop at REF, and Mathematica stops at RREF, then I can't use it to check whether my row reductions are correct(without me doing further unnecessary calculations). Much of my coursework involves matrices in REF. Maple has the option to get a matrix to REF and/or RREF, and I found this feature very useful. As a new user of Mathematica, the solution in your first reply, while it did generate a REF, it is not a trivial solution for a beginner . I don't even know what "LU decomposition" is. If your solution can be packaged as a clickable function in Mathematica, then that would be much easier and quicker to implement. Anyway, that's all the time I want to devote to this topic. I think that I can probably explain myself a bit better, but I have neither the time or the inclination. Thanks for your replies. :)

POSTED BY: D P

Gaurav Khanna

Gaurav Khanna, Three Sigma Capital

Posted 5 years ago

I realize this is an old thread, but I agree with D P. I am learning linear algebra and would like to just see the matrix in Upper triangular or REF form -- not in the complete row-reduced (RREF) form. Many textbooks also make this distinction (such as Strang's textbook).