In the following question I have solved the system
$$2x_1-x_2=2$$ $$-x_1+3x_2 = 4$$
Using gaussian elimination. Below are the workings, however I am wonder what is the cost of this process? how do I count the amount of operations?
$$ A= \bigg[ \begin{matrix} 2&-1\\-1&3 \end{matrix} \bigg] = \bigg[ \begin{matrix} 2\\4 \end{matrix} \bigg] $$
for row $2$ multiplying Row $1$ by 2 and adding to row $2$ gives
$$ A= \bigg[ \begin{matrix} 2&-1\\0&5 \end{matrix} \bigg] = \bigg[ \begin{matrix} 2\\10 \end{matrix} \bigg] $$
using back sub we get $x_2=2$ and $x_1=\frac{2+1\times 2}{2} = 2$
But what was the cost of this?
Consider a system of $m$ equations with $m$ unknowns then we have the system:
$$\begin{pmatrix} a_{11} & a_{12} &\dots& a_{1m} \\ a_{21} & a_{22} &\dots & a_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mm} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\x_m \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}$$
Through Gaussian Elimination we transform the system into: $$\begin{pmatrix} u_{11} & u_{12} &\dots& u_{1m} \\ & u_{22} &\dots & u_{2m} \\ & & \ddots & \vdots \\ & & & u_{mm} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\x_m \end{pmatrix} = \begin{pmatrix} g_1 \\ g_2 \\ \vdots \\ g_m \end{pmatrix}$$ if we carefully count the number of operations in transforming $A$ into $U$ we can get the following:
\begin{array}{c|c|c|c} \textrm{step} & \textrm{addition} & \textrm{multiplication} & \textrm{division} \\ \hline 1 & (m-1)^2 & (m-1)^2 & m-1 \\ 2 & (m-2)^2 & (m-2)^2 & m-2 \\ \vdots & \vdots& \vdots & \vdots \\ m -1 & 1 & 1 & 1 & \\ \hline \textrm{total}: & 6^{-1}m(m-1)(2m-1) & 6^{-1}m(m-1)(2m-1) & 2^{-1}n(n-1) \end{array}
similarly to transform $b$ into $g$ we have $2^{-1}m(m-1)$ additions and multiplications
finally, when back-solving we have $2^{-1}m(m-1)$ additions and $2^{-1}m(m+1)$ multiplications
so the total number of operations required is: $$\frac{m(m(4m+9)-7)}{6}$$
i.e. for a $2\times 2$ system we see that we require 9 operations