GATE DA 2025 Set 1 — Question 12

An upper triangular matrix is already in row echelon form. If the question refers to the standard Gaussian elimination process (forward elimination) to transform a matrix into upper triangular form, applying it to a matrix that is already upper triangular involves checking entries below the diagonal (which are zero) and performing no arithmetic updates. However, the algorithmic complexity to traverse and verify the structure is $O(n^2)$.If the question implies solving a system of linear equations $Ax=b$ where $A$ is upper triangular, the method used is Backward Substitution. The number of operations for backward substitution is:

• For $x_n$: 1 division.
• For $x_{n-1}$: 1 multiplication, 1 subtraction, 1 division.
• ...
• Total operations $\approx \sum_{i=1}^n i = \frac{n(n+1)}{2} \approx O(n^2)$.

If the question implies Gauss-Jordan elimination to convert the upper triangular matrix to a diagonal (or identity) matrix (Reduced Row Echelon Form), we must eliminate the entries above the diagonal. This process is symmetric to forward elimination and also requires $O(n^2)$ operations.In all relevant interpretations involving non-trivial work on an upper triangular matrix in the context of Gaussian elimination/solvers, the complexity is $O(n^2)$.