-
-
Save pmelanson/6edd97fe7425ce00707d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 | |
print "~" | |
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment