GATE DA

Linear systems

Systems of linear equations, Gaussian elimination, rank and nullity

A system of linear equations $A x = b$ is solved by row-reducing its augmented matrix. The rank of the matrix tells you whether solutions exist and how many there are. Rank and nullity, linked by the rank-nullity theorem, also describe the null space, so the same reduction answers questions on solvability, parametric systems and matrix inverses.

2 previous-year questions · 2 solved · 5 practice questions

Setting and conventions

Convention: all matrices are real. $A$ is an $m \times n$ matrix (m equations, n unknowns), $x \in R^{n}$ and $b \in R^{m}$ are column vectors in bold, and $A^{T}$ is the transpose. The system is

$A x = b$ , with augmented matrix $[A ∣ b]$ of size $m \times (n + 1)$ .

The system is consistent if at least one solution exists and inconsistent otherwise. It is homogeneous when $b = 0$ ; a homogeneous system is always consistent because $x = 0$ is a solution.

The three elementary row operations

Swap two rows.
Multiply a row by a non-zero scalar.
Add a multiple of one row to another row.

Each operation is reversible. Applied to the whole augmented matrix $[A ∣ b]$ , it does not change the solution set of $A x = b$ . It also does not change the row space, the null space or the rank of $A$ . It can change the column space of $A$ , so never read a column space off the reduced matrix directly; use the pivot positions to pick the original columns of $A$ .

Column operations also leave the rank unchanged, so they may be used when only the rank is wanted. Do not use them when solving $A x = b$ : they mix the unknowns, and the reduced system no longer has the original variables.

Gaussian elimination, pivots and free variables

Procedure

Write the augmented matrix $[A ∣ b]$ .
Working left to right, pick a non-zero entry in the current column (swap rows if needed). This is a pivot. Use it to make every entry below it zero.
Move to the next column and the next row, and repeat until no usable rows or columns are left. The result is a row-echelon form: every zero row is at the bottom, and each pivot lies strictly to the right of the pivot above it.
Read the pivots. A column of $A$ with a pivot is a pivot column and its variable is a basic variable. A column of $A$ without a pivot gives a free variable.
Back-substitute from the last non-zero row upward, writing each basic variable in terms of the free variables.

Reduced row-echelon form (RREF) goes further: every pivot is 1 and is the only non-zero entry in its column. RREF is unique for a given matrix. A row-echelon form is not unique, but the number and the column positions of its pivots are the same in every echelon form.

RANK AND FREE VARIABLES

rank (A) = number of pivots, number of free variables = n - rank (A)

Applies to any $m \times n$ matrix $A$ after row reduction; the rank is the same in every echelon form.

A row of the form $[00 \dots 0 ∣ c]$ with $c \neq = 0$ means $0 = c$ , so the system is inconsistent. A row $[0 \dots 0 ∣ 0]$ carries no information and is dropped.

Consistency and number of solutions

ROUCHÉ-CAPELLI CONSISTENCY TEST

A x = b is consistent ⟺ rank (A) = rank ([A ∣ b])

Equivalent statement: $b$ lies in the column space of $A$ . Always $rank (A) \leq rank ([A ∣ b]) \leq rank (A) + 1$ .

Outcomes for an m by n system, with r = rank(A)

Condition	Number of solutions	Free variables
$r < rank ([A ∣ b])$	None (inconsistent)	not applicable
$r = rank ([A ∣ b]) = n$	Exactly one	0
$r = rank ([A ∣ b]) < n$	Infinitely many	$n - r$

STRUCTURE OF THE SOLUTION SET

{x : A x = b} = x_{p} + N (A), N (A) = {x : A x = 0}

When the system is consistent, $x_{p}$ is any one particular solution; the general solution adds an arbitrary null-space vector.

Consequences worth remembering: if $r = m$ (full row rank) the system is consistent for every $b$ ; if $r = n$ (full column rank) there is at most one solution; for a square $n \times n$ matrix with $r = n$ there is exactly one solution for every $b$ . A system with fewer equations than unknowns ( $m < n$ ) can never have a unique solution, because $r \leq m < n$ .

WORKED EXAMPLE

Solve $x + 2 y + z = 4, 2 x + 4 y + 3 z = 9, 3 x + 6 y + 4 z = 13$ (a $3 \times 3$ system), and say what happens if the last right-hand side is changed to 14.

Solution

Augmented matrix $1232461344913$ .
$R_{2} \to R_{2} - 2 R_{1}$ gives $[001 ∣ 1]$ ; $R_{3} \to R_{3} - 3 R_{1}$ gives $[001 ∣ 1]$ .
$R_{3} \to R_{3} - R_{2}$ gives the zero row $[000 ∣ 0]$ .
Pivots are in columns 1 and 3, so $rank (A) = rank ([A ∣ b]) = 2 < 3$ : consistent with $3 - 2 = 1$ free variable, which is $y = t$ .
Row 2 gives $z = 1$ ; row 1 gives $x = 4 - 2 t - 1 = 3 - 2 t$ .
With 14 instead of 13, $R_{3} - 3 R_{1}$ gives $[001 ∣ 2]$ and then $R_{3} - R_{2}$ gives $[000 ∣ 1]$ , so $rank ([A ∣ b]) = 3 > 2$ and there is no solution.

Answer: $(x, y, z) = (3 - 2 t, t, 1)$ for any real $t$ (infinitely many solutions); with 14 the system is inconsistent.

Homogeneous systems, rank and nullity

The null space (kernel) of $A$ is $N (A) = {x \in R^{n} : A x = 0}$ , a subspace of $R^{n}$ . Its dimension is the nullity of $A$ . The rank is the dimension of the column space, which equals the dimension of the row space. Equivalently, the rank is the largest $k$ for which some $k \times k$ submatrix of $A$ has a non-zero determinant (a non-zero minor of order $k$ ).

RANK-NULLITY THEOREM

rank (A) + nullity (A) = n

$n$ is the number of columns of $A$ (not rows). Nullity equals the number of free variables in an echelon form of $A$ .

RANK BOUNDS

rank (A) \leq min (m, n), rank (A) = rank (A^{T}), rank (A B) \leq min {rank (A), rank (B)}

For $A$ of size $m \times n$ and any product $A B$ that is defined. For real matrices also $rank (A^{T} A) = rank (A A^{T}) = rank (A)$ .

MORE RANK FACTS

rank (A) + rank (B) - n \leq rank (A B), rank (A + B) \leq rank (A) + rank (B), rank (P A Q) = rank (A)

First (Sylvester's inequality): $A$ is $m \times n$ and $B$ is $n \times p$ . Second: $A$ and $B$ have the same size. Third: $P$ ( $m \times m$ ) and $Q$ ( $n \times n$ ) are invertible. Also, for non-zero $u \in R^{m}$ and $v \in R^{n}$ , the $m \times n$ matrix $u v^{T}$ has rank 1.

The four fundamental subspaces of an m by n matrix A with rank r

Subspace	Lives in	Dimension
Column space $C (A)$	$R^{m}$	$r$
Row space $C (A^{T})$	$R^{n}$	$r$
Null space $N (A)$	$R^{n}$	$n - r$
Left null space $N (A^{T})$	$R^{m}$	$m - r$

For a real matrix, every vector in $N (A)$ is orthogonal to every row of $A$ (that is what $A x = 0$ says), so $N (A)$ is the orthogonal complement of the row space in $R^{n}$ . Likewise $N (A^{T})$ is the orthogonal complement of the column space in $R^{m}$ .

Facts for homogeneous systems $A\mathbf{x}=\mathbf{0}$

A non-trivial solution exists exactly when $rank (A) < n$ .
If $m < n$ (fewer equations than unknowns) a non-trivial solution always exists.
For a square matrix: a non-trivial solution exists iff $det A = 0$ .
The solutions form a subspace with dimension $n - rank (A)$ ; a basis is obtained by setting one free variable to 1 and the others to 0, in turn.

WORKED EXAMPLE

Let $A = 101202011134$ ( $3 \times 4$ ). Find the rank, the nullity and a basis of $N (A)$ .

Solution

$R_{3} \to R_{3} - R_{1}$ gives $[0013]$ ; then $R_{3} \to R_{3} - R_{2}$ gives the zero row.
Pivots are in columns 1 and 3, so $rank (A) = 2$ and, by rank-nullity, $nullity (A) = 4 - 2 = 2$ .
Free variables are $x_{2}$ and $x_{4}$ . Row 2: $x_{3} = - 3 x_{4}$ . Row 1: $x_{1} = - 2 x_{2} - x_{4}$ .
Setting $(x_{2}, x_{4}) = (1, 0)$ gives $(- 2, 1, 0, 0)^{T}$ ; setting $(0, 1)$ gives $(- 1, 0, - 3, 1)^{T}$ .
Check the second vector in row 3 of the original $A$ : $- 1 + 0 - 3 + 4 = 0$ .

Answer: Rank 2, nullity 2, basis ${(- 2, 1, 0, 0)^{T}, (- 1, 0, - 3, 1)^{T}}$ .

Inverses by row reduction and invertibility

INVERSE BY ROW REDUCTION

[A ∣ I] row operations [I ∣ A^{- 1}]

For a square $n \times n$ matrix, with $I$ the $n \times n$ identity. If the left block cannot be reduced to $I$ (a zero row appears in it), $A$ is singular and has no inverse.

CRAMER'S RULE

x_{i} = \frac{det ( A _{i} )}{det ( A )}, i = 1, \dots, n

For a square $n \times n$ system with $det A \neq = 0$ . $A_{i}$ is $A$ with its $i$ -th column replaced by $b$ .

Equivalent conditions for an $n\times n$ matrix $A$

Statement	Meaning
$A$ is invertible	$A^{- 1}$ exists
$rank (A) = n$	$n$ pivots; RREF is $I$
$det A \neq = 0$	not singular
$A x = 0$ has only $x = 0$	nullity 0
$A x = b$ has a unique solution for every $b$	$x = A^{- 1} b$
Columns (and rows) are linearly independent	they span $R^{n}$
$0$ is not an eigenvalue of $A$	$det (A - 0 \cdot I) \neq = 0$

The same row reduction that finds $A^{- 1}$ also computes the rank: the rank of any matrix is the number of non-zero rows in an echelon form. For a matrix with a parameter, reduce while keeping the parameter symbolic, then examine each special value that makes a pivot vanish. Never divide a row by an expression in the parameter without treating separately the value that makes that expression zero.

EXAM TIP

Parametric square systems: suppose that after reduction every pivot except the last is a non-zero constant, and the last row reads $[0 \dots 0 p (k) ∣ q (k)]$ . For every $k$ with $p (k) \neq = 0$ the solution is unique. At a value $k_{0}$ with $p (k_{0}) = 0$ , check $q (k_{0})$ : if it is also zero you get infinitely many solutions, and if it is non-zero you get none. If an earlier pivot also depends on $k$ , check each of its zeros the same way.

Exam traps and quick checks

EXAM TIP

Rank-nullity uses the number of columns. For $A$ of size $5 \times 7$ with rank 4, $nullity (A) = 7 - 4 = 3$ , but $nullity (A^{T}) = 5 - 4 = 1$ because $A^{T}$ has 5 columns.

EXAM TIP

Equal rank does not mean a unique solution. Consistency needs $rank (A) = rank ([A ∣ b])$ ; uniqueness additionally needs that common rank to equal $n$ .

EXAM TIP

Row operations keep the null space and row space, not necessarily the column space. To describe the column space, take the original columns of $A$ in the pivot positions.

EXAM TIP

A homogeneous system never has 'no solution'. If a question asks when $A x = 0$ has non-trivial solutions, the answer is $rank (A) < n$ , not an inconsistency condition.

EXAM TIP

Check any particular solution by substituting it back into the original (not reduced) equations; a single arithmetic slip in elimination can lead you to a wrong option.

PREVIOUS-YEAR QUESTIONS

2 questions from the DA papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE DA 2025 · GATE DA 2024

GATE 2025 DA Q.12

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

Answer and solution

GATE 2025 DA Q.12: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 DA Q.12: answer and solution

GATE 2024 DA Q.48

GATE 2024 · DAQ.48 · 2 marks · MSQ

Which of the following statements is/are TRUE?

Note: $R$ denotes the set of real numbers.

(A)
There exist $M \in R^{3 \times 3}$ , $p \in R^{3}$ , and $q \in R^{3}$ such that $Mx = p$ has a unique solution and $Mx = q$ has infinite solutions.
(B)
There exist $M \in R^{3 \times 3}$ , $p \in R^{3}$ , and $q \in R^{3}$ such that $Mx = p$ has no solutions and $Mx = q$ has infinite solutions.
(C)
There exist $M \in R^{2 \times 3}$ , $p \in R^{2}$ , and $q \in R^{2}$ such that $Mx = p$ has a unique solution and $Mx = q$ has infinite solutions.
(D)
There exist $M \in R^{3 \times 2}$ , $p \in R^{3}$ , and $q \in R^{3}$ such that $Mx = p$ has a unique solution and $Mx = q$ has no solutions.

Answer and solution

GATE 2024 DA Q.48: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.48: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · MCQ

For a real number $k$ , consider the $3 \times 3$ system $x + y + z = 1, x + 2 y + 3 z = 2, x + 3 y + k z = 3$ . For which value of $k$ does the system have infinitely many solutions?

(A)
$k = 1$
(B)
$k = 3$
(C)
$k = 5$
(D)
There is no such value of $k$

Answer and solution

Answer: (C)

Augmented matrix rows: $[111 ∣ 1]$ , $[123 ∣ 2]$ , $[13 k ∣ 3]$ .
$R_{2} - R_{1}$ : $[012 ∣ 1]$ ; $R_{3} - R_{1}$ : $[02 k - 1 ∣ 2]$ .
$R_{3} - 2 R_{2}$ : $[00 k - 5 ∣ 0]$ .
The right-hand side of that row is 0, so the system is consistent for every $k$ . If $k \neq = 5$ the rank is 3 and the solution is unique.
If $k = 5$ the last row is zero, the rank is 2 and there is one free variable, so there are infinitely many solutions.

PRACTICE 21 mark · NAT

A real matrix $A$ has size $5 \times 7$ and rank 4. What is the nullity of $A^{T}$ (the dimension of the set of $y \in R^{5}$ with $A^{T} y = 0$ )?

Answer and solution

Answer: $1$

$rank (A^{T}) = rank (A) = 4$ .
$A^{T}$ has size $7 \times 5$ , so it has $5$ columns.
By rank-nullity, $nullity (A^{T}) = 5 - 4 = 1$ .

PRACTICE 32 marks · MSQ

Let $A$ be a real $4 \times 3$ matrix with $rank (A) = 3$ . Which of the following statements must be true?

(A)
$A x = 0$ has only the trivial solution.
(B)
For every $b \in R^{4}$ , the system $A x = b$ has at most one solution.
(C)
For every $b \in R^{4}$ , the system $A x = b$ is consistent.
(D)
The four rows of $A$ are linearly independent.

Answer and solution

Answer: (A), (B)

Here $n = 3$ and $rank (A) = 3$ , so $nullity (A) = 3 - 3 = 0$ . Statement A is true.
With a trivial null space, any two solutions of $A x = b$ differ by a null-space vector, so they are equal. Statement B is true.
The column space has dimension 3 inside $R^{4}$ , so it is not all of $R^{4}$ ; some $b$ give an inconsistent system. C is false.
The rows of $A$ are four vectors in $R^{3}$ , and any four vectors in $R^{3}$ are linearly dependent (equivalently, the row space has dimension 3). D is false.

PRACTICE 42 marks · MCQ

The real system $x + y + z = 6, 2 x - y + z = 3, x + 2 y - z = 2$ has a unique solution $(x, y, z)$ . What is the value of $x + 2 y + 3 z$ ?

(A)
12
(B)
13
(C)
14
(D)
15

Answer and solution

Answer: (C)

The coefficient determinant is $1 \cdot (1 - 2) - 1 \cdot (- 2 - 1) + 1 \cdot (4 + 1) = 7 \neq = 0$ , so the solution is unique.
From the first equation $z = 6 - x - y$ .
Substituting in the second: $2 x - y + 6 - x - y = 3$ , so $x - 2 y = - 3$ and $x = 2 y - 3$ .
Substituting in the third: $x + 2 y - (6 - x - y) = 2$ , so $2 x + 3 y = 8$ .
Then $2 (2 y - 3) + 3 y = 8$ gives $7 y = 14$ , so $y = 2$ , $x = 1$ , $z = 3$ .
Check in all three equations: $1 + 2 + 3 = 6$ , $2 - 2 + 3 = 3$ , $1 + 4 - 3 = 2$ . Hence $x + 2 y + 3 z = 1 + 4 + 9 = 14$ .

PRACTICE 52 marks · NAT

Let $A = 100210031$ ( $3 \times 3$ ). Using row reduction on $[A ∣ I]$ , find the entry in row 1, column 3 of $A^{- 1}$ .

Answer and solution

Answer: $6$

Write $[A ∣ I]$ with rows $[120 ∣ 100]$ , $[013 ∣ 010]$ , $[001 ∣ 001]$ . $A$ is upper triangular with every pivot equal to 1, so only upward elimination is needed.
Clear column 3 above its pivot: $R_{2} \to R_{2} - 3 R_{3}$ gives $[010 ∣ 01 - 3]$ . Row 1 already has 0 in column 3.
Clear column 2 above its pivot: $R_{1} \to R_{1} - 2 R_{2}$ gives $[100 ∣ 1 - 26]$ .
So $A^{- 1} = 100 - 2 10 6 - 3 1$ . Check: row 1 of $A$ times column 3 of $A^{- 1}$ is $6 - 6 + 0 = 0$ , and row 3 of $A$ times column 3 is $1$ , as required for $A A^{- 1} = I$ .
The entry in row 1, column 3 is $6$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE DA

systems of linear equations and solutions; Gaussian elimination … rank, nullity

Preparing in Kolkata? IAE Academy's course for GATE DA.