Systems of Linear Equations and LU Decomposition Notes for GATE CS

Systems of Linear Equations and LU Decomposition notes for GATE CS: 39 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Systems of Linear Equations

Journey through this chapter

Step 1 · Consistency of Parameterized Systems

Decide unique, infinite, or no solution when parameters appear.

Step 2 · LU Decomposition Properties

Why

P = LU

exists and how it reorganises solving.

Step 3 · LU Factorization & Substitution

Compute

L

and

U

, then solve

L Y = B

U X = Y

Goal: Classify any linear system and solve it using LU decomposition in two triangular sweeps.

Why Parameterized Systems Matter

A parameterized linear system is a system $A X = B$ where some entries of $A$ or $B$ are not fixed numbers but parameters (letters such as $k$ , $a$ , $b$ , $λ$ ).

The central question: for which values of the parameter does the system have a unique solution, infinitely many solutions, or no solution at all?

Why this is asked in GATE:

Parameters model design variables, physical constants, or tuning knobs.
The exam tests whether you can read the structure of a system instead of blindly solving it.
It is the cleanest way to test your understanding of rank, determinant, and consistency in one question.

Behaviour	Meaning
Unique solution	Exactly one $X$ satisfies every equation
Infinitely many	A whole family of $X$ satisfies every equation
No solution	No $X$ can satisfy all equations simultaneously

Consistency: The Rank Test

Let the system be $A X = B$ , where $A$ is $m \times n$ .

$A$ = coefficient matrix, size $m \times n$
$[A ∣ B]$ = augmented matrix, size $m \times (n + 1)$
$rank (A)$ = number of linearly independent rows of $A$
$rank ([A ∣ B])$ = rank of the augmented matrix

The Consistency Theorem
Let

r_{A} = rank (A)

and

r_{A B} = rank ([A ∣ B])

If $r_{A} \neq = r_{A B}$ , the system is inconsistent (no solution).
If $r_{A} = r_{A B} = n$ (number of unknowns), the system has a unique solution.
If $r_{A} = r_{A B} < n$ , the system has infinitely many solutions, with $n - r_{A}$ free variables.

Key consequence for square systems ( $m = n$ ):

$det (A) \neq = 0 ⟹ r_{A} = n ⟹$ unique solution for any $B$ .
$det (A) = 0 ⟹ r_{A} < n ⟹$ either no solution or infinitely many. You must check $r_{A B}$ to decide.

Geometric Picture in Two Variables

For two equations in $x$ and $y$ , each equation is a line in the plane.

Unique · lines cross

No solution · parallel

Infinite · coincident

Picture	Rank test
Cross	$r_{A} = r_{A B} = 2$
Parallel	$r_{A} = 1, r_{A B} = 2$
Coincident	$r_{A} = r_{A B} = 1$

Systems of Linear Equations and LU Decomposition: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Engineering Mathematics MCQ

For a system of linear equations $A X = B$ with $n$ variables, which of the following conditions guarantees that the system has infinitely many solutions?

A.
$e x t r ank (A) < e x t r ank ([A ∣ B])$
B.
$e x t r ank (A) = e x t r ank ([A ∣ B]) < n$
C.
$e x t r ank (A) = e x t r ank ([A ∣ B]) = n$
D.
$e x t r ank (A) > e x t r ank ([A ∣ B])$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct definition question about the Rouché-Capelli theorem, recognisable because it asks for the condition of infinite solutions in terms of matrix ranks.

Step 1: Recall the consistency condition.

A system $A X = B$ is consistent if and only if $rank (A) = rank ([A ∣ B])$ .

Step 2: Distinguish between unique and infinite solutions.

If the common rank equals the number of variables $n$ , the system has exactly one unique solution.

If the common rank is strictly less than $n$ , there are $n - rank (A)$ free variables, leading to infinitely many solutions.

Step 3: Evaluate the options.

Option A implies inconsistency (no solution).

Option B implies consistency with free variables (infinite solutions).

Option C implies consistency with no free variables (unique solution).

Option D is mathematically impossible.

Answer: B

Question 2 · Engineering Mathematics MCQ

When applying Doolittle's algorithm to factorize a matrix $A$ into $LU$ , what is the very first step in computing the entries of $L$ and $U$ ?

A.
Set the first row of $U$ to be exactly equal to the first row of $A$ .
B.
Compute the first column of $L$ by dividing the first column of $A$ by $a_{11}$ .
C.
Compute the diagonal entries of $U$ by subtracting the products of known entries.
D.
Perform forward substitution on the first row of $A$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is an algorithmic sequence question recognizable by the request for the "first step" of Doolittle's algorithm.

Step 1: Doolittle's algorithm computes $L$ and $U$ by equating $A = LU$ and solving row by row and column by column.

Step 2: The first row of $A$ depends only on the first row of $U$ (since the first row of $L$ is $[1, 0, \dots, 0]$ ).

Step 3: Therefore, the very first step is to copy the first row of $A$ directly into the first row of $U$ .

Answer: A

Question 3 · Engineering Mathematics MCQ

When solving the system $A X = B$ using the LU decomposition $A = LU$ , an intermediate vector $Y$ is introduced such that $U X = Y$ . What equation must $Y$ satisfy?

A.
$A Y = B$
B.
$U Y = B$
C.
$L Y = B$
D.
$Y L = B$

Correct Answer:

Step-by-Step Solution

Key idea: This is a solution strategy question recognizable by the introduction of an intermediate vector $Y$ in the LU solve process.

Step 1: We are given $A X = B$ and $A = LU$ .

Step 2: Substitute $A$ to get $LU X = B$ .

Step 3: We define the intermediate vector $Y$ such that $U X = Y$ .

Step 4: Substituting $Y$ into the equation gives $L Y = B$ . This is the system we solve first using forward substitution.

Answer: C

Question 4 · Engineering Mathematics MCQ

For a $2 \times 2$ linear system $A X = B$ , if the determinant of the coefficient matrix $A$ is zero ( $det (A) = 0$ ), which of the following is definitely true?

A.
The system has no solution.
B.
The system has infinitely many solutions.
C.
The system does not have a unique solution.
D.
The system has exactly one solution.

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of the determinant condition for consistency. It is recognisable because it gives a specific condition (

det (A) = 0

) and asks for the guaranteed nature of the solutions. Step 1: Recall the determinant theorem. For a square system

A X = B

, if

det (A) \neq = 0

, the matrix

A

is invertible, and the system has exactly one unique solution. Step 2: Analyse the given condition. We are given

det (A) = 0

. This means

A

is singular (not invertible). Therefore, the system cannot have a unique solution. Step 3: Determine what else is possible. When

det (A) = 0

, the system is either inconsistent (no solution) or dependent (infinitely many solutions). The exact outcome depends on the constant vector

B

. Step 4: Evaluate the options. Since it could be either "no solution" or "infinitely many solutions", we cannot definitively say it has no solution (Option A) or infinitely many (Option B). However, we can definitively say it does not have a unique solution. Answer: C

Question 5 · Engineering Mathematics MCQ

Given a system $A X = B$ and its LU decomposition $A = LU$ , what is the correct sequence of steps to solve for $X$ ?

A.
Solve $U X = B$ for $X$ , then solve $L Y = X$ for $Y$ .
B.
Solve $L X = B$ for $X$ , then solve $U Y = X$ for $Y$ .
C.
Solve $L Y = B$ for $Y$ , then solve $U X = Y$ for $X$ .
D.
Solve $U X = L$ for $X$ , then solve $L Y = B$ for $Y$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the algorithmic strategy for solving systems using LU decomposition. It is recognisable because it asks for the "sequence of steps" given $A = LU$ .

Step 1: Substitute the decomposition into the system.

The original system is $A X = B$ . Since $A = LU$ , we can write this as $(LU) X = B$ .

Step 2: Use associativity and define an intermediate variable.

Matrix multiplication is associative, so $L (U X) = B$ . Let's define a new vector $Y = U X$ . The equation simplifies to $L Y = B$ .

Step 3: Solve the first system.

We first solve $L Y = B$ for $Y$ . Since $L$ is a lower triangular matrix, this is done efficiently using forward substitution.

Step 4: Solve the second system.

Once we have the vector $Y$ , we substitute it back into our definition $Y = U X$ . We then solve $U X = Y$ for $X$ . Since $U$ is an upper triangular matrix, this is done efficiently using backward substitution.

Step 5: State the sequence.

The correct order is: first solve $L Y = B$ for $Y$ , then solve $U X = Y$ for $X$ .

Answer: C

Question 6 · Engineering Mathematics MCQ

To determine if a parameterized system has no solution, which matrix property must you evaluate?

A.
The ranks of both the coefficient matrix $A$ and the augmented matrix $[A ∣ B]$ .
B.
The rank of the coefficient matrix $A$ only.
C.
The determinant of the augmented matrix $[A ∣ B]$ .
D.
The trace of the coefficient matrix $A$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the consistency of linear systems. It is recognisable because it asks for the specific matrix property used to determine if a system has no solution.

Step 1: Recall the Rouché-Capelli theorem. A linear system $A X = B$ has a solution if and only if the rank of the coefficient matrix $A$ is equal to the rank of the augmented matrix $[A ∣ B]$ .

Step 2: Analyze the condition for "no solution". If the rank of $A$ is strictly less than the rank of $[A ∣ B]$ , the system is inconsistent and has no solution.

Step 3: Evaluate the options. You cannot determine this by looking at $A$ alone (Option B) or $[A ∣ B]$ alone (Option C). You must compare the ranks of both matrices.

Step 4: Conclude. You must evaluate the ranks of both the coefficient matrix $A$ and the augmented matrix $[A ∣ B]$ .

Answer: A

Question 7 · Engineering Mathematics MCQ

If a square matrix $A$ has an LU decomposition $A = LU$ , where $L$ is a unit lower triangular matrix, how can the determinant of $A$ be computed directly from the matrix $U$ ?

A.
It is the sum of the diagonal entries of $U$ .
B.
It is the product of the diagonal entries of $U$ .
C.
It is the determinant of $L$ plus the determinant of $U$ .
D.
It cannot be determined from $U$ alone.

Correct Answer:

Step-by-Step Solution

Key idea: This is a matrix properties question recognizable by the request to find $det (A)$ given its LU decomposition.

Step 1: Recall the multiplicative property of determinants: $det (A) = det (LU) = det (L) det (U)$ .

Step 2: Since $L$ is a unit lower triangular matrix (its diagonal entries are all $1$ ), its determinant is the product of its diagonal entries, so $det (L) = 1$ .

Step 3: Therefore, $det (A) = 1 \times det (U) = det (U)$ .

Step 4: The determinant of any triangular matrix (like $U$ ) is simply the product of its main diagonal entries.

Answer: B

Question 8 · Engineering Mathematics MCQ

During the LU factorization of a matrix $A$ without row swaps, you encounter a step where the computed diagonal entry $u_{k k}$ is zero. What does this imply?

A.
The matrix $A$ is definitely the zero matrix.
B.
The system $A X = B$ has infinitely many solutions.
C.
The matrix $L$ must have a zero on its diagonal.
D.
The standard LU decomposition without row swaps does not exist for this matrix.

Correct Answer:

Step-by-Step Solution

Key idea: This is a boundary case question recognizable by the mention of a "zero pivot" or " $u_{k k} = 0$ " during factorization.

Step 1: In Doolittle's algorithm, to compute the $k$ -th column of $L$ , we must divide by the pivot $u_{k k}$ .

Step 2: If $u_{k k} = 0$ , this division is undefined. The algorithm breaks down.

Step 3: This implies that the standard LU decomposition (without row swaps) does not exist for this matrix. We must use partial pivoting ( $P A = LU$ ).

Answer: D

Question 9 · Engineering Mathematics MCQ

In Doolittle's method for LU decomposition, which matrix is constrained to have all $1$ s on its main diagonal to ensure the factorization is unique?

A.
The lower triangular matrix $L$
B.
The upper triangular matrix $U$
C.
Both the matrices $L$ and $U$
D.
Neither $L$ nor $U$

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition recall question regarding the conventions of LU decomposition, recognizable by the mention of "Doolittle's method".

Step 1: Recall that the equation $A = LU$ has scaling ambiguity. To make the factorization unique, we must fix the diagonal of either $L$ or $U$ to $1$ .

Step 2: Doolittle's convention specifically forces the main diagonal of the lower triangular matrix $L$ to be exactly $1$ . This makes $L$ a unit lower triangular matrix.

Step 3: The upper triangular matrix $U$ retains its original diagonal entries from the factorization process.

Answer: A

Question 10 · Engineering Mathematics MCQ

When solving the system $L Y = B$ using forward substitution, where $L$ is a lower triangular matrix, in which direction are the variables computed?

A.
From $y_{n}$ down to $y_{1}$
B.
From $y_{1}$ up to $y_{n}$
C.
All variables simultaneously
D.
In a random order

Correct Answer:

Step-by-Step Solution

Key idea: This tests the terminology and direction of solving triangular systems in LU decomposition, recognizable by the phrase "forward substitution".

Step 1: Analyze the equation $L Y = B$ . Here, $L$ is lower triangular. The variable $y_{1}$ appears only in the first equation, $y_{1}$ and $y_{2}$ in the second, and so on.

Step 2: Determine the solving order. Since $L$ is lower triangular, we solve for $y_{1}$ first, then substitute it into the second equation to find $y_{2}$ , and continue down to $y_{n}$ . This top-to-bottom process is called Forward Substitution.

Answer: B