Commands

Off[General::"spell1"]

\(\(\(Clear[LeadZ, LeadT, row];\)\(
\)
    \)\)
\(\(\(LeadZ[row_] := 
        Module[{sr}, sr = Split[row]; 
          If[sr[[1, 1]] == 0, 
            Length[sr[[1]]], 
            0]];\)\(
\)
    \)\)
LeadT[row_] := 
        If[LeadZ[row] == Length[row], 0, 
          row[[LeadZ[row] + 
              1]]];

    
Clear[TestREF, TestSoR, MM, k];

    
TestREF[MM_] := 
        Apply[And, 
          Table[
Or[
              LeadZ[MM[[k]]] < 
                LeadZ[MM[[k + 1]]], 
              LeadZ[MM[[
                    k + 1]]] == 
                Length[MM[[
                    k + 1]]]], {k, 1, 
              Length[MM] - 1}]];

    
TestSoR[MM_] := 
        Apply[And, 
          Table[
LeadZ[
                MM[[k]]] ≤ 
              LeadZ[MM[[k + 1]]], {k, 1, 
              Length[MM] - 1}]];

    
Clear[SortR, MM];

    
SortR[MM_] := 
        Flatten[Map[Sort[#, LeadT[#1] > LeadT[#2] &] &, 
            Split[Sort[MM, LeadZ[#1] < LeadZ[#2] &], 
              LeadZ[#1] == LeadZ[#2] &]], 
          1];


Clear[Fun1, Fun2, MM, sMM, k, fk, m, RM];

    
Fun1[MM_] := 
        Module[{sMM, k, fk}, 
sMM = 
            Sort[MM, LeadZ[#1] < LeadZ[#2] &]; 
If[
            TestREF[sMM], sMM, 
            k = 1; 
While[k = k + 1; 
              LeadZ[sMM[[k - 1]]] < 
                LeadZ[sMM[[
                    k]]],]; 
fk = 
              k; Insert[Delete[sMM, fk], 
              sMM[[fk]] - LeadT[
                        sMM[[fk]]]/LeadT[sMM[[fk - 1]]] 
                  sMM[[fk - 1]], 
              fk]]
];

    
Fun2[MM_] := 
        Module[{k, fk, m, RM}, 
If[
            Not[TestSoR[MM]], 
SortR[
              MM], 
       If[
              TestREF[MM], 
          MM, 
k = 1; 
While[
                LeadZ[MM[[k]]] < 
                  LeadZ[MM[[k + 1]]], 
                k = k + 1]; 
m = k; 
              RM = MM; 
While[
(m < 
                      Length[MM]) && (LeadZ[
                        MM[[k]]] == 
                      LeadZ[MM[[m + 
                            1]]]), 
                RM = Insert[Delete[RM, m + 1], 
                    RM[[m + 
                          1]] - LeadT[
                              RM[[m + 
                                  1]]]/LeadT[
                              RM[[k]]] 
                        RM[[k]], m + 1]; 
                m = m + 1
          ]; 
              RM ]
     ]
];


\(\(\(Clear[TestRREF, MM, tMM];\)\(
\)
    \)\)
TestRREF[MM_] := 
        Module[{tMM}, 
tMM = 
            Transpose[MM]; 
Apply[And, 
            Table[Or[
                Norm[MM[[k]]] == 
                  0, tMM[[LeadZ[
                        MM[[k]]] + 
                      1]] == IdentityMatrix[
                      Length[MM]][[k]]], {k, 1, Length[MM]}]]
];

    
Clear[ReplaceRow, MM, row, n];

    
ReplaceRow[MM_, row_, n_] := 
        Insert[Delete[MM, n], row, 
          n];


\(\(\(Clear[Fun3, MM, tMM, k, m, RM];\)\(
\)
    \)\)
Fun3[MM_] := 
        Module[
{Lead1, tr, k, tMM, TM, 
            m}, 

tMM = Transpose[MM]; 
          Lead1[tr_] := 
            If[Norm[tr] == 0, 
              tr, (1/LeadT)[tr] 
                tr]; 
If[
Apply[And, 
              Table[Or[
                  Norm[MM[[k]]] == 
                    0, LeadT[
                      MM[[k]]] == 
                    1], {k, 1, Length[MM]}]], 
k = 
              Length[MM];  
While[
              k > 0 && Or[
Norm[
                      MM[[k]]] == 
                    0, 
tMM[[LeadZ[
                          MM[[k]]] + 
                        1]] == IdentityMatrix[
                        Length[
                          MM]][[k]]], 
              k = k - 1]; 
m = k;  RM = MM; 
            m = k - 1; 
While[m > 0, 
              RM = ReplaceRow[RM, 
                  RM[[m]] - 
                    MM[[m, 
                        LeadZ[MM[[k]]] + 
                          1]] 
                      MM[[k]], m]; 
              m = m - 1]; 
            RM, 
Map[Lead1[#] &, 
              MM]]
];

    
Clear[Fun4, MM];

    
Fun4[MM_] := 
        If[TestREF[MM], Fun3[MM], Fun2[MM]];

Test the functions defined above

mM = {{0, 0, 1, 2}, {0, 1, 2, 3}, {0, 2, 3, 4}}

Given a row count the leading zeros.

LeadZ[{0, 0, 0, 3, 4}]

LeadZ[mM[[1]]]

Given a row find the leading entry.

LeadT[mM[[1]]]

LeadT[{0, 0, 0}]

LeadZ[{0, 0, 0}]

mM

Decide if a matrix is in row echelon form.

TestREF[mM]

Decide if  the rows of  a matrix are ordered by the number of leading zeros.

TestSoR[mM]

mR = {{1, 2, 3, 4}, {0, 1, 2, 3}, {0, 0, 0, 0}}

TestREF[mR]

TestSoR[mR]

This function tells if the matrix is in reduced row echelon form.

TestRREF[mM]

TestRREF[{{1, 3, 0, 2, 0, 1, 
          4}, 
                {0, 0, 1, 2, 
          0, 1, 3}, 
                {0, 0, 
          0, 0, 1, 1, 
          2}, 
                 {0, 0, 0, 
          0, 0, 0, 0}}]

Here I test sorting of pairs of numbers.

tt = 
      Table[{Random[Integer, {0, 9}], Random[Integer, {0, 9}]}, {k, 1, 
          19}]

Flatten[
      Map[Sort[#, #1[[2]] > #2[[2]] &] &, 
        Split[Sort[
            tt, #1[[1]] > #2[[1]] &], #1[[1]] == #2[[1]] &]], 
      1]

This function sorts rows of a matrix by the number of leading zeros.

mM

SortR[mM]

The following function performs a necessary row reduction. It decides what is the next step.

Fun2[{{1, 2}, {3, 4}}]

Here is a more complicated example

tM = {{0, 0, 1, 2, 3, 4, 5, 6, 7, 8}, {0, 0, 0, 0, 2, 3, 4, 5, 0, 
          0}, {0, 0, 0, 1, 2, 3, 4, 5, 6, 7}, {0, 0, 2, 3, 4, 5, 6, 7, 8, 
          9}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}

MatrixForm[tM]

Fun2[tM]; 

MatrixForm[%]

Fun2[%%];

    
MatrixForm[%]

Fun2[%%];

    
MatrixForm[%]

Fun2[%%];

    
MatrixForm[%]

Fun2[%%];

    
MatrixForm[%]

TestREF[%%]

%%%

tMr = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 0, 2, 3, 4, 5, 6, 7, 8, 
          9}, {0, 0, 0, (1/2), 1, (3/2), 2, (5/2), 3, (7/2)}, {0, 0, 0, 0, 2, 3, 
          4, 5, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}

MatrixForm[tMr]

TestREF[tMr]

We achieved that matrix is in row echelon form. Now proceed towards reduced row echelon form.

Fun3[tMr];

    
MatrixForm[%]

Fun3[%%];

    
MatrixForm[%]

Fun3[%%];

    
MatrixForm[%]

Fun3[%%];

    
MatrixForm[%]

%%

tMrr = {{0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 
          0, -(1/2), -1, -(3/2), -5, -6}, {0, 0, 0, 
          1, 0, 0, 0, 0, 6, 7}, {0, 0, 0, 0, 1, (3/2), 2, (5/2), 0, 0}, {0, 0, 
          0, 0, 0, 0, 0, 0, 0, 0}}

TestRREF[tMrr]

Done!

Mathematica has a function to do row reduction. The result must be the same.

MatrixForm[RowReduce[tM]]

MatrixForm[tMrr]

RowReduce[tM] == tMrr

A complete example

tM2  = {{3, 2, 1, 0, 1, 2, 3, 4, 5, 6}, {6, 7, 8, 9, 8, 7, 6, 5, 4, 
          3}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 1, 2, 3, 2, 1, 0, 1, 2, 
          3}, {6, 7, 6, 5, 4, 3, 2, 1, 0, 1}, {8, 9, 8, 7, 6, 5, 4, 3, 2, 
          1}, {3, 4, 5, 6, 7, 8, 7, 6, 5, 4}, {1, 2, 1, 0, 1, 2, 3, 4, 5, 
          6}}

TableForm[
      Map[MatrixForm[#] &, 
        NestWhileList[Fun2, tM2, Not[TestREF[#]] &]]]

The last matrix is in row echelon form. Next we repeat the above calculations and proceed to reduced row echelon form.

TableForm[
      Map[MatrixForm[#] &, 
        NestWhileList[Fun4, tM2, Not[TestRREF[#]] &]]]

RowReduce[tM2] // MatrixForm

The same example, done step by step. At each step analyze what Mathematica did. Make your own judgment if that was efficient step towards the reduced row echelon form.

MatrixForm[tM2]

Fun4[tM2];

    
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

The last matrix is in reduced row echelon form. The Mathematica's function gives the same result.

MatrixForm[RowReduce[tM2]]

A matrix making function

To do more examples I define a function that will make random integer matrices for me.

Clear[MakeM, rr];

    
MakeM[rr_] := 
      Module[{rb, rm}, 
        Table[
rb = Random[Integer, {-3, 8}]; 
          rb = UnitStep[rb]*rb; 
rm = 
            Random[Integer, {rb, 9}]; 
Join[
            Range[rb, rm, 1], 
            Abs[Range[rm - 1, 2 rm - rb - 9, -1]]], {j, 1, rr, 
            1}]
]

Now I define a matrix to row reduce. Every time you execute this command it will give a different matrix.

tM3 = MakeM[7]

TableForm[
      Map[MatrixForm[#] &, 
        NestWhileList[Fun4, tM3, Not[TestRREF[#]] &]]]

The same example, done step by step. At each step analyze what Mathematica did. Make your own judgment if that was efficient step towards the reduced row echelon form.

MatrixForm[tM3]

Fun4[tM3];

    
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Fun4[%%];
MatrixForm[%]

Depending on the random matrix that is being row reduced, the last matrix might be in reduced row echelon form. Since this is a random example it will probable take more or less steps for your specific matrix. If it takes more steps you can highlight the cell with the command and paste it below the last one and continue evaluations.

A collection of matrices

tM4 = {{0, 1, 2, 3, 4, 5, 4, 3, 2, 1}, {0, 1, 2, 3, 2, 1, 0, 1, 2, 
          3}, {0, 1, 2, 3, 2, 1, 0, 1, 2, 3}, {0, 1, 2, 3, 4, 5, 6, 7, 6, 
          5}, {7, 8, 9, 8, 7, 6, 5, 4, 3, 2}, {0, 1, 2, 3, 4, 5, 4, 3, 2, 
          1}, {2, 3, 4, 5, 4, 3, 2, 1, 0, 1}}

tM5 = {{0, 1, 2, 3, 4, 5, 6, 5, 4, 3}, {1, 2, 3, 4, 5, 6, 5, 4, 3, 
          2}, {0, 1, 2, 3, 2, 1, 0, 1, 2, 3}, {0, 1, 2, 3, 2, 1, 0, 1, 2, 
          3}, {7, 8, 9, 8, 7, 6, 5, 4, 3, 2}, {7, 6, 5, 4, 3, 2, 1, 0, 1, 
          2}, {0, 1, 2, 3, 4, 5, 4, 3, 2, 1}}

tM6 = {{3, 4, 5, 6, 7, 8, 7, 6, 5, 4}, {4, 5, 4, 3, 2, 1, 0, 1, 2, 
          3}, {0, 1, 2, 3, 2, 1, 0, 1, 2, 3}, {6, 7, 8, 9, 8, 7, 6, 5, 4, 
          3}, {0, 1, 2, 3, 4, 5, 4, 3, 2, 1}, {4, 5, 6, 7, 8, 7, 6, 5, 4, 
          3}, {0, 1, 2, 3, 4, 3, 2, 1, 0, 1}, {2, 3, 4, 5, 4, 3, 2, 1, 0, 
          1}}

tM7 = {{2, 3, 4, 5, 6, 7, 8, 9, 8, 7}, {6, 7, 8, 7, 6, 5, 4, 3, 2, 
          1}, {0, 1, 2, 3, 4, 5, 6, 5, 4, 3}, {7, 8, 9, 8, 7, 6, 5, 4, 3, 
          2}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 5, 6, 5, 4, 3, 
          2}, {2, 1, 0, 1, 2, 3, 4, 5, 6, 7}}

tM8 = {{1, 2, 3, 4, 5, 6, 7, 6, 5, 4}, {2, 3, 4, 5, 6, 7, 6, 5, 4, 
          3}, {8, 7, 6, 5, 4, 3, 2, 1, 0, 1}, {0, 1, 2, 3, 4, 5, 6, 7, 6, 
          5}, {7, 6, 5, 4, 3, 2, 1, 0, 1, 2}, {2, 3, 4, 5, 6, 5, 4, 3, 2, 
          1}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 7}}

tM8 = {{5, 6, 7, 8, 9, 8, 7, 6, 5, 4}, {4, 5, 6, 5, 4, 3, 2, 1, 0, 
          1}, {2, 3, 4, 5, 6, 7, 8, 9, 8, 7}, {4, 3, 2, 1, 0, 1, 2, 3, 4, 
          5}, {3, 4, 5, 6, 5, 4, 3, 2, 1, 0}, {3, 4, 5, 6, 7, 8, 9, 8, 7, 
          6}, {6, 5, 4, 3, 2, 1, 0, 1, 2, 3}}

Vectors

Example 1

v7 = Transpose[MakeM[7]]

v7 = {{0, 1, 3, 5, 1, 0, 4}, {1, 2, 4, 6, 2, 1, 3}, {2, 3, 5, 5, 1, 2, 
          2}, {3, 4, 6, 4, 0, 3, 1}, {4, 5, 7, 3, 1, 4, 0}, {5, 6, 6, 2, 2, 
          5, 1}, {6, 7, 5, 1, 3, 6, 2}, {7, 8, 4, 0, 4, 7, 3}, {6, 9, 3, 1, 
          5, 8, 4}, {5, 8, 2, 2, 6, 9, 5}}

MatrixForm[v7]

MatrixForm[RowReduce[v7]]

Example 2

v7a = Transpose[MakeM[7]]

v7a = {{8, 4, 3, 6, 0, 4, 2}, {9, 5, 4, 7, 1, 5, 3}, {8, 6, 5, 8, 2, 6, 
          2}, {7, 7, 6, 7, 3, 7, 1}, {6, 8, 7, 6, 4, 8, 0}, {5, 9, 8, 5, 5, 
          9, 1}, {4, 8, 9, 4, 6, 8, 2}, {3, 7, 8, 3, 7, 7, 3}, {2, 6, 7, 2, 
          6, 6, 4}, {1, 5, 6, 1, 5, 5, 5}}

MatrixForm[v7a]

MatrixForm[RowReduce[v7a]]

Example 3

v7b = Transpose[MakeM[7]]

v7b = {{0, 6, 7, 0, 5, 4, 1}, {1, 5, 8, 1, 6, 5, 2}, {2, 4, 9, 2, 7, 6, 
          3}, {1, 3, 8, 3, 6, 5, 2}, {0, 2, 7, 4, 5, 4, 1}, {1, 1, 6, 5, 4, 
          3, 0}, {2, 0, 5, 6, 3, 2, 1}, {3, 1, 4, 7, 2, 1, 2}, {4, 2, 3, 8, 
          1, 0, 3}, {5, 3, 2, 9, 0, 1, 4}}

MatrixForm[v7b]

MatrixForm[RowReduce[v7b]]

A random example

v7r = Transpose[MakeM[7]]

MatrixForm[v7r]

MatrixForm[RowReduce[v7r]]