Reduced row echelon form: Difference between revisions

{{wikipedia|Rref#Pseudocode}}

{{task|Matrices}}

{{trans|Python}}

 

V lead = 0

V rowCount = M.len

 

L(rw) mtx

 

{{out}}

=={{header|360 Assembly}}==

{{trans|BBC BASIC}}

RREF CSECT

USING RREF,R12

PG DC CL48' '

YREGS

{{out}}

<pre>

Therefore return this statements are returning the Matrix object itself.

 

var lead:uint, i:uint, j:uint, r:uint = 0;

 

}

return this;

 

=={{header|Ada}}==

matrices.ads:

type Element_Type is private;

Zero : Element_Type;

array (Positive range <>, Positive range <>) of Element_Type;

function Reduced_Row_Echelon_form (Source : Matrix) return Matrix;

 

matrices.adb:

procedure Swap_Rows (From : in out Matrix; First, Second : in Positive) is

Temporary : Element_Type;

return Result;

end Reduced_Row_Echelon_form;

 

Example use: main.adb:

with Ada.Text_IO;

procedure Main is

Ada.Text_IO.Put_Line ("reduced to:");

Print_Matrix (Reduced);

 

{{out}}

 

=={{header|Aime}}==

{

integer e, f, i, j, lead, r;

 

0;

{{Out}}

<pre> 1 0 0 -8

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has not FORMATted transput, also it generates a call to undefined C external }} -->

MODE VEC = [0]FIELD;

MODE MAT = [0,0]FIELD;

mat repr = $"("n(1 UPB mat-1)(f(vec repr)", "lx)f(vec repr)")"$;

 

{{out}}

<pre>

=={{header|ALGOL W}}==

From the pseudo code.

% replaces M with it's reduced row echelon form %

% M should have bounds ( 0 :: rMax, 0 :: cMax ) %

end for_r

end

{{out}}

<pre>

0.0 1.0 0.0 1.0

0.0 0.0 1.0 -2.0

</pre>

 

=={{header|AutoHotkey}}==

rowCount := M.Count() ; the number of rows in M

columnCount := M.1.Count() ; the number of columns in M

}

return M

, [2 , 3, -1, -11]

, [-2, 0, -3, 22]]

}

MsgBox % output

{{out}}

<pre>1 0 0 -8

 

=={{header|AutoIt}}==

Global $ivMatrix[3][4] = [[1, 2, -1, -4],[2, 3, -1, -11],[-2, 0, -3, 22]]

ToReducedRowEchelonForm($ivMatrix)

Return $matrix

EndFunc ;==>ToReducedRowEchelonForm

{{out}}

<pre>[1,0,0,-8]

[-0,-0,1,-2]</pre>

 

{{works with|BBC BASIC for Windows}}

matrix() = 1, 2, -1, -4, \

\ 2, 3, -1, -11, \

lead% += 1

NEXT r%

{{out}}

<pre>

 

=={{header|C}}==

#define TALLOC(n,typ) malloc(n*sizeof(typ))

 

MtxDisplay(m1);

return 0;

 

=={{header|C sharp|C#}}==

 

namespace rref

}

}

 

=={{header|C++}}==

 

{{works with|g++|4.1.2 20061115 (prerelease) (Debian 4.1.1-21)}}

#include <cstddef>

#include <cassert>

 

return EXIT_SUCCESS;

{{out}}

<pre>

=={{header|Common Lisp}}==

Direct implementation of the pseudo-code given.

(let* ((dimensions (array-dimensions matrix))

(row-count (first dimensions))

(* scale (aref matrix r c))))))

(incf lead))

 

=={{header|D}}==

 

void toReducedRowEchelonForm(T)(T[][] M) pure nothrow @nogc {

A.toReducedRowEchelonForm;

writefln("%(%(%2d %)\n%)", A);

{{out}}

<pre> 1 0 0 -8

0 1 0 1

0 0 1 -2</pre>

 

=={{header|Euphoria}}==

integer lead,rowCount,columnCount,i

sequence temp

{ { 1, 2, -1, -4 },

{ 2, 3, -1, -11 },

 

{{out}}

 

=={{header|Factor}}==

{{out}}

<pre>

 

=={{header|Fortran}}==

implicit none

contains

deallocate(trow)

end subroutine to_rref

 

use rref

implicit none

end do

 

 

=={{header|FreeBASIC}}==

Include the code from [[Matrix multiplication#FreeBASIC]] because this function uses the matrix type defined there and I don't want to reproduce it all here.

 

 

sub rowswap( byval M as Matrix, i as uinteger, j as uinteger )

next j

print

{{out}}

<pre>

===2D representation===

From WP pseudocode:

 

import "fmt"

lead++

}

{{out}} (not so pretty, sorry)

<pre>

 

===Flat representation===

 

import "fmt"

m.rref()

m.print("Reduced:")

{{out}}

<pre>

Options are provided for both ''partial pivoting'' and ''scaled partial pivoting''.

The default option is no pivoting at all.

NONE({ i, it -> 1 }),

PARTIAL({ i, it -> - (it[i].abs()) }),

}

matrix

 

This test first demonstrates the test case provided, and then demonstrates another test case designed to show the dangers of not using pivoting on an otherwise solvable matrix. Both test cases exercise all three pivoting options.

 

println "Tests for matrix A:"

println "pivoting == Pivoting.SCALED"

reducedRowEchelonForm(matrixCopy(b), Pivoting.SCALED).each { println it }

 

{{out}}

This program was produced by translating from the Python and gradually refactoring the result into a more functional style.

 

 

rref :: Fractional a => [[a]] -> [[a]]

{- Replaces the element at the given index. -}

replace n e l = a ++ e : b

 

=={{header|Icon}} and {{header|Unicon}}==

 

Works in both languages:

tM := [[ 1, 2, -1, -4],

[ 2, 3, -1,-11],

procedure showMat(M)

every r := !M do every writes(right(!r,5)||" " | "\n")

 

{{out}}

 

=={{header|J}}==

 

NB. form: (row,col) pivot M

pivot=: dyad define

end.

mtx

 

'''Usage:'''

]A=: 1 2 _1 _4 , 2 3 _1 _11 ,: _2 0 _3 22

1 2 _1 _4

1 0 0 _8

0 1 0 1

 

Additional examples, recommended on talk page:

 

gauss_jordan 2 0 _1 0 0,1 0 0 _1 0,3 0 0 _2 _1,0 1 0 0 _2,:0 1 _1 0 0

1 0 0 0 _1

1 0

0 1

 

And:

 

1 0 0 0 0 0 1 0 0 0 0 _1 0 0 0 0 0 0

1 0 0 0 0 0 0 1 0 0 0 0 _1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0.512821

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

 

=={{header|Java}}==

''This requires Apache Commons 2.2+''

import java.lang.Math;

import org.apache.commons.math.fraction.Fraction;

System.out.println("after\n" + a.toString() + "\n");

}

 

=={{header|JavaScript}}==

{{works with|SpiderMonkey}} for the <code>print()</code> function.

Extends the Matrix class defined at [[Matrix Transpose#JavaScript]]

Matrix.prototype.toReducedRowEchelonForm = function() {

var lead = 0;

[ 3, 3, 0, 7]

]);

{{out}}

<pre>1,0,0,-8

0,1,0,1.666666666666667

0,0,1,1</pre>

 

=={{header|Julia}}==

 

=={{header|Kotlin}}==

 

typealias Matrix = Array<DoubleArray>

m.printf("Reduced row echelon form:")

}

 

{{out}}

 

=={{header|Lua}}==

local lead = 1

local n_rows, n_cols = #M, #M[1]

end

io.write( "\n" )

{{out}}

<pre>1 0 0 -8

=={{header|M2000 Interpreter}}==

low bound 1 for array

Module Base1 {

dim base 1, A(3, 4)

}

Base1

 

Low bound 0 for array

 

Module base0 {

dim base 0, A(3, 4)

}

base0

 

=={{header|Maple}}==

 

with(LinearAlgebra):

 

ReducedRowEchelonForm(<<1,2,-2>|<2,3,0>|<-1,-1,-3>|<-4,-11,22>>);

{{out}}

<pre>

</pre>

 

 

=={{header|MATLAB}}==

 

=={{header|Maxima}}==

k:min(p,q),

for i thru min(p,q) do (if a[i,i]=0 then (k:i-1,return())),

 

rref(a);

 

=={{header|Nim}}==

===Using rationals===

To avoid rounding issues, we can use rationals and convert to floats only at the end.

 

type Fraction = Rational[int]

runTest(m2)

runTest(m3)

 

{{out}}

===Using floats===

When using floats, we have to be careful when doing comparisons. The previous program adapted to use floats instead of rationals may give wrong results. This would be the case with the second matrix. To get the right result, we have to do a comparison to an epsilon rather than zero. Here is the program modified to work with floats:

 

const Eps = 1e-10

runTest(m2)

runTest(m3)

 

{{Out}}

 

=={{header|Objeck}}==

class RowEchelon {

function : Main(args : String[]) ~ Nil {

}

}

 

=={{header|OCaml}}==

let tmp = m.(i) in

m.(i) <- m.(j);

) row;

print_newline()

 

Another implementation:

let nr, nc = Array.length m, Array.length m.(0) in

let add r s k =

print_newline();

rref mat;

 

=={{header|Octave}}==

refA = rref(A);

 

=={{header|PARI/GP}}==

my(d=matsize(M));

if(d[1]+1 != d[2], error("Bad size in rref"), d=d[1]);

concat(matid(d), matsolve(matrix(d,d,x,y,M[x,y]), M[,d+1]))

Example:

{{out}}

<pre>%1 =

{{trans|Python}}

Note that the function defined here takes an array reference, which is modified in place.

{our @m; local *m = shift;

@m or return;

 

rref(\@m);

{{out}}

<pre> 1 0 0 -8

=={{header|Phix}}==

{{Trans|Euphoria}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">ToReducedRowEchelonForm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">M</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">{</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">11</span> <span style="color: #0000FF;">},</span>

<span style="color: #0000FF;">{</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22</span> <span style="color: #0000FF;">}</span> <span style="color: #0000FF;">})</span>

{{out}}

<pre>

{{works with|PHP|5.x}}

{{trans|Java}}

 

function rref($matrix)

return $matrix;

}

 

=={{header|PicoLisp}}==

(let (Lead 1 Cols (length (car Mat)))

(for (X Mat X (cdr X))

(car X) ) ) ) )

(T (> (inc 'Lead) Cols)) ) )

{{out}}

<pre>(reducedRowEchelonForm

=={{header|Python}}==

 

if not M: return

lead = 0

 

for rw in mtx:

 

=={{header|R}}==

{{trans|Fortran}}

pivot <- 1

norow <- nrow(m)

-2, 0, -3, 22), 3, 4, byrow=TRUE)

print(m)

 

=={{header|Racket}}==

#lang racket

(require math)

[2 3 -1 -11]

[-2 0 -3 22]]))

{{out}}

<pre>

=={{header|Raku}}==

(formerly Perl 6)

 

for ^$rows -> $r {

my $i = $r;

until @m[$i;$lead] {

$i = $r;

}

@m[$i, $r] = @m[$r, $i] if $r != $i;

for ^$rows -> $n {

next if $n == $r;

}

++$lead;

sub rat-or-int ($num) {

return $num unless $num ~~ Rat;

$num.nude.join: '/';

}

say_it( 'Reduced Row Echelon Form Matrix', rref(@matrix) );

say "\n";

 

Raku handles rational numbers internally as a ratio of two integers

 

{{out}}

Original Matrix

1 2 -1 -4

0 1 0 1

0 0 1 -2

 

Original Matrix

0 1 0 -217/6

0 0 1 -125/6

 

Original Matrix

0 0 0 0 0 0

0 0 0 0 0 0

 

Original Matrix

</pre>

 

and

 

 

my @M = (

);

 

}

 

 

 

}

}

);

 

 

=={{header|REXX}}==

''Reduced Row Echelon Form'' &nbsp; (a.k.a. &nbsp; ''row canonical form'') &nbsp; of a matrix, with optimization added.

cols= 0; w= 0; @. =0 /*max cols in a row; max width; matrix.*/

mat.=; mat.1= ' 1 2 -1 -4 '

end /*c*/

say _ /*display a matrix row to the terminal.*/

{{out|output|text=&nbsp; when using the default (internal) input:}}

<pre>

 

=={{header|Ring}}==

# Project : Reduced row echelon form

 

lead = lead + 1

next

Output:

<pre>

0 1 0 1

0 0 1 -2

</pre>

 

=={{header|Ruby}}==

{{works with|Ruby|1.9.3}}

def reduced_row_echelon_form(ary)

lead = 0

reduced = reduced_row_echelon_form(mtx)

print_matrix reduced

 

{{out}}

0.0 0.0 1.0 1.0

</pre>

=={{header|Rust}}==

{{trans|FORTRAN}}

I have tried to avoid state mutation with respect to the input matrix and adopt as functional a style as possible in this translation, so for larger matrices one may want to consider memory usage implications.

fn main() {

let mut matrix_to_reduce: Vec<Vec<f64>> = vec![vec![1.0, 2.0 , -1.0, -4.0],

let column_count = matrix_out[0].len();

if column_count <= pivot {

break;

if column_count == pivot {

pivot = pivot - 1;

}

}

matrix_out

}

Output:

<pre>

[[1.0, 0.0, 0.0, -8.0], [-0.0, 1.0, 0.0, 1.0], [-0.0, -0.0, 1.0, -2.0]]

</pre>

=={{header|Sage}}==

{{works with|Sage|4.6.2}}

sage: m.rref()

[ 1 0 0 -8]

[ 0 1 0 1]

 

=={{header|Scheme}}==

{{Works with|Scheme|R<math>^5</math>RS}}

(define (clean-down matrix from-row column)

(cons (car matrix)

indices)

indices)

Example:

(list (list 1 2 -1 -4) (list 2 3 -1 -11) (list -2 0 -3 22)))

 

(display (reduced-row-echelon-form matrix))

{{out}}

 

=={{header|Seed7}}==

 

const proc: toReducedRowEchelonForm (inout matrix: mat) is func

end for;

end for;

 

Original source: [http://seed7.sourceforge.net/algorith/math.htm#toReducedRowEchelonForm]

=={{header|Sidef}}==

{{trans|Raku}}

var (j, rows, cols) = (0, M.len, M[0].len)

say_it('Reduced Row Echelon Form Matrix', rref(matrix));

say '';

{{out}}

<pre>

 

=={{header|Swift}}==

var lead = 0

for r in 0..<rows {

lead += 1

}

 

=={{header|Tcl}}==

Using utility procs defined at [[Matrix Transpose#Tcl]]

namespace path {::tcl::mathop ::tcl::mathfunc}

 

set m {{1 2 -1 -4} {2 3 -1 -11} {-2 0 -3 22}}

print_matrix $m

{{out}}

<pre> 1 2 -1 -4

=={{header|TI-83 BASIC}}==

Builtin function: rref()

{{out}}

<pre>

 

=={{header|TI-89 BASIC}}==

 

Output (in prettyprint mode): <math>\begin{bmatrix} 1&0&0&-8 \\ 0&1&0&1 \\ 0&0&1&-2 \end{bmatrix}</math>

These are all combined in the main rref function.

 

#import flo

 

<1.,2.,-1.,-4.>,

<2.,3.,-1.,-11.>,

{{out}}

<pre>

This solution is applicable only if the input

is a non-singular augmented square matrix.

 

 

=={{header|VBA}}==

Dim lead As Integer: lead = 0

Dim rowCount As Integer: rowCount = UBound(M)

Debug.Print Join(r(i), vbTab)

Next i

<pre>1 0 0 -8

0 1 0 1

=={{header|Visual FoxPro}}==

Translation of Fortran.

CLOSE DATABASES ALL

LOCAL lnRows As Integer, lnCols As Integer, lcSafety As String

ACOPY(m1, m2, e1, n, e2)

ENDPROC

{{out}}

<pre>

{{libheader|Wren-matrix}}

The above module has a method for this built in as it's needed to implement matrix inversion using the Gauss-Jordan method. However, as in the example here, it's not just restricted to square matrices.

 

var m = Matrix.new([

System.print("\nRREF:\n")

m.toReducedRowEchelonForm

 

{{out}}

| 0 0 1 -2|

</pre>

 

=={{header|zkl}}==

The "best" way is to use the GNU Scientific Library:

fcn toReducedRowEchelonForm(M){ // in place

lead,rows,columns := 0,M.rows,M.cols;

}

M

2, 3, -1, -11,

-2, 0, -3, 22);

{{out}}

<pre>

Or, using lists of lists and direct implementation of the pseudo-code given,

lots of generating new rows rather than modifying the rows themselves.

lead,rowCount,columnCount := 0,m.len(),m[1].len();

foreach r in (rowCount){

}//foreach

m

T( 2, 3, -1, -11,),

T(-2, 0, -3, 22,));

 

fcn printM(m){ m.pump(Console.println,rowFmt) }

{{out}}

<pre>