@Carl Love Thanks for all annotations.

@Kitonium I don't know why these matrices shall not work properly? I tested them all and i got a reduced form. What was your output?

@acer You are totally right. I nedd to fix perm. Also my declaration of my vairables which are type of integer or nonigennt seems to be wrong. I think thats caused the wrong output. With the help of @Carl Love tip to use trace (i didnt know there is something like this. thanks!) I could fix my code. 

I compared my procedure reduced with the existing procedure reducedRowEchelonForm(), but unfortunately it is not equal to it. I show it at the end.

Here is my new code:

with(LinearAlgebra):
multiplikation:= proc(m,n,a,b)
local M:= Matrix(m,n),i,j;
for i from 1 to m do
for j from 1 to n do
if not(i=j) then
M[i,j]:=0;
elif i=j and not(i=a) then
M[i,j]:=1;
else
M[i,j]:=b;
end if;
end do;
end do;
return M;
end proc:

addition:= proc(m,n,a,b,c)
local M:= Matrix(m,n),i,j;
for i from 1 to m do
for j from 1 to n do
if ((i=a) and (j=b)) then
M[i,j]:=c;
elif (not(i=a) or not(j=b)) then
if i=j then
M[i,j]:=1;
else
M[i,j]:=0;
end if;
end if;
end do;
end do;
return M;
end proc:

perm:= proc(m,n,a,b)
local M:= Matrix(m,n),i,j;
if a=b then
return IdentityMatrix(m);
else
for i from 1 to m do
for j from 1 to n do
if ((i=a and j=a) or (i=b and j=b)) then
M[i,j]:=0;
elif ((i=a and j=b) or (i=b and j=a)) then
M[i,j]:= 1;
else
if ((i=j and not(i=a)) and (i=j and not(i=b))) then
M[i,j]:=1;
elif (not(i=j) and not(i=a) and not(i=b) and not(j=a) and not(j=b)) then
M[i,j]:=0;
end if;
end if;
end do;
end do;
end if:
return M;
end proc:

with(LinearAlgebra):
reduced:=proc(B)
uses LinearAlgebra;
local M:=B, l:=1, m:=RowDimension(M),n:=ColumnDimension(M),i,j; # l zeigt aktuelle Spalte an
for i from 1 to m do # gehe alle Zeilen durch
if n<l then # da l Startindex muss dieser kleiner/gleich als Spaltennummer sein, sonst sind wir fertig
return M;
end if;
j:=i; # arbeite mit aktueller Zeilennummer i
while M[j,l]=0 do # suche ersten Zeileneintrag ungleich Null in Spalte l
j:=j+1;
if m<j then # Zeile zu Ende, gehe in nächste Spalte und suche dort
j:=i;
l:=l+1;
if n<l then # sind am Ende angekommen, dann gebe M aus
return M;
end if;
end if;
end do;
M:= perm(m,m,j,i).M; # Vertausche Zeile j mit erster Zeile i
if not(M[i,l]=0) then # Multipliziere Zeile i mit M[i,l])^(-1),aber nur wenn wir NICHT durch 0 teilen, sonst nicht nötig
M:= multiplikation(m,m,i,(M[i,l])^(-1)).M;
end if;
for j from 1 to m do # Subtrahiere jede Zeile j mit Zeile i um das M[j,l]-fache
if not(j=i) then
M:= addition(m,m,j,i,(-1)*M[j,l]).M;
end if;
end do;
l:=l+1; # erhöhe l um 1, damit wir nächste Spalte untersuchen, neue Iteration in for-Schleife bewirkt, dass wir auch i eins erhöhen und so auch eine Zeile "tiefer" starten
end do;
return M;
end proc:

I tested it a few times (including the trace command). It seems to work. 

I tried now to compare it to the existing ReducedRowEchelonForm command:

for i from 1 to 10 do
for n from 3 to 10 do
for m from 3 to 10 do
X := Matrix(n,m,rand(-10..10));
if(not(Equal(ReducedRowEchelonForm(X),Gauss(X)))) then
print(X);
fi;
od;
od;
od;

Unfortunately it prints lots of Matrices... I will probably work tomorrow on it, maybe i find the issue.

But thank you guys so far!!

@Carl Love  

with(LinearAlgebra):
reduced:=proc(B)
uses LinearAlgebra;
local M:=B, l:=1, m:=RowDimension(M),n:=ColumnDimension(M),i,j; # l is current column
for i from 1 to m do # going through every row item 
if n<l then # l needs to be less than column number n
return M;
end if;
j:=i; # initialize current row number
while M[j,l]=0 do # search for first row item unequal zero
j:=j+1;
if m<j then # end of row, go to next column
j:=i;
l:=l+1;
if n<l then # end of column and row
return M;
end if;
end if;
end do;
M:= perm(m,m,j,i).M; # permutate row j and row i
if not(M[i,l]=0) then # multiply row i with M[i,l])^(-1), if it is not zero
M:= multiplikation(m,m,i,(M[i,l])^(-1)).M;
end if;
for j from 1 to m do # Subtract each row j with row i for M[j,l]-times
if not(j=i) then
M:= addition(m,m,j,i,(-1)*M[j,l]).M;
end if;
end do;
l:=l+1; # increase l by 1, next iteration i increase either
end do;
end proc:

------------------------------------------------------------------------------------

My elementary matrices are working. (i created them before the main program, so some of the variables are unnecessary)

with(LinearAlgebra):

multiplikation:= proc(m,n,a::nonnegint,b::integer)
local M:= Matrix(m,n),i,j;
for i from 1 to m do
for j from 1 to n do
if not(i=j) then
M[i,j]:=0;
elif i=j and not(i=a) then
M[i,j]:=1;
else
M[i,j]:=b;
end if;
end do;
end do;
return M;
end proc:

addition:= proc(m,n,a::nonnegint,b::nonnegint,c::integer)
local M:= Matrix(m,n),i,j;
for i from 1 to m do
for j from 1 to n do
if ((i=a) and (j=b)) then
M[i,j]:=c;
elif (not(i=a) or not(j=b)) then
if i=j then
M[i,j]:=1;
else
M[i,j]:=0;
end if;
end if;
end do;
end do;
return M;
end proc:

perm:= proc(m,n,a::nonnegint,b::nonnegint)
local M:= Matrix(m,n),i,j;
for i from 1 to m do
for j from 1 to n do
if ((i=a and j=a) or (i=b and j=b)) then
M[i,j]:=0;
elif ((i=a and j=b) or (i=b and j=a)) then
M[i,j]:= 1;
else
if ((i=j and not(i=a)) and (i=j and not(i=b))) then
M[i,j]:=1;
elif (not(i=j) and not(i=a) and not(i=b) and not(j=a) and not(j=b)) then
M[i,j]:=0;
end if;
end if;
end do;
end do;
return M;
end proc:

-----------------------------------------------------------------------------------------

@Carl Love  Thank you that helps me. I'm able to compile my procedure, but I dont get what i except.:

L:=Matrix(3,3,[1,2,5,4,5,6,7,8,9]);

M:=Matrix(2,3,[1,2,5,4,5,6]);

reduced(L);

4

reduced(M);

3

technically i have to get a matrix back, but i receive an integer. Maybe i did something wrong with my elementary matrices. I'll present it to you if i'll fix it.