Let be a given matrix with . Find upper bound on the number of additions and multiplications required to determine the rank using the elimination procedure.

## Basic Understanding of Problem Nature

Consider matrix

This simulates matrix with .

Now, let’s consider Gauss Elimination. Every elementary row operation is of the form .

(1)

Gauss Elimination for matrix A:

__Step 1:__

is pivot for row. So, and should be made zero. For this, we need to perform elementary row operations on rows. Each row will have elements.

__Step 2:__

is pivot for row. So, and should be made zero. For this, we need to perform elementary row operations on rows. Each row will have elements. This is because the 1st column elements of all rows except 1 are now zero. This excluded 3 elements.

__Step 3:__

is pivot for row. So, and should be made zero. For this, we need to perform elementary row operations on rows. Each row will have element. This is because the & column elements of all rows except & are now zero. This excluded 4 elements.

(2)

## Solution

From (1) & (2),

Total no. of operations (add + mult) for Gauss Elimination,

(3)

Let and Apply this in (3),

Applying rules of summation & ignoring lower order variables,

Therefore, Upper bound on the number of additions and multiplications required to determine the rank using the elimination procedure,

*Degree of highest order polynomial is 3. *