I am having some problem wrapping my head around an assignment.
I have to find out how many additions, subtractions, multiplications and divisions are used while solving an $N \times M$ linear equation, while using Gauss-Jordan elimination.
Could anyone point me in the right direction?
Best Answer
It depends on how efficient you want to be, and it also depends on the rank of the matrix. But for a "generic" matrix, you can expect the rank to be $\min(N,M)$, and for "most" entries to be nonzero. (And, do you count multiplying zero by a constant as a "multiplication"? Adding two zeros as an "addition"?)
I interpret your question as asking for the number of multiplications and additions of entries, rather than adding rows, etc.
Every time you multiply a row by a constant, you are performing $M$ multiplications (minus the number of entries that are zero if they don't count); every time you add a row to another row you are performing $M$ additions/subtractions (minus the number of entries that are zero in both).
So, generically, let us assume that the only zeros you will encounter are the ones you create throught Gauss-Jordan elimination.
So, how do you get started? First you pick a pivot; then you use that pivot to eliminate the other entries in the column; there are $N-1$ entries to be eliminated; each elimination requires (i) multiplying your pivot row by a constant; and (ii) adding the pivot row to another row. So you are performing $M$ products and $M$ sums in each step, and you are doing this $N-1$ times. Then, you multiply the first row appropriately to get a $1$ in the pivot, for another $M$ products.
Next you pick your next pivot, and you need to eliminate the entries below it on the column; there are $N-2$ entries; each entry requires (i) multiplying your pivot row by a constant, which requires $M-1$ products (first entry is $0$, you can ignore it), and then (ii) adding to the other row, requiring $M-1$ sums (first entry in both is $0$, you can ignore it). You do this $N-2$ times, and then multiply the first row by a constant ($M-1$ products again) to get a $1$ in the pivot.
Then you pick your next pivot... etc. Figure out how many products/sums we are doing in each step, how many steps, add them all up.
This will be an upper bound, since in practice you could end up with lots of zeros, or a matrix that has rank strictly smaller than $\min(M,N)$, so that you get a row of zeroes early on, etc.
Reading your title, though, you might be counting "add a row to another row" as a single step, and "multiply a row by a constant" as a single step; in that case, proceed as above but you only count the number of row operations instead of the number of individual numerical operations, and the number of common zeros between the rows is irrelevant.