System of Linear Equations-REF, RREF & Rank.

So When you have spent some amount of time building models with Scikit-learn or other packages, you suddenly realize that you should try to understand the mathematical intuition behind algorithms (Linear and Logistic...etc) so we directly dive into mathematical equations hoping for some shortcuts but sadly there is none. To understand or I would say to get the feel of these powerful algorithms we must brush up on our high school maths and a few more complex math topics.

In this post and subsequent posts, we are going to talk about some useful topics from Linear algebra. The assumption here is that reader is familiar with the concept of Vectors, Matrices, and their basic properties.

Though we will be talking about the System of Linear equations in detail in the next post for now simple definition is needed to set the context.

A linear system of m equations in n unknowns x1, … , xn is a set of equations of the form

Fig1. Linear system of m equations

The system is called linear because each variable xj appears in the first power only, just as in the equation of a straight line.

a11, … , amn are given numbers, called the coefficients of the system.

b1, … , bm on the right are also given numbers.

If all the bj are zero, then (1) is called a homogeneous system.

If at least one bj is not zero, then (1) is called a non-homogeneous system.

Now coming back to the main topic, Let’s expand the terms:

REF: Row Echelon Form.

RREF: Reduced Row Echelon Form.

Both REF and RREF are associated with the matrix so Let’s understand what is REF and RREF and we will see why it important.

Before that Let’s put some light on Elementary Row Operation or Operations that can be performed on a row of Matrix (not Columns):

1. Interchange of two rows
2. Addition of a constant multiple of one row to another row
3. Multiplication of a row by a nonzero constant c

What is the REF form of a Matrix?

Matrix is said to be in the REF form if the following properties hold true:

1. Any row of all zeros is below any other non-zero rows.
2. Each leading entry of a row is in a column to the right of the leading entry of the row above it.
3. All entries in a column below a leading entry are zeros.

Ex:

Matrix given

To reduce this matrix to row echelon form following steps need to perform following row operations:

Step 1: Multiply Row 1 by 2 and add it to Row 2 then replace Row 2 with the new value. Similarly, Multiply Row 1 by 7 and subtract it from Row 3 then replace Row 3 with the new value. This is being done to make elements to 0 in the first column except for the first top left element.

Row operations

Resulting :

Matrix after Step 1

Step 2: As we can see above matrix does not hold for property 3, to hold property 3 true, we have to make an entry below 42 to 0.

Let’s divide Row 2 by 2 and add it to Row 3 to get a new Row 3

Row operation of Row 3

Resulting Matrix:

As we can see this matrix satisfies all three properties of REF. Also, it must be noted down that there are not any fixed row operations to convert the matrix to its REF form. We could have chosen some other row operation to get REF.

What is the RREF form of a Matrix?

We say that a matrix is in Reduced Row Echelon Form if it is in Echelon form and additionally,

1. The leading entry in each row is 1.

2. Each leading 1 is the only non zero entry in its column

If we have to reduce the REF matrix to RREF form then we need to make pivot entries to 1 and all entries above and below the pivot to zero.

Step: Divide Row 1 by 3 and replace Row 1 with new values, similarly Divide Row 2 by 42 and replace Row 2 with new values, and the resulting matrix is in RREF form:

RREF form of Matrix

So the obvious question that comes to our mind is “ What is the use and where of these so-called REF and RREF?”

The answer is :

while solving a system of linear equations.

Finding rank, nullity, and basis of Vector space.

and many more.

Let's define the Rank first then we will see the use of RREF and REF in determining the Rank of the Matrix.

Definition 1: “ The rank of a matrix A is the maximum number of linearly independent row vectors of A. It is denoted by rank A.”

Definition 2: “ The rank r of a matrix A equals the maximum number of linearly independent column vectors of A.”

What is Linear Independence?

The simple definition of Linear Independence is:

“ Two vectors u and v are linearly independent if the only numbers x and y satisfying xu+yv=0 are x=y=0 ”

Till now we have defined :

1. What is a system of Linear equations?

2. Rank of the Matrix.

3. And, Linear Independence.

We will now see how REF and RREF of a Matrix help us find all the above.

First, let's See the REF :

Fig 2

Once the Matrix is in REF form,

we can determine the Rank (as shown in the figure) of the matrix, apart from this REF matrix gives us

1. Linearly Independent Row Vectors ( the non-zero row vectors ) from the REF matrix.
2. Linearly Independent Column Vectors ( the columns with pivots) from the REF matrix.

Now Let’s take look at the RREF form of Matrix:

As you can see in the figure above, we can get Rank, independence of vectors, etc from the RREF as well.

Then why do we need RREF when we have REF?

Well REF of Matrix is not unique but the RREF of a matrix is unique.

No matter what sequence of row operations we use each matrix is row equivalent to one and only one reduced echelon matrix.

We will continue the discussion in the next post.

thanks…