Let $A_{mXn}$ be a given matrix with $m > n$. Find upper bound on the number of additions and multiplications required to determine the rank using the elimination procedure.

Let $A_{mXn}$ be a given matrix with $m > n$ . 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

$\left A_{5X3} = \right \left (\begin{array}{rrr} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ a_{41} & a_{42} & a_{43} \\ a_{51} & a_{52} & a_{53} \end{array} \right)$

This simulates $A_{mXn}$ matrix with $m > n$ .

Now, let’s consider Gauss Elimination. Every elementary row operation is of the form $R_2 \leftarrow R_2 + (m_{21})*R_1$ .

(1) $\begin{equation*} \begin{minipage}{1\textwidth} So there is one addition & one multiplication per elementary row operation. Also, number of additions=multiplications. \end{minipage} \end{equation*}$

Gauss Elimination for matrix A:

Step 1:

$a_{11}$ is pivot for $1^{st}$ row. So, $a_{21}, a_{31}, a_{41}$ and $a_{51}$ should be made zero. For this, we need to perform elementary row operations on $5-1 = 4$ rows. Each row will have $3+1-1=3$ elements.

Step 2:

$a_{22}$ is pivot for $2^{nd}$ row. So, $a_{32}, a_{42}$ and $a_{52}$ should be made zero. For this, we need to perform elementary row operations on $5-2 = 3$ rows. Each row will have $3+1-2 = 2$ elements. This is because the 1st column elements of all rows except 1 are now zero. This excluded 3 elements.

Step 3:

$a_{33}$ is pivot for $3^{rd}$ row. So, $a_{43}$ and $a_{53}$ should be made zero. For this, we need to perform elementary row operations on $5-3 = 2$ rows. Each row will have $3+1-3 = 1$ element. This is because the $1^{st}$ & $2^{nd}$ column elements of all rows except $a_{11}$ & $a_{22}$ are now zero. This excluded 4 elements.

(2) $\begin{equation*} \begin{minipage}{1\textwidth} Thus for the kth step, when $a_{kk}$ is the pivot, the elementary row operations will be done on $m-k$ rows and each row will have $n+1-k$ elements. \end{minipage} \end{equation*}$