I have an assignment to find the number of operations (only multiplications and divisions) needed to solve $N \times N$ linear equation while using Jordan Elimination method. I thought about it in two different ways but I'm not sure if my work is right.
Suppose that that the augumented matrix where I need to apply the Jordan elimination is:
$$ \left[ \begin{array}{ccc|c} a_{11}& \cdots \quad \cdots \quad \cdots \quad \cdots &a_{1n}&a_{1,n+1}\\ a_{21}& \cdots \quad \cdots \quad \cdots \quad \cdots &a_{2n}&a_{2,n+1}\\ \vdots& \quad \quad \quad & \vdots&\vdots\\ \vdots& \quad \quad \quad & \vdots&\vdots\\ a_{n1}& \cdots \quad \cdots \quad \cdots \quad \cdots &a_{nn}&a_{n,n+1}\\ \end{array} \right] $$
Step 1: for the $1^{st}$ row
Normalization of this row requires $n+1$ divisions since there is $n+1$ elements in the first row that I have to divide by $a_{11}$ and reduction requires $(n-1) (n+1)$ operations since I have to multiply each element of the $1^{st}$ row by $a_{i1}, i \neq 1$ (before subtracting the result from the $i^{th}$ row respectively but I'm not counting the additions/subtractions). There is $n -1$ rows where I have to do this and in each row there is $n+1$ elements or $n+1$ columns. Therefore, the total operations for the $1^{st}$ step is: $$(n+1) + (n-1)(n+1)$$
Note that I've thought about the reduction in another way which gave me a different answer. I know for a fact that all the elements below $a_{11}$ will be zero so there is no need to multiply these elements by $a_{11}$ and I can just put zero right away. Therefore, I still have to do the reduction on $n-1$ rows but only on $n$ columns. Thus, the total number of operations if I used this method should be:
$$ (n+1) + (n-1)n $$ At the end of this step, the matrix should look like: $$ \left[ \begin{array}{ccc|c} a_{11}& \cdots \quad \cdots \quad \cdots \quad \cdots &a_{1n}&a_{1,n+1}\\ 0& a_{22} \quad \cdots \quad \cdots \quad \cdots &a_{2n}&a_{2,n+1}\\ \vdots& \quad & \vdots&\vdots\\ \vdots& \quad \quad \quad & \vdots&\vdots\\ 0& a_{n2} \quad \cdots \quad \cdots \quad \cdots &a_{nn}&a_{n,n+1}\\ \end{array} \right] $$
Step 2: for the 2$^{nd}$ row
In this step, normalization requires $n$ divisions since I have to divide each element of the $2^{nd}$ row (except $a_{21}$ which is already zero) by $a_{22}$.
For the reduction part, I have to multiply each element of the $2^{nd}$ row (except $a_{21}$) by $a_{i2}, i \neq 2$ before subtracting. There is $n-1$ rows and $n$ columns so the number of operations for the reduction part is: $(n-1)n$ and the total number of operations for this step is: $$ n + (n-1)n $$
As in step 1, I know that $a_{i2}, (i \neq 2)$ will be zero in this step so I can skip the multiplication of these elements so instead of $n$ columns, I have $n-1$ columns. Therefore, the total number of operations should be: $$ n + (n-1)(n-1) $$
$\vdots$
Step k: for the k$^{th}$ row
I concluded that the number of divisions in the $k^{th}$ step should be: $n-k+2$ and the number of operations in the reduction part should be either: $(n-1)(n-k+2)$ or $(n-1)(n-k+1)$ depending on my approach as stated above.
The total number of operations for the $k^{th}$ step is either: $$ (n-k+2) + (n-1)(n-k+2) $$
$$\mathbf{OR}$$
$$ (n-k+2) + (n-1)(n-k+1) $$
The total number of operations of the Jordan elimination is either: $$ \sum_{k=1}^{n} \left[(n-k+2) + (n-1)(n-k+2) \right] = \frac{n^3}{2} + \frac{3n^2}{2} $$
$$\mathbf{OR}$$
$$ \sum_{k=1}^{n} \left[(n-k+2) + (n-1)(n-k+1) \right] = \frac{n^3}{2} + \frac{n^2}{2} + n $$
Is my work right? I hope my work will be of good help to those seeking the same answer since I didn't find much about this topic on the internet.