Question

How many steps maximum does it take to perform row reduction on a 2x3 matrix? a 3x4 matrix? a 4x5 matrix? an NxN+1 matrix?

Answer 1

How would you define a step?
Is it in terms of the number of multiplications/divisions/additions?

Answer 2

elementary row operations, addition, multiplication, etc.

Answer 3

I assume a well-conditioned matrix, with strong diagonal elements, so no need to exchange rows.

I also assume row reduction is done to the point where we have an upper triangular matrix with 1's on the diagonal.
For an nx(n+1) matrix, we have to work on n rows.
For row i, we have at the end, (n-i+2) elements. Each element has to do a reduction with each of the previous rows, so there are (i-1)*(n-i+2) multiplications for each row, and the same number of additions.
The final step of each row is to divide each element by the diagonal element. There are (n-i+1) divisions to be done, excluding the diagonal, which is assumed to be 1.
\[\sum_{i=1}^{n} \left( (n-i+1) \ divisions + (i-1)(n-i+2) \ multiplications\ and\ (i-1)(n-i+2)\ additions \right)\]
If we assume all operations have equal weight, the the summation simplifies to:
\[\sum_{i=1}^{n} \left( (n-i+1) + 2(i-1)(n-i+2) \right)\]
This simplifies to:
\[\sum_{i=1}^{n} \left( i(2n+5)-2i^{2}-(3+n) \right)\]
which can be summed readily to:
\[((n)(n-1)/2)(2n+5) - 2(n)(n+1)(2n+1)/6 + n(3+n))\]
and simplified to:
\[(2n^{3}+9n^{2}+n)/6\]
The backward substitution can be worked out similarly.

Answer 4

Wow! Thanks so much

Answer 5

You're welcome!