GATE DA Systems of Linear Equations Previous Year Questions

GATE DA 2025 | Question 12

MCQ · 1 mark · −0.33

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})\)

Explanation

Answer: (B)

Gaussian elimination first creates zeros below the diagonal. For a full matrix this costs about \(\frac{2}{3}n^{3}\) additions and multiplications, the source of the \(O(n^{3})\) option. An upper triangular matrix already has those zeros, so this phase has nothing to do, and only back substitution remains:

\(x_{i} = \dfrac{1}{a_{ii}}\Big(b_{i} - \sum_{j \gt i} a_{ij}x_{j}\Big)\) for \(i = n, n - 1, \dots, 1\).

Row \(i\) needs \(n - i\) multiplications and \(n - i\) additions, so the total is \(\frac{n(n-1)}{2}\) of each: \(O(n^{2})\). \(O(n)\) is too small, because each of the roughly \(\frac{n^{2}}{2}\) entries above the diagonal is used once.

Answer: B

GATE DA 2024 | Question 48

MSQ · 2 marks

Which of the following statements is/are TRUE?

Note: \(\mathbb{R}\) denotes the set of real numbers.

There exist \(\boldsymbol{M} \in \mathbb{R}^{3 \times 3}\), \(\boldsymbol{p} \in \mathbb{R}^{3}\), and \(\boldsymbol{q} \in \mathbb{R}^{3}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has a unique solution and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has infinite solutions. There exist \(\boldsymbol{M} \in \mathbb{R}^{3 \times 3}\), \(\boldsymbol{p} \in \mathbb{R}^{3}\), and \(\boldsymbol{q} \in \mathbb{R}^{3}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has no solutions and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has infinite solutions. There exist \(\boldsymbol{M} \in \mathbb{R}^{2 \times 3}\), \(\boldsymbol{p} \in \mathbb{R}^{2}\), and \(\boldsymbol{q} \in \mathbb{R}^{2}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has a unique solution and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has infinite solutions. There exist \(\boldsymbol{M} \in \mathbb{R}^{3 \times 2}\), \(\boldsymbol{p} \in \mathbb{R}^{3}\), and \(\boldsymbol{q} \in \mathbb{R}^{3}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has a unique solution and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has no solutions.

Explanation

Answer: (B), (D)

A consistent system \(\boldsymbol{M}\mathbf{x} = \boldsymbol{b}\) has a unique solution exactly when the null space of \(\boldsymbol{M}\) is \(\{\mathbf{0}\}\); otherwise every consistent right-hand side has infinitely many solutions.

(A) False. A unique solution forces a trivial null space, so the square \(\boldsymbol{M}\) is invertible and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) also has exactly one solution.
(B) True. Take \(\boldsymbol{M} = \operatorname{diag}(1, 1, 0)\), \(\boldsymbol{p} = (0, 0, 1)^{\top}\) (no solution) and \(\boldsymbol{q} = \mathbf{0}\) (infinitely many).
(C) False. With 3 unknowns and rank at most 2, the null space is never trivial, so no solution is unique.
(D) True. Let \(\boldsymbol{M}\) have columns \((1, 0, 0)^{\top}\) and \((0, 1, 0)^{\top}\). Then \(\boldsymbol{p} = (1, 1, 0)^{\top}\) has the single solution \((1, 1)\), while \(\boldsymbol{q} = (0, 0, 1)^{\top}\) lies outside the column space.

Answer: B, D