GATE 2025 DA – Question 12

Linear Algebra · Systems of linear equations and Gaussian elimination · 1 mark · Multiple choice

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

$O(n)$
$O(n^2)$
$O(n^3)$
$O(n^4)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $O(n^2)$

Explanation

An upper triangular matrix has no entries below the diagonal, so there is nothing to eliminate and no row operations are needed. Solving the system takes only back substitution, where the unknown $x_i$ needs about $n - i$ multiplications and additions. The total is about $\frac{n(n-1)}{2}$, which is $O(n^2)$. (Full elimination of a general matrix is the $O(n^3)$ case.)