Transform M into row reduced echelon form (rref)

Gauss-Jordan Elimination

Mark first row (*) as next result row
M = * 00000000000000000000000000000001
      00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000001001000000001000
      00000000000000001100001000010000
      00000000000000010010101000100000
      00000000000000001110110001000000
      00000000000000001011000010000000
Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M = * 00000000000000000000000000000001
      00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000001001000000001000
      00000000000000001100001000010000
      00000000000000010010101000100000
      00000000000000001110110001000000
      00000000000000001011000010000000

Swap pivot row and next result row; Increment next result row.
M =   00000000000000010010101000100000
    * 00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000001001000000001000
      00000000000000001100001000010000
      00000000000000000000000000000001
      00000000000000001110110001000000
      00000000000000001011000010000000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010010101000100000
    * 00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000001001000000001000
      00000000000000001100001000010000
      00000000000000000000000000000001
      00000000000000001110110001000000
      00000000000000001011000010000000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000000010010101000100000
    * 00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000001001000000001000
      00000000000000001100001000010000
      00000000000000000000000000000001
      00000000000000001110110001000000
      00000000000000001011000010000000

Swap pivot row and next result row; Increment next result row.
M =   00000000000000010010101000100000
      00000000000000001001000000001000
    * 00000000000000000010100000000100
      00000000000000000000110000000010
      00000000000000001100001000010000
      00000000000000000000000000000001
      00000000000000001110110001000000
      00000000000000001011000010000000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010010101000100000
      00000000000000001001000000001000
    * 00000000000000000010100000000100
      00000000000000000000110000000010
      00000000000000000101001000011000
      00000000000000000000000000000001
      00000000000000000111110001001000
      00000000000000000010000010001000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000000010010101000100000
      00000000000000001001000000001000
    * 00000000000000000010100000000100
      00000000000000000000110000000010
      00000000000000000101001000011000
      00000000000000000000000000000001
      00000000000000000111110001001000
      00000000000000000010000010001000

Swap pivot row and next result row; Increment next result row.
M =   00000000000000010010101000100000
      00000000000000001001000000001000
      00000000000000000101001000011000
    * 00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000000000000000000001
      00000000000000000111110001001000
      00000000000000000010000010001000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010010101000100000
      00000000000000001001000000001000
      00000000000000000101001000011000
    * 00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000000000000000000001
      00000000000000000010111001010000
      00000000000000000010000010001000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000000010010101000100000
      00000000000000001001000000001000
      00000000000000000101001000011000
    * 00000000000000000000110000000010
      00000000000000000010100000000100
      00000000000000000000000000000001
      00000000000000000010111001010000
      00000000000000000010000010001000

Swap pivot row and next result row; Increment next result row.
M =   00000000000000010010101000100000
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010100000000100
    * 00000000000000000000110000000010
      00000000000000000000000000000001
      00000000000000000010111001010000
      00000000000000000010000010001000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010100000000100
    * 00000000000000000000110000000010
      00000000000000000000000000000001
      00000000000000000000011001010100
      00000000000000000000100010001100

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010100000000100
    * 00000000000000000000110000000010
      00000000000000000000000000000001
      00000000000000000000011001010100
      00000000000000000000100010001100

Increment next result row.
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010100000000100
      00000000000000000000110000000010
    * 00000000000000000000000000000001
      00000000000000000000011001010100
      00000000000000000000100010001100

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010010000000110
      00000000000000000000110000000010
    * 00000000000000000000000000000001
      00000000000000000000011001010100
      00000000000000000000010010001110

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010010000000110
      00000000000000000000110000000010
    * 00000000000000000000000000000001
      00000000000000000000011001010100
      00000000000000000000010010001110

Swap pivot row and next result row; Increment next result row.
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010010000000110
      00000000000000000000110000000010
      00000000000000000000011001010100
    * 00000000000000000000000000000001
      00000000000000000000010010001110

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010001001010010
      00000000000000000000101001010110
      00000000000000000000011001010100
    * 00000000000000000000000000000001
      00000000000000000000001011011010

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010001001010010
      00000000000000000000101001010110
      00000000000000000000011001010100
    * 00000000000000000000000000000001
      00000000000000000000001011011010

Swap pivot row and next result row; Increment next result row.
M =   00000000000000010000001000100100
      00000000000000001001000000001000
      00000000000000000101001000011000
      00000000000000000010001001010010
      00000000000000000000101001010110
      00000000000000000000011001010100
      00000000000000000000001011011010
    * 00000000000000000000000000000001

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010000000011111110
      00000000000000001001000000001000
      00000000000000000101000011000010
      00000000000000000010000010001000
      00000000000000000000100010001100
      00000000000000000000010010001110
      00000000000000000000001011011010
    * 00000000000000000000000000000001

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000000010000000011111110
      00000000000000001001000000001000
      00000000000000000101000011000010
      00000000000000000010000010001000
      00000000000000000000100010001100
      00000000000000000000010010001110
      00000000000000000000001011011010
    * 00000000000000000000000000000001

Increment next result row.
M =   00000000000000010000000011111110
      00000000000000001001000000001000
      00000000000000000101000011000010
      00000000000000000010000010001000
      00000000000000000000100010001100
      00000000000000000000010010001110
      00000000000000000000001011011010
      00000000000000000000000000000001

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000000010000000011111110
      00000000000000001001000000001000
      00000000000000000101000011000010
      00000000000000000010000010001000
      00000000000000000000100010001100
      00000000000000000000010010001110
      00000000000000000000001011011010
      00000000000000000000000000000001

Done.
M = 00000000000000010000000011111110
    00000000000000001001000000001000
    00000000000000000101000011000010
    00000000000000000010000010001000
    00000000000000000000100010001100
    00000000000000000000010010001110
    00000000000000000000001011011010
    00000000000000000000000000000001

See also: