GATE CS 2017 Set 1 Q.3 (CS Q.3): Linear Algebra

Let $c_1, \dots, c_n$ be scalars, not all zero, such that $\sum_{i=1}^n c_i a_i = 0$ where $a_i$ are column vectors in $\mathbb{R}^n$ . Consider the set of linear equations

Ax = b

where $A = [a_1, \dots, a_n]$ and $b = \sum_{i=1}^n a_i$ . The set of equations has

a unique solution at $x = J_n$ , where $J_n$ denotes an $n$ -dimensional vector of all 1

no solution

infinitely many solutions

finitely many solutions

Official answer and solution

Official answer: C
From: Official GATE 2017 answer key

Solution

Use the definition of linear dependence of column vectors and the properties of non-trivial null space vectors in linear systems.

We are given that $c_1, \dots, c_n$ are scalars, not all zero, such that:

\sum_{i=1}^n c_i a_i = 0

Let $c = [c_1, c_2, \dots, c_n]^T$ . Then $c \ne 0$ is a non-zero vector, and $Ac = \sum_{i=1}^n c_i a_i = 0$ . This means that $c$ is a non-trivial vector in the null space (kernel) of $A$ , so the matrix $A$ is singular (its determinant is 0).

Now consider the linear system $Ax = b$ , where $b = \sum_{i=1}^n a_i$ . Notice that:

A J_n = [a_1, a_2, \dots, a_n] \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} = \sum_{i=1}^n a_i = b

Hence, $x_0 = J_n$ is a particular solution to the system $Ax = b$ .

For any scalar $k \in \mathbb{R}$ , consider the vector $x = J_n + k c$ . We evaluate:

A(J_n + k c) = A J_n + k(A c) = b + k(0) = b

Because $c \ne 0$ and $k$ can be any real number, there are infinitely many vectors of the form $J_n + k c$ that satisfy the system. Therefore, the set of linear equations has infinitely many solutions.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 3 of 65, printed as CS Q.3
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source