Ruby Gaussian Elimination Steps

gauss.rb

# Step-By-Step Gaussian Elimination on Augmented Matrices
# By Tristan Hume

require "rational"

def reduce_down(mat)
  # Use each row going down to cancel lower rows
  # Each iteration of this loop is one step
  rows = mat.length
  (0..rows-2).each do |ri1|
    transforms = Array.new(rows,nil)
    # Cancel correct column of all rows below
    cancel_col = ri1
    (ri1+1..rows-1).each do |ri2|
      # We want mat[ri1][cancel_col]*cancel_coeff + mat[ri2][cancel_col] = 0
      cancel_coeff = -(mat[ri2][cancel_col])/(mat[ri1][cancel_col])
      mat[ri2] = mat[ri2].map.with_index { |x,c| x + cancel_coeff*mat[ri1][c]}
      transforms[ri2] = [[1,ri2],[cancel_coeff,ri1]]
    end
    out(mat,transforms)
  end
  mat
end

# Input needs to be in row echelon form
def one_ify_leads(mat)
  transforms = []
  mat.each_with_index do |row, ri|
    coeff = 1/row[ri] # needed to make leading into one
    transforms << [[coeff,ri]]
    mat[ri] = row.map { |c| c*coeff }
  end
  out(mat,transforms)
  mat
end

def reduce_up(mat)
  # Each iteration of this loop is one step
  rows = mat.length
  (rows-1).downto(1) do |ri1|
    transforms = Array.new(rows,nil)
    # Cancel correct column of all rows above
    cancel_col = ri1
    (ri1-1).downto(0) do |ri2|
      # We want mat[ri1][cancel_col]*cancel_coeff + mat[ri2][cancel_col] = 0
      cancel_coeff = -(mat[ri2][cancel_col])/(mat[ri1][cancel_col])
      mat[ri2] = mat[ri2].map.with_index { |x,c| x + cancel_coeff*mat[ri1][c]}
      transforms[ri2] = [[1,ri2],[cancel_coeff,ri1]]
    end
    out(mat,transforms)
  end
  mat
end

def is_identity?(r,trans)
  trans.all? { |a| a[0] == ((a[1] == r) ? 1 : 0) }
end

# Output

def console_format_num(n)
  return n.numerator.to_s if n.denominator == 1
  n.to_s + ' '
end

def console_out(mat,transforms)
  mat.each_with_index do |row,ri|
    print row.map { |c| console_format_num(c).ljust(5) }.join('')
    unless !transforms[ri] || is_identity?(ri,transforms[ri])
      print "      "
      transforms[ri].each_with_index do |t,ti|
        print "+" unless t[0] < 0 || ti == 0
        print console_format_num(t[0]) unless t[0] == 1
        print "R#{t[1]}"
      end
    end
    puts ''
  end
  puts ''
end

# TODO: LaTeX output

def out(mat,transforms)
  console_out(mat,transforms)
end

# Testing

def debug(m)
  STDERR.puts m
end


test_mat =
[
 [1,1,0, -5],
 [2,4,1, -6],
 [1,2,1, 9]
]

test_mat.map! { |r| r.map{ |c| c.to_r }}

debug "Reducing Down..."
reduce_down(test_mat)
debug "One-ifying..."
one_ify_leads(test_mat)
debug "Reducing Up..."
reduce_up(test_mat)

output.txt

Reducing Down...
1    1    0    -5
0    2    1    4          R1-2R0
0    1    1    14         R2-1R0

1    1    0    -5
0    2    1    4
0    0    1/2  12         R2-1/2 R1

One-ifying...
1    1    0    -5
0    1    1/2  2          1/2 R1
0    0    1    24         2R2

Reducing Up...
1    1    0    -5
0    1    0    -10        R1-1/2 R2
0    0    1    24

1    0    0    5          R0-1R1
0    1    0    -10
0    0    1    24