The number of additions and multiplications involved in performing Gaussian elimination on any n × n upper triangular matrix is of the order

A.

O(n)

B.

O(n2)

C.

O(n3)

D.

O(n4)

Solution:

What is an Upper Triangular Matrix?

An upper triangular matrix has all elements below the diagonal equal to zero. For example, in a 3x3 case:

***0**00*

This means no elimination is needed below the diagonal (since those entries are already 0). So, most of the work is already done!

Gaussian Elimination: General Case

In general, Gaussian elimination on an n × n dense matrix requires about 23n3\frac{2}{3}n^3 operations (additions + multiplications).

For Upper Triangular Matrices:

You only need to perform back substitution because the matrix is already in row echelon form.

Back Substitution Cost:

  • For the last variable xnx_n, 0 operations (just division).

  • For xn−1x_{n-1}, 1 multiplication + 1 subtraction.

  • For xn−2x_{n-2}, 2 multiplications + 2 subtractions.

  • ...

  • For x1x_1, n−1n-1 multiplications + n−1n-1 subtractions.

So, total operations:

∑k=1n−12k=2⋅(n−1)n2=n(n−1)\sum_{k=1}^{n-1} 2k = 2 \cdot \frac{(n-1)n}{2} = n(n-1)

The number of additions and multiplications involved is of the order O(n2)