GATE 2025 DA Q.12: solution and answer

GATE 2025 · DAQ.12 · 1 mark · MCQ

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

(A)
$O (n)$
(B)
$O (n^{2})$
(C)
$O (n^{3})$
(D)
$O (n^{4})$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The operation count is of order $O (n^{2})$ , option (B).

Official answer: BSource: Official answer key, GATE 2025 DA (IIT Roorkee)

Gaussian elimination reduces a matrix to upper triangular form by subtracting multiples of the pivot row from the rows below it. In an upper triangular matrix every entry below the diagonal is already $0$ , so every row multiplier is $0$ and the elimination phase needs no row operations.
The arithmetic that remains is the solution of $U x = b$ by back substitution, computing $x_{n}, x_{n - 1}, \dots, x_{1}$ in turn. Row $i$ uses the $n - i$ already-known unknowns: $n - i$ multiplications, $n - i$ subtractions, and one division by $u_{ii}$ .
Total multiplications: $\sum_{i = 1}^{n} (n - i) = \frac{n ( n - 1 )}{2}$ . The number of additions/subtractions is the same, so multiplications plus additions come to $n (n - 1)$ (plus $n$ divisions).
$n (n - 1) = n^{2} - n$ grows like $n^{2}$ , so the work is $Θ (n^{2})$ . Every one of the $\frac{n ( n + 1 )}{2}$ nonzero entries is used, so the work cannot be $O (n)$ , and it is not of order $n^{3}$ or $n^{4}$ .
Hence the order is $O (n^{2})$ , option (B). The $O (n^{3})$ cost belongs to a full (dense) matrix, where each of about $n$ pivots updates an $(n - k) \times (n - k)$ block.

KEY IDEA

An upper triangular matrix needs no elimination. The only work left is back substitution, which costs about $\frac{n ( n - 1 )}{2}$ multiplications and as many additions, so $Θ (n^{2})$ .

WATCH OUT FOR

Quoting the dense-matrix cost $O (n^{3})$ for Gaussian elimination without noticing that this matrix is already triangular and the elimination cost vanishes.

From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 2 Linear systems questions, with notes