Transform M into row reduced echelon form (rref)

Gauss-Jordan Elimination

Mark first row (*) as next result row
M = * 00000000000000000000000000000001
      00000000000000000011000000000010
      00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000010001000000000010000
      00000000000111111110100000100000
      00000000000001000111000001000000
      00000000000111011100000010000000
      00000000000100101101000100000000
      00000000000001101001001000000000
Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M = * 00000000000000000000000000000001
      00000000000000000011000000000010
      00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000010001000000000010000
      00000000000111111110100000100000
      00000000000001000111000001000000
      00000000000111011100000010000000
      00000000000100101101000100000000
      00000000000001101001001000000000

Swap pivot row and next result row; Increment next result row.
M =   00000000000111111110100000100000
    * 00000000000000000011000000000010
      00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000010001000000000010000
      00000000000000000000000000000001
      00000000000001000111000001000000
      00000000000111011100000010000000
      00000000000100101101000100000000
      00000000000001101001001000000000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000111111110100000100000
    * 00000000000000000011000000000010
      00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000010001000000000010000
      00000000000000000000000000000001
      00000000000001000111000001000000
      00000000000000100010100010100000
      00000000000011010011100100100000
      00000000000001101001001000000000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000111111110100000100000
    * 00000000000000000011000000000010
      00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000010001000000000010000
      00000000000000000000000000000001
      00000000000001000111000001000000
      00000000000000100010100010100000
      00000000000011010011100100100000
      00000000000001101001001000000000

Swap pivot row and next result row; Increment next result row.
M =   00000000000111111110100000100000
      00000000000010001000000000010000
    * 00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000001000111000001000000
      00000000000000100010100010100000
      00000000000011010011100100100000
      00000000000001101001001000000000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000101110110100000110000
      00000000000010001000000000010000
    * 00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000001000111000001000000
      00000000000000100010100010100000
      00000000000001011011100100110000
      00000000000001101001001000000000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000101110110100000110000
      00000000000010001000000000010000
    * 00000000000000001010000000000100
      00000000000000100100000000001000
      00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000001000111000001000000
      00000000000000100010100010100000
      00000000000001011011100100110000
      00000000000001101001001000000000

Swap pivot row and next result row; Increment next result row.
M =   00000000000101110110100000110000
      00000000000010001000000000010000
      00000000000001000111000001000000
    * 00000000000000100100000000001000
      00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000100010100010100000
      00000000000001011011100100110000
      00000000000001101001001000000000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100110001100001110000
      00000000000010001000000000010000
      00000000000001000111000001000000
    * 00000000000000100100000000001000
      00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000100010100010100000
      00000000000000011100100101110000
      00000000000000101110001001000000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000100110001100001110000
      00000000000010001000000000010000
      00000000000001000111000001000000
    * 00000000000000100100000000001000
      00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000100010100010100000
      00000000000000011100100101110000
      00000000000000101110001001000000

Increment next result row.
M =   00000000000100110001100001110000
      00000000000010001000000000010000
      00000000000001000111000001000000
      00000000000000100100000000001000
    * 00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000100010100010100000
      00000000000000011100100101110000
      00000000000000101110001001000000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100010101100001111000
      00000000000010001000000000010000
      00000000000001000111000001000000
      00000000000000100100000000001000
    * 00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000000110100010101000
      00000000000000011100100101110000
      00000000000000001010001001001000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000100010101100001111000
      00000000000010001000000000010000
      00000000000001000111000001000000
      00000000000000100100000000001000
    * 00000000000000000011000000000010
      00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000000110100010101000
      00000000000000011100100101110000
      00000000000000001010001001001000

Swap pivot row and next result row; Increment next result row.
M =   00000000000100010101100001111000
      00000000000010001000000000010000
      00000000000001000111000001000000
      00000000000000100100000000001000
      00000000000000011100100101110000
    * 00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000000110100010101000
      00000000000000000011000000000010
      00000000000000001010001001001000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100001001000100001000
      00000000000010001000000000010000
      00000000000001000111000001000000
      00000000000000100100000000001000
      00000000000000011100100101110000
    * 00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000000110100010101000
      00000000000000000011000000000010
      00000000000000001010001001001000

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000100001001000100001000
      00000000000010001000000000010000
      00000000000001000111000001000000
      00000000000000100100000000001000
      00000000000000011100100101110000
    * 00000000000000000000000000000001
      00000000000000001010000000000100
      00000000000000000110100010101000
      00000000000000000011000000000010
      00000000000000001010001001001000

Swap pivot row and next result row; Increment next result row.
M =   00000000000100001001000100001000
      00000000000010001000000000010000
      00000000000001000111000001000000
      00000000000000100100000000001000
      00000000000000011100100101110000
      00000000000000001010000000000100
    * 00000000000000000000000000000001
      00000000000000000110100010101000
      00000000000000000011000000000010
      00000000000000001010001001001000

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100000011000100001100
      00000000000010000010000000010100
      00000000000001000111000001000000
      00000000000000100100000000001000
      00000000000000010110100101110100
      00000000000000001010000000000100
    * 00000000000000000000000000000001
      00000000000000000110100010101000
      00000000000000000011000000000010
      00000000000000000000001001001100

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000100000011000100001100
      00000000000010000010000000010100
      00000000000001000111000001000000
      00000000000000100100000000001000
      00000000000000010110100101110100
      00000000000000001010000000000100
    * 00000000000000000000000000000001
      00000000000000000110100010101000
      00000000000000000011000000000010
      00000000000000000000001001001100

Swap pivot row and next result row; Increment next result row.
M =   00000000000100000011000100001100
      00000000000010000010000000010100
      00000000000001000111000001000000
      00000000000000100100000000001000
      00000000000000010110100101110100
      00000000000000001010000000000100
      00000000000000000110100010101000
    * 00000000000000000000000000000001
      00000000000000000011000000000010
      00000000000000000000001001001100

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100000011000100001100
      00000000000010000010000000010100
      00000000000001000001100011101000
      00000000000000100010100010100000
      00000000000000010000000111011100
      00000000000000001010000000000100
      00000000000000000110100010101000
    * 00000000000000000000000000000001
      00000000000000000011000000000010
      00000000000000000000001001001100

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000100000011000100001100
      00000000000010000010000000010100
      00000000000001000001100011101000
      00000000000000100010100010100000
      00000000000000010000000111011100
      00000000000000001010000000000100
      00000000000000000110100010101000
    * 00000000000000000000000000000001
      00000000000000000011000000000010
      00000000000000000000001001001100

Swap pivot row and next result row; Increment next result row.
M =   00000000000100000011000100001100
      00000000000010000010000000010100
      00000000000001000001100011101000
      00000000000000100010100010100000
      00000000000000010000000111011100
      00000000000000001010000000000100
      00000000000000000110100010101000
      00000000000000000011000000000010
    * 00000000000000000000000000000001
      00000000000000000000001001001100

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100000000000100001110
      00000000000010000001000000010110
      00000000000001000001100011101000
      00000000000000100001100010100010
      00000000000000010000000111011100
      00000000000000001001000000000110
      00000000000000000101100010101010
      00000000000000000011000000000010
    * 00000000000000000000000000000001
      00000000000000000000001001001100

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000100000000000100001110
      00000000000010000001000000010110
      00000000000001000001100011101000
      00000000000000100001100010100010
      00000000000000010000000111011100
      00000000000000001001000000000110
      00000000000000000101100010101010
      00000000000000000011000000000010
    * 00000000000000000000000000000001
      00000000000000000000001001001100

Swap pivot row and next result row; Increment next result row.
M =   00000000000100000000000100001110
      00000000000010000001000000010110
      00000000000001000001100011101000
      00000000000000100001100010100010
      00000000000000010000000111011100
      00000000000000001001000000000110
      00000000000000000101100010101010
      00000000000000000011000000000010
      00000000000000000000001001001100
    * 00000000000000000000000000000001

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100000000000100001110
      00000000000010000001000000010110
      00000000000001000001100011101000
      00000000000000100001100010100010
      00000000000000010000000111011100
      00000000000000001001000000000110
      00000000000000000101100010101010
      00000000000000000011000000000010
      00000000000000000000001001001100
    * 00000000000000000000000000000001

Highlight next pivot row and column
Find first row with leftmost bit set starting from next result row.
M =   00000000000100000000000100001110
      00000000000010000001000000010110
      00000000000001000001100011101000
      00000000000000100001100010100010
      00000000000000010000000111011100
      00000000000000001001000000000110
      00000000000000000101100010101010
      00000000000000000011000000000010
      00000000000000000000001001001100
    * 00000000000000000000000000000001

Increment next result row.
M =   00000000000100000000000100001110
      00000000000010000001000000010110
      00000000000001000001100011101000
      00000000000000100001100010100010
      00000000000000010000000111011100
      00000000000000001001000000000110
      00000000000000000101100010101010
      00000000000000000011000000000010
      00000000000000000000001001001100
      00000000000000000000000000000001

Clear pivot column.
Add pivot row to all other rows with bit set in pivot column
M =   00000000000100000000000100001110
      00000000000010000001000000010110
      00000000000001000001100011101000
      00000000000000100001100010100010
      00000000000000010000000111011100
      00000000000000001001000000000110
      00000000000000000101100010101010
      00000000000000000011000000000010
      00000000000000000000001001001100
      00000000000000000000000000000001

Done.
M = 00000000000100000000000100001110
    00000000000010000001000000010110
    00000000000001000001100011101000
    00000000000000100001100010100010
    00000000000000010000000111011100
    00000000000000001001000000000110
    00000000000000000101100010101010
    00000000000000000011000000000010
    00000000000000000000001001001100
    00000000000000000000000000000001

See also: