gaussian_elimination_GF2_matrix.sf

#!/usr/bin/ruby

# Perform Gauss elimination on a bit-matrix, where rows are integers.

# Code inspired from:
#   https://github.com/martani/Quadratic-Sieve/blob/master/matrix.c

func display_bitMatrix(A, n) {

    A.each { |r|
        var d = r.digits(2)
        d += (n-d.len + 1 -> of(0))
        say d.join(' ')
    }

    say ''
}

func gauss_elimination(A, n) {

    var m = A.end
    var I = (m+1).of {|i| 1 << i }

    var nrow = -1

    for col in (0 .. min(m, n)) {
        var npivot = -1

        for row in (nrow+1 .. m) {
            if (A[row].bit(col)) {
                npivot = row
                nrow++
                break
            }
        }

        next if (npivot < 0)

        if (npivot != nrow) {
            A.swap(npivot, nrow)
            I.swap(npivot, nrow)
        }

        for row in (nrow+1 .. m) {
            if (A[row].bit(col)) {
                A[row] ^= A[nrow]
                I[row] ^= I[nrow]
            }
        }
    }

    return I
}

var n = 5       # number of columns-1

var A = [
    0b001100,       # 12
    0b001011,       # 11
    0b010111,       # 23
    0b010011,       # 19
    0b010001,       # 17
    0b001111,       # 15
]

say "=> Matrix A before Gaussian elimination"
display_bitMatrix(A, n)

var I = gauss_elimination(A, n)

say "=> Matrix A after Gaussian elimination"
display_bitMatrix(A, n)

say "=> Matrix I"
display_bitMatrix(I, n)

say "A = #{A}"
say "I = #{I}"

assert_eq(I, [2, 18, 6, 10, 7, 46])
assert_eq(A, [11, 26, 28, 24, 16, 0])