Welcome back. If you're here for the first time I suggest reading from the beginning of the series (over here).
Recap
Last time, which happens to be yesterday, we added gaussian elimination to our matrix class. On the way to doing this we also added a few other helper methods which we can hopefully use throughout this series.
1.2 Gauss-Jordan Elimination
Today we extend our gaussian elimination (albeit in a new function) to perform gauss-jordan elimination.
If you recall from last week, we said (not precisely) that gaussian elimination amounts to getting our matrix into the following form:
- Each row is either all zeros or contains a leading 1
- Each leading 1 has only 0's below it
Our final matrix from last time was:
We were pleased with our results, though we mentioned we'd like to clean up those negative 0's.
Gauss-Jordan elimination is the same as Gaussian Elimination but with 1 added rule: All leadings 1's must have only zeros below and above it.
Similar to last time we will start with going over the general algorithm
Algorithm
Step 1 in our algorithm will be performing Gaussian Elimination (this is an extension after all). At this point our matrix is in row echelon form.
Next we start from the last row and force each value above our leading 1 to be 0 just as we did when forcing all values below our leading 1 to be 0.
If the value we are trying to zero out is k, then we want to subtract that row by k times the row our leading 1 is in.
Programming
I feel like this is very similar to the last article. We can use our subtract _SubtractRowByRowMultiple method and just loop over the matrix bottom right to top left.
I'll just post the code here. I feel like it shares enough similarities with our Gaussian Elimination method that not much explaination is necessary.
I commented it to add clarity where I felt this code differed from Gaussian Elimination.
void ReduceToReducedRowEchelonForm() {
// Reduce to row echelon form
ReduceToRowEchelonForm();
int32_t r = NumRows,
c = NumCols;
while(c >= 0) {
// Save the current row position in case this column is all 0's
int32_t temp_row = r;
// If r == 0 then no work to do so might as well
// not consider this leading 1
for(; r >= 0; r--) {
if(matrix_[r][c] == 1) {
break;
}
}
// If we located a leading 1 in row 0 then there is
// no work to be done. Just break out. We're finished
if(r == 0) {
break;
}
// No leading 1 found
if(r < 0) {
r = temp_row;
c -= 1;
continue;
}
// Zero out all values above leading 1
for (int32_t above_row = r - 1; above_row >= 0; above_row--) {
_SubtractRowByRowMultiple(above_row, r, matrix_[above_row][c]);
}
r -= 1;
c -= 1;
}
}
This post is short since it's just an extension to last weeks. If we update our main.cpp to the following:
#include "linalg/matrix.h"
int main() {
mathlib::linalg::Matrix<float, 5, 5> matrix;
matrix << 1, 0, 33, 931, 11,
0, 0, 3, 99, 9,
0, 0, 653, -125, 271,
0, 0, 77, -30, -15,
0, 0, 95, 61, -9;
std::cout << "---------------Matrix---------------" << std::endl;
matrix.LatexPrint();
matrix.ReduceToRowEchelonForm();
std::cout << "-------- Row Echelon Form ----------" << std::endl;
matrix.LatexPrint();
matrix.ReduceToReducedRowEchelonForm();
std::cout << "---- Reduced Row Echelon Form ------" << std::endl;
matrix.LatexPrint();
}
we can return a get the output (In Latex):
Till next time!
-- Ehud