By the end of this post, we will be able to get any matrix into Row Echelon Form. It will be helpful to look at the All Integer Method. We will be using a modified version of it to obtain our goal.
We will be using a basic Python Array to represent our matrix. No, I will not use NumPy, SciPy, or any of the like. The main reason, what’s the fun in that? Sure there are Tasks where they are appropriate, this is not one of them.
Let’s dive into all the individual tasks we will want to handle.
Python Elements
- Array
- Dictionary
- For Loop
- While Loop
- If Statement
I will leave it up to you if you want to look those up, but I will explain how I am using each of the above elements.
The Functions
Our main goal is to keep everything simple. We want to take the complex task of producing a Reduced Row Echelon Matrix and break it down into simple elements. Let’s briefly go over these elements.
Displaying our Matrix: We will want an easy and readable way to display our matrix whenever we want. This is mainly going to be used as a development tool, and it will be used to make sure that other elements are doing what we want them to be doing.
Swapping Rows: Matrixes don’t always play nice. From the All Integer Method, it is not always convenient to select the next pivot and row swapping will help.
Where Are We: We will use a Dictionary to keep track of what we are using as a pivot as well as keeping track of when we are done.
Finding Pivots: Most of the times the next pivot is one row down and one column to the right. When this is not the case, this will help us. This is when Swapping Rows will come in handy.
Criss Cross: This is a step directly from the All Integer Method. Multiply the pivot with the target and subtract from that the product of the opposite corners.
New Matrix After Pivitong the Entier Matrix: By the way, I like to call this step, “Blasting Everything to Ash.” This will slightly deviate from The All integer Method, but it will handle previous pivots, anything previously zeroed, zeroes in pivot column, and everything else. If you have not already done so, please go over my post for the All Integer Method.
Greatest Common Divisor (GCD): We will want to simplify each row of our matrix as we go with the greatest common divisor of its non zero elements. This is another deviation from the All Integer Method. With how computers store integers, there is a limit to how big the numbers can become. With no simplification, it is very easy to reach this limit using the All Integer Method. While it is somewhat a standard algorithm, I have made a post of an explanation of the basic GCD algorithm also known as Euclid’s Algorithm. For our purposes, we will do four functions. One function that does GCD of two inputs. The second will use this base algorithm to find the GCD of any number of inputs. The third will gather the non zero elements of a row. Finally, a driver function to iterate over our matrix.
A Driver: Finally we will want a function to bring everything together. Find a pivot, pivot (Blasting Everything to Ash), simplify the matrix, find the next pivot, so on and so forth until we have a Reduced Row Echelon matrix.
A Class
At the end, I will show you how to wrap all of this into a class. This will help to keep everything simple. After that, I will be using classes for every other part of this project.
Final Thoughts
At this point, I will ask that you do some digesting. Reread this post and do some thinking. If you have some experience with Python, no matter how small, maybe you have already thought about how to handle each of the above tasks.
Again, if you have not done so, go over the All Integer Method as well as Euclid’s Algorithm.
Recent Comments