Linear Algebra

Most matrix operations — multiplication, inversion, raising to a power — tell you nothing intuitively about what a matrix does geometrically; eigenvalues and eigenvectors are the rare exception that reveal the matrix's inner structure directly, and they underpin everything from Google's PageRank to quantum mechanics to principal component analysis.

Definition: For a square matrix A, a non-zero vector v is an eigenvector with corresponding eigenvalue λ if:

Av = λv

The matrix A maps the vector v to a scalar multiple of itself — it only scales v, it does not rotate or shear it. The scaling factor is λ.

Definition: The characteristic polynomial of A is det(A − λI) = 0. Its roots are the eigenvalues.

Definition: The eigenspace for eigenvalue λ is the null space of (A − λI) — the set of all eigenvectors corresponding to λ, plus the zero vector.

Finding eigenvalues — the characteristic equation

Step 1: Form the matrix (A − λI) by subtracting λ from each diagonal entry.

Step 2: Set det(A − λI) = 0. This gives a polynomial of degree n (for an n×n matrix).

Step 3: Solve the polynomial for λ. The roots are the eigenvalues.

For a 2×2 matrix: det(A − λI) = λ² − (tr A)λ + det A = 0

This is the fastest route for 2×2 problems in GATE and engineering entrances:

• Sum of eigenvalues = trace(A) (sum of diagonal entries)
• Product of eigenvalues = det(A)

Finding eigenvectors — the null space

For each eigenvalue λ, solve the homogeneous system (A − λI)v = 0 by row reduction. The solution space is the eigenspace.

There is always an infinite family of solutions (any scalar multiple of an eigenvector is also an eigenvector). Usually we express the eigenvector as the simplest non-zero representative.

Fully worked example

Question: Find eigenvalues and eigenvectors of A = [[2, 1], [1, 2]].

Solution:

Step 1: Characteristic equation = det(A − λI) = (2−λ)² − 1 = λ² − 4λ + 3 = 0

Step 2: Factorise: (λ−1)(λ−3) = 0 → λ₁ = 1, λ₂ = 3

Step 3: Verify via trace and det:

• Trace = 2+2 = 4 = 1+3 ✓
• Det = 4−1 = 3 = 1×3 ✓

Step 4: Eigenvector for λ₁ = 1:
(A − I) = [[1,1],[1,1]]. Row reduce → [1,1,0]. Solution: v₁ = s·(1, −1) for any scalar s.
Choose v₁ = (1, −1).

Step 5: Eigenvector for λ₂ = 3:
(A − 3I) = [[−1,1],[1,−1]]. Row reduce → [1,−1,0]. Solution: v₂ = s·(1, 1).
Choose v₂ = (1, 1).

Conclusion: Eigenvalues 1 and 3 with eigenvectors (1,−1) and (1,1). Geometrically, this symmetric matrix stretches along the diagonal direction (1,1) by factor 3 and compresses along the anti-diagonal (1,−1) by factor 1 (unchanged).

Key properties of eigenvalues — exam shortcuts

Why the triangular shortcut matters: For a triangular matrix (upper or lower), no computation is needed — the eigenvalues are literally the diagonal. Always check for triangular structure first.

Diagonalization — the payoff

If A has n linearly independent eigenvectors (columns of P), then:

A = PDP⁻¹

where D is diagonal with eigenvalues on the diagonal. Then:

Aᵏ = PDᵏP⁻¹

Raising D to the k-th power is trivial: just raise each diagonal entry to the k-th power. This is the key computational advantage of diagonalization.

When is A diagonalizable? A is diagonalizable if and only if for every eigenvalue, its geometric multiplicity (dimension of eigenspace) equals its algebraic multiplicity (multiplicity as a root of the characteristic polynomial). A matrix with all distinct eigenvalues is always diagonalizable.

Real-world example (India-relevant): A Markov chain modelling student migration between three exam coaching centres can be diagonalized. The eigenvector corresponding to eigenvalue 1 gives the long-run steady-state distribution — how many students each centre will eventually attract regardless of the starting distribution. State-level coaching institute planners use exactly this analysis.

Cayley-Hamilton theorem

Every square matrix satisfies its own characteristic equation.

For a 2×2 matrix with characteristic polynomial λ² − (tr A)λ + (det A) = 0, we have:

A² − (tr A)·A + (det A)·I = 0

Useful application — finding A⁻¹:

Rearranging: (det A)·I = (tr A)·A − A²

→ A⁻¹ = [(tr A)·I − A] / det A (when det A ≠ 0)

This avoids row reduction entirely for 2×2 matrices, and is also valid for higher orders with the appropriate polynomial.

Question: Use Cayley-Hamilton to find A⁻¹ for A = [[2,1],[1,2]].

Solution:

Step 1: tr A = 4, det A = 3. Characteristic equation: A² − 4A + 3I = 0.

Step 2: 3I = 4A − A² → I = (4A − A²)/3 → A⁻¹ = (4I − A)/3.

Step 3: 4I − A = [[4,0],[0,4]] − [[2,1],[1,2]] = [[2,−1],[−1,2]].

Step 4: A⁻¹ = (1/3)[[2,−1],[−1,2]].

Conclusion: A⁻¹ = [[2/3, −1/3], [−1/3, 2/3]]. (Verify: A·A⁻¹ = I ✓)

Applications — why eigenvalues matter beyond the exam

1. Principal Component Analysis (PCA): The eigenvectors of the data covariance matrix are the principal components — the directions of maximum variance. Eigenvalues tell you how much variance each direction explains. Used in face recognition, data compression, genetics.

2. Google PageRank: The importance of a webpage is defined as the leading eigenvector (eigenvalue = 1) of the web's link-transition matrix. The entire search engine ranking is an eigenvalue problem.

3. Structural engineering (vibration analysis): Natural frequencies of a structure (bridge, building) are the square roots of eigenvalues of the mass-normalised stiffness matrix. Engineers must ensure no eigenfrequency matches the frequency of expected loads (earthquake, wind, traffic) to prevent resonance.

4. Quantum mechanics: Observable quantities (energy, momentum, position) are eigenvalues of Hermitian operators (Hamiltonians). The famous time-independent Schrödinger equation is Hψ = Eψ — an eigenvalue equation where E (energy levels) are eigenvalues.

5. Markov chains: The stationary probability distribution is the eigenvector of the transition matrix corresponding to eigenvalue 1 — directly applicable to queuing theory, population genetics, and financial modelling.

:::compare Eigenvalue properties — triangular and symmetric matrices

:::keypoints Key points

• Av = λv: eigenvector v is unchanged in direction; eigenvalue λ is the scaling factor.
• Find eigenvalues: solve det(A − λI) = 0 (characteristic equation).
• Find eigenvectors: solve (A − λI)v = 0 for each λ.
• For 2×2: sum of eigenvalues = trace; product = determinant.
• Triangular matrix: eigenvalues are the diagonal entries directly.
• Symmetric matrix: all eigenvalues are real and eigenvectors are orthogonal.
• Diagonalization: A = PDP⁻¹; enables fast computation of Aᵏ = PDᵏP⁻¹.
• Cayley-Hamilton: every matrix satisfies its characteristic polynomial.
  :::

:::memory
"EIGEN = Extend In Given ENveloped Normal" — the eigenvector extends/compresses in its own direction (no rotation). Or simply: eigenvector keeps its direction, eigenvalue gives the stretch factor.
:::

:::recap

• Eigenvalues are roots of the characteristic polynomial det(A − λI) = 0.
• Eigenvectors are found from the null space of (A − λI) for each λ.
• The trace-sum and determinant-product properties let you verify eigenvalues instantly.
• A matrix is diagonalizable when geometric multiplicity equals algebraic multiplicity for every eigenvalue.
• Cayley-Hamilton theorem gives a formula for A⁻¹ without row reduction.
• Eigenvalues appear in PCA, PageRank, vibration analysis, quantum mechanics, and Markov chains — mastering them here pays dividends across all of GATE and advanced engineering.
  :::

Key determinant facts for GATE: det(AB) = det(A)det(B); det(A^T) = det(A); det(kA) = k^n·det(A) for an n×n matrix; det(A^-1) = 1/det(A). A row/column swap flips the sign; adding a multiple of one row to another leaves det unchanged. det(A) = product of eigenvalues. A triangular matrix's determinant is the product of its diagonal entries. Memory aid: 'SWAP-FLIP, SCALE-power-n, INVERSE-reciprocal.' For a 2×2 [[a,b],[c,d]], det = ad − bc. A matrix is singular (non-invertible) iff det = 0, which means rank < n and at least one eigenvalue is 0. These properties let you avoid full cofactor expansion under exam time pressure.

Rank is the single most expressive number you can attach to a matrix — it tells you, in one integer, how much "real information" the matrix carries. In GATE Engineering Mathematics, rank ties together row operations, solvability of linear systems, invertibility, determinants, and the rank-nullity theorem. Master rank and you have understood half of linear algebra.

Definition: The rank of a matrix A, written rank(A) or ρ(A), is the maximum number of linearly independent rows of A; equivalently, the maximum number of linearly independent columns of A; equivalently, the number of non-zero rows in any row echelon form of A; equivalently, the order of the largest non-zero minor of A.

The fact that all four definitions agree is itself a deep theorem — the row rank equals the column rank, even for a non-square matrix. You can choose whichever definition is most convenient for the problem at hand.

How big can rank get?

For an m × n matrix, rank cannot exceed the number of rows or the number of columns, so

rank(A) ≤ min(m, n).

When rank(A) equals min(m, n) we say A has full rank:

• If m ≤ n and rank = m, A has full row rank — every row is independent.
• If n ≤ m and rank = n, A has full column rank — every column is independent.
• For a square matrix (m = n), full rank means rank = n; this is exactly the condition for invertibility.

For a non-zero matrix, rank is at least 1. The zero matrix is the only matrix with rank 0. A rank-1 matrix has a very special structure: it can always be written as an outer product uvᵀ of two non-zero column vectors. Every row is a scalar multiple of the same vector.

Why it matters — solvability of Ax = b

The most important application of rank is the Rouché-Capelli criterion for the system Ax = b where A is m × n and [A | b] is the augmented matrix:

• The system is inconsistent (no solution) iff rank(A) < rank([A | b]).
• The system is consistent (has at least one solution) iff rank(A) = rank([A | b]).
• The consistent system has a unique solution iff rank(A) = rank([A | b]) = n.
• The consistent system has infinitely many solutions iff rank(A) = rank([A | b]) < n. The solution space has dimension n − rank(A) (this many free parameters).

For a square n × n matrix, rank(A) = n is equivalent to det(A) ≠ 0, which is equivalent to A being invertible, which is equivalent to Ax = 0 having only the trivial solution x = 0.

How to compute rank — Gaussian elimination

The fastest, most reliable method on the GATE exam is:

Step 1: Apply elementary row operations to reduce A to row echelon form. The three legal operations are: swap two rows; multiply a row by a non-zero scalar; add a scalar multiple of one row to another. Each of these preserves rank.
Step 2: Count the number of non-zero rows. That count is rank(A). Equivalently, count the pivots (the first non-zero entry of each non-zero row).

This is fast because elementary row operations are mechanical and the answer falls out instantly once the matrix is in echelon form. You do not need reduced echelon form — plain echelon form is enough.

The other method — finding the largest non-zero minor — is useful for small matrices and for theoretical proofs but is slow for anything larger than 3 × 3.

The Rank-Nullity Theorem

For any m × n matrix A:

rank(A) + nullity(A) = n

where the nullity is the dimension of the null space {x : Ax = 0}, that is, the number of free parameters in the general solution of Ax = 0. This identity is your most powerful shortcut: if you know one of rank or nullity, you know the other.

For example, if A is 4 × 7 and rank(A) = 3, then nullity(A) = 7 − 3 = 4. The homogeneous system Ax = 0 has a 4-parameter family of solutions.

Rank inequalities you should memorise

• rank(AB) ≤ min(rank(A), rank(B)) — multiplication cannot increase rank.
• rank(A + B) ≤ rank(A) + rank(B) — subadditive under addition.
• rank(A) = rank(Aᵀ) = rank(AᵀA) = rank(AAᵀ) — transpose and Gram matrices have the same rank.
• For an outer product, rank(uvᵀ) = 1 whenever u, v ≠ 0.
• rank(A) is invariant under multiplication by an invertible matrix on either side.

The first inequality is the source of many GATE traps. If A is 3 × 5 with rank 2 and B is 5 × 4 with rank 3, then rank(AB) ≤ 2 — multiplication is capped by the smaller rank.

Worked example

Question: Find the rank of A = [[1, 2, 3], [2, 4, 7], [3, 6, 10]].

Solution:
Step 1: Row-reduce. R₂ → R₂ − 2 R₁ gives [0, 0, 1]. R₃ → R₃ − 3 R₁ gives [0, 0, 1].
Step 2: R₃ → R₃ − R₂ gives [0, 0, 0]. The matrix is now [[1, 2, 3], [0, 0, 1], [0, 0, 0]].
Step 3: Count non-zero rows. Two non-zero rows.
Conclusion: rank(A) = 2. Since A is 3 × 3 and rank ≠ 3, det(A) = 0 and A is singular. The homogeneous system Ax = 0 has nullity 3 − 2 = 1, that is, one free parameter.

Why it matters in practice

Rank is the dimension of the column space (image) of A as a linear map. When you build a least-squares regression in machine learning, the design matrix must have full column rank for the normal equations to give a unique solution. When you compress a high-resolution image with SVD, you are throwing away small singular values — equivalently, approximating the image by a lower-rank matrix. The same matrix-rank ideas reappear in network theory, control systems, and computer graphics.

Real-world example: PageRank, the original algorithm behind Google, treats the web as a giant sparse matrix and computes a dominant eigenvector. The numerical stability of that calculation depends fundamentally on whether the matrix has full rank — and many years of mathematical research go into "regularising" near-rank-deficient matrices in industry.

Common misconception: Students confuse rank with the number of non-zero rows of the original matrix. Wrong — the rows of the original matrix may be linearly dependent even when none of them is zero. You must reduce to echelon form first. Three identical non-zero rows give rank 1, not rank 3.

Another misconception: rank(A + B) = rank(A) + rank(B). False in general — consider A = [[1, 0], [0, 0]] and B = [[0, 0], [0, 1]]. Each has rank 1; their sum is the identity, which has rank 2. But A + (−A) has rank 0, not 2 × rank(A). Only the inequality rank(A + B) ≤ rank(A) + rank(B) holds.

:::compare

:::keypoints

• Rank = number of independent rows = number of independent columns = pivots in echelon form.
• rank(A) ≤ min(m, n) for any m × n matrix.
• Square A is invertible iff rank(A) = n iff det(A) ≠ 0.
• Rank-nullity: rank(A) + nullity(A) = n (number of columns).
• Row operations preserve rank; multiplying by an invertible matrix preserves rank.
• rank(AB) ≤ min(rank(A), rank(B)); rank(uvᵀ) = 1 for non-zero u, v.
• Rouché-Capelli: solvability of Ax = b is decided by comparing rank(A) and rank([A | b]).
  :::

:::memory
"Independent Rows = Independent Columns = Pivots = Largest Non-zero Minor" — four definitions, one number. And the soul of the chapter: "Rank tells you how many directions the matrix really uses."
:::

:::recap

• Rank is the most compact description of the "size" of a matrix as a linear map.
• Compute by reducing to row echelon form and counting non-zero rows.
• Rank decides invertibility, solvability of linear systems, and dimensions of null and column spaces.
• Rank-nullity (rank + nullity = n) is your favourite shortcut.
  :::

Find det(A) where A is 3×3 with trace = 6 and you are told eigenvalues are in arithmetic progression with the smallest being 1. AP with smallest 1: eigenvalues λ, λ+d, λ+2d summing to trace = 6, so 3λ+3d = 6 → λ+d = 2 (the middle term). With smallest = 1, middle = 2, largest = 3. Then det(A) = product of eigenvalues = 1×2×3 = 6. This shows two shortcuts: trace = sum of eigenvalues, det = product of eigenvalues. Always use these to bypass cofactor expansion when eigenvalue information is given.

For Ax = b with A an m×n matrix and augmented matrix [A|b]: (1) If rank(A) ≠ rank([A|b]) → INCONSISTENT, no solution. (2) If rank(A) = rank([A|b]) = n (number of unknowns) → UNIQUE solution. (3) If rank(A) = rank([A|b]) = r < n → INFINITELY many solutions with (n − r) free parameters. Memory aid: 'Ranks differ = none; Ranks equal & = unknowns = one; Ranks equal & < unknowns = infinite.' For homogeneous systems Ax = 0, rank([A|0]) always equals rank(A), so they are always consistent (trivial solution exists); they have non-trivial solutions iff rank(A) < n.

When you stare at a 3×3 system on the GATE paper, you have two clean weapons in your toolkit: Cramer's Rule, which is beautiful but expensive, and Gaussian Elimination, which is what computers actually run. Picking the right one — and knowing the time-complexity facts the examiner loves — is what this lesson is about.

Definition: Cramer's Rule solves a square linear system Ax = b (with det(A) ≠ 0) by the formula x_i = det(A_i) / det(A), where A_i is A with its i-th column replaced by the right-hand side vector b.

Definition: Gaussian Elimination reduces the augmented matrix [A | b] to row echelon form through a sequence of elementary row operations, and then recovers the solution by back-substitution from the last equation upward.

Definition: LU decomposition factorises A = L · U into a lower-triangular L and an upper-triangular U so that one expensive O(n³) factor-once step makes every subsequent solve for a new right-hand side cheap (O(n²)).

Cramer's Rule — when it shines, when it doesn't

Cramer's Rule is the algebraic ideal. For a 2×2 system its formula reads off in seconds; for a 3×3 it is still tractable on paper. It is the right tool when:

• The system is small (n = 2 or 3).
• You need a symbolic answer (parameters in the matrix, not just numbers).
• The question explicitly tests conceptual understanding of determinants.

But Cramer's Rule is computationally awful at scale. Computing det(A) by naive cofactor expansion costs O(n!) operations; even with the recursion arranged carefully you end up at O(n! · n). For an n×n system you must compute n+1 determinants — det(A), det(A_1), …, det(A_n). For a 10×10 system that is already > 30 million operations. For a 100×100 system, more than the number of atoms in your laptop. This is why no production linear-algebra library uses Cramer's Rule.

Crucially, Cramer's Rule fails the moment det(A) = 0. That happens when the rows (or columns) of A are linearly dependent — meaning either the system has no solution (inconsistent) or infinitely many solutions (dependent). Cramer's Rule cannot distinguish these two cases; it just refuses to apply. Gaussian elimination handles both gracefully.

Gaussian Elimination — the workhorse

Gaussian elimination is the algorithm every numerical solver descends from. Its three elementary row operations — swap two rows, scale a row by a non-zero constant, add a multiple of one row to another — preserve the solution set. Apply them systematically to put zeros below the diagonal one column at a time, producing an upper-triangular matrix. Then back-substitute from the bottom.

The arithmetic cost is O(n³) — specifically about (2/3) n³ floating-point operations for the elimination plus n² for the back-substitution. That cubic scaling is the single most important number to memorise from this lesson; GATE has tested it in close to every recent year. Compare 10^3 = 1000 operations for n=10 vs Cramer's 30 million — three orders of magnitude faster, and the gap widens as n grows.

Gaussian elimination also tells you, as a side effect, the rank of A, the dimension of its null space, and whether the system is consistent. It is, in that sense, a diagnostic instrument as much as a solver.

Partial pivoting — the numerical-stability fix

Pure Gaussian elimination has a hidden weakness: if a pivot (the diagonal entry you're using to clear the column) is very small relative to the entries below it, dividing by it amplifies floating-point round-off error catastrophically. The standard fix is partial pivoting: before each elimination step, swap rows so that the largest absolute value in the current column sits on the diagonal. This keeps the multipliers ≤ 1 in magnitude and bounds error growth. GATE often phrases it as: "Gaussian elimination with partial pivoting is numerically stable" — that exact sentence has appeared in past papers.

There is also complete pivoting (search both rows and columns), which gives slightly better stability but doubles the bookkeeping cost and is rarely worth it in practice.

LU decomposition — pay once, solve many

Often a system of the form Ax = b must be solved repeatedly with the same A but different b — for example, in finite-element method simulations or in iterative refinement schemes. Gaussian elimination from scratch would cost O(n³) each time. LU does better.

Factor A = LU once (O(n³)). Then for every new b:

1. Solve Ly = b by forward substitution — O(n²).
2. Solve Ux = y by back substitution — O(n²).

So k right-hand sides cost O(n³ + kn²) instead of O(kn³). For k = 100 and n = 1000, that's a 100× speed-up. This is why LU is the standard interface in BLAS / LAPACK, in MATLAB's backslash operator, and inside SciPy's linalg.solve.

The "what does det(A) tell you" decision table

This is the GATE-favourite synthesis question.

• det(A) ≠ 0 → unique solution exists. Cramer's, Gaussian, LU all work. Matrix is invertible.
• det(A) = 0 and the augmented system is consistent → infinitely many solutions (the null space of A is non-trivial). Cramer's Rule fails.
• det(A) = 0 and the augmented system is inconsistent → no solution. Cramer's Rule fails.

To separate the two zero-det cases, compare rank(A) with rank([A | b]) using row-reduction. If they are equal, solutions exist; if not, the system is inconsistent. (Rouché–Capelli theorem.)

Why it matters: Linear systems are the bedrock of every quantitative GATE topic — from circuit analysis (Kirchhoff's equations) to PageRank (eigenvector iteration) to neural network training (least-squares solves). Knowing which solver fits which situation is part of the GATE CSE problem-solving toolkit, and the time-complexity facts are direct one-mark questions.

Real-world example: A real-time route optimisation engine for Indian Railways must solve large sparse linear systems whenever it recomputes travel times after a track event. The engineers don't run Cramer — they pre-compute an LU factorisation of the sparse Laplacian once a day, then service every incoming query in O(n²) time. That choice is literally the difference between "answer in 80 ms" and "answer in 8 minutes."

Common misconception: "Cramer's Rule is faster because the formula looks short." The formula is short; the evaluation of n+1 determinants is what kills it. Symbolic compactness has nothing to do with algorithmic cost.

Common misconception: "If det(A) = 0, the system has no solution." Half-true at best. det(A) = 0 means not unique — the system may have either no solution or infinitely many. You need the augmented-rank check to decide.

Common misconception: "Gaussian elimination without pivoting is fine in practice." For matrices whose diagonal entries are small, naive elimination can produce wildly wrong answers in floating-point even when det(A) is well away from zero. Always pivot.

Question: For an n×n linear system Ax = b with det(A) ≠ 0, what is the asymptotic worst-case running time of Gaussian elimination with partial pivoting?

Solution:
Step 1: Forward elimination dominates. For column k (1 to n−1), it costs O((n−k)²) work to clear the column below the pivot. Sum from k=1 to n−1 gives Θ(n³).
Step 2: Partial pivoting adds an O(n−k) search per column for the max element — negligible compared to the elimination cost.
Step 3: Back substitution is Θ(n²).
Conclusion: Total cost is Θ(n³) — the textbook answer GATE expects, often phrased as "O(n³)."

:::compare

:::keypoints

• Cramer's Rule: x_i = det(A_i)/det(A); short formula, but O(n!) cost — only practical for n ≤ 3.
• Cramer's Rule fails when det(A) = 0; cannot tell no-solution from infinite solutions.
• Gaussian elimination costs O(n³) — memorise this exact bound for GATE.
• Always use partial pivoting for numerical stability; "Gaussian elimination with partial pivoting is numerically stable" is a stock GATE statement.
• LU decomposition factors once, then solves every new b in O(n²) — pay-once-solve-many.
• det(A) ≠ 0 → unique solution; det(A) = 0 → check rank([A|b]) vs rank(A) to distinguish cases.
• Gaussian elimination also yields rank, null-space dimension, and consistency as by-products.
• Gauss–Jordan is just Gaussian extended to reduced row echelon form, costing ~1.5× more.
  :::

:::memory
"Cramer is Cute but Costly; Gauss is Grand and Cubic; LU Lets you Loop." Cute & Costly = closed-form but O(n!). Grand & Cubic = the workhorse at O(n³). LU Lets you Loop = factor once, then every new b is O(n²).
:::

:::recap

• For small or symbolic systems, Cramer's Rule is elegant; for everything else, use Gaussian elimination.
• Gaussian elimination runs in O(n³) and is numerically stable with partial pivoting.
• LU decomposition is the right choice for repeated solves with the same A.
• det(A) = 0 means not unique; pair it with a rank check to settle no-solution vs infinitely-many.
  :::

"Find the value of the parameter k for which the system has no solution." This single phrase has appeared in GATE CSE Engineering Mathematics nearly every alternate year. The procedure is mechanical once you understand what the determinant is really telling you about the geometry of the three planes.

Definition: A system of linear equations Ax = b has a unique solution if and only if the coefficient matrix A is non-singular, i.e., det(A) ≠ 0.

Definition: When det(A) = 0, the system is either inconsistent (no solution) or has infinitely many solutions, depending on the right-hand side b.

The problem

We are given:

x + y + z = 6
x + 2y + 3z = 10
x + 2y + kz = μ

The question is: for what value(s) of k does this system fail to have a unique solution? And once we know that k, the supplementary question is: for what μ is the system inconsistent versus underdetermined?

Step 1 — Set up the coefficient matrix

The coefficient matrix is

A = [[1, 1, 1], [1, 2, 3], [1, 2, k]]

A unique solution to Ax = b exists if and only if det(A) ≠ 0 (Cramer's Rule, or equivalently A is invertible). So we compute det(A) as a function of k and find where it vanishes.

Step 2 — Evaluate the determinant by row reduction

Direct cofactor expansion works but invites sign errors. A cleaner route: subtract row 1 from rows 2 and 3, which does not change the determinant.

Row 2 ← Row 2 − Row 1: [1−1, 2−1, 3−1] = [0, 1, 2]
Row 3 ← Row 3 − Row 1: [1−1, 2−1, k−1] = [0, 1, k−1]

The matrix becomes upper-triangular-ish:

[[1, 1, 1], [0, 1, 2], [0, 1, k − 1]]

Expanding along column 1 (only one non-zero entry, the leading 1):

det(A) = 1 × det([[1, 2], [1, k − 1]]) = 1 × (1 × (k − 1) − 2 × 1) = k − 3

Step 3 — Locate the critical value

A unique solution exists iff det(A) ≠ 0, i.e., k ≠ 3. So the answer to "for what k is there no unique solution?" is k = 3.

But this is not the full story. At k = 3 the system can be either inconsistent (no solution at all) or consistent and underdetermined (infinitely many solutions). Which one occurs depends on μ.

Step 4 — At k = 3, decide between no solution and infinitely many

Substitute k = 3 and look at the row-reduced augmented matrix [A | b]:

[[1, 1, 1 | 6], [0, 1, 2 | 4], [0, 1, 2 | μ − 6]]

Row 3 minus Row 2 gives [0, 0, 0 | μ − 6 − 4] = [0, 0, 0 | μ − 10].

• If μ − 10 ≠ 0, i.e., μ ≠ 10, the last equation reads 0 = (μ − 10), a contradiction — the system has no solution.
• If μ = 10, the last equation reads 0 = 0, which is a tautology — the system reduces to two independent equations in three unknowns and has infinitely many solutions.

So the complete answer:

• k ≠ 3: unique solution (for every μ)
• k = 3 and μ ≠ 10: no solution
• k = 3 and μ = 10: infinitely many solutions

Geometric intuition

Each linear equation in three variables represents a plane in ℝ³. Three planes can intersect in three qualitatively different ways:

• Unique solution: the three planes meet at a single point. This requires the three normal vectors to be linearly independent — equivalent to det(A) ≠ 0.
• No solution: the three planes form a triangular prism, or two are parallel with the third cutting across. No common point exists.
• Infinitely many solutions: the three planes share a common line (or a common plane), giving a one- or two-parameter family of solutions.

At k = 3, the third plane becomes parallel to a linear combination of the first two. The position of the third plane — controlled by μ — then determines whether it shares the same line as the others (giving infinitely many solutions) or sits offset (no solution).

Why it matters: GATE problems are not asking you to solve the system. They are asking you to recognise the geometry. Once you internalise that det(A) = 0 means "the three planes don't pin down a point", every variant of this question becomes one-line work — compute the determinant, set it to zero.

The general GATE pattern

The template for any "find k such that..." problem is:

1. Identify the coefficient matrix A (it does not include the right-hand side b).
2. Compute det(A) as a polynomial in k. Use row operations to keep the algebra clean.
3. Solve det(A) = 0 for the critical k.
4. At each critical k, examine the rank of A versus the rank of the augmented matrix [A | b]:
   • rank(A) = rank([A | b]) = n ⇒ unique solution
   • rank(A) = rank([A | b]) < n ⇒ infinitely many solutions
   • rank(A) < rank([A | b]) ⇒ no solution (inconsistent)

This is the Rouché–Capelli theorem, and it is the master rule of linear systems.

Worked example variant

Question: For what value of k does the system x + 2y + z = 3, 2x + 3y + 2z = 4, 3x + 5y + 3z = k have infinitely many solutions?

Solution:
Step 1: Coefficient matrix A = [[1, 2, 1], [2, 3, 2], [3, 5, 3]]. Notice row 3 = row 1 + row 2 in the coefficient part.
Step 2: det(A) = 0 automatically (linearly dependent rows). So unique solution never exists.
Step 3: For infinitely many solutions, the augmented matrix must also satisfy row 3 = row 1 + row 2, i.e., k = 3 + 4 = 7.
Conclusion: At k = 7, infinitely many solutions; for any other k, no solution.

Real-world example

Real-world example: In civil-engineering network analysis — load distribution across a truss with redundant members — engineers solve linear systems where some equations are dependent. If the loads are consistent with the dependency, infinitely many internal-force distributions are possible (the structure is statically indeterminate). If the loads violate the dependency, the equations are inconsistent and the assumed structure cannot exist as drawn. The same mathematics — Rouché–Capelli — that picks the right k in a GATE problem decides whether a real bridge is solvable.

Common misconception

Common misconception: Many students compute det([A | b]) (a non-square augmented matrix has no determinant — this alone betrays the error) or think that det(A) = 0 always means "no solution". Neither is right. The determinant is computed for the coefficient matrix only, and det(A) = 0 means "no unique solution" — it leaves open whether there are zero or infinitely many solutions. The distinction is made by comparing ranks.

:::compare

| det(A) | rank(A) vs rank([A | b]) | Result |
| --- | --- | --- |
| ≠ 0 | rank(A) = rank([A | b]) = n | Unique solution |
| = 0 | rank(A) = rank([A | b]) < n | Infinitely many solutions |
| = 0 | rank(A) < rank([A | b]) | No solution |
:::

:::keypoints

• For Ax = b, det(A) ≠ 0 iff the system has a unique solution.
• det(A) = 0 is the critical case; further analysis depends on b.
• Use row operations (R2 ← R2 − R1, etc.) to evaluate determinants cleanly.
• For this lesson's system, det = k − 3, so k = 3 is the critical value.
• At k = 3: μ ≠ 10 ⇒ no solution; μ = 10 ⇒ infinite solutions.
• Geometrically, each equation is a plane; the solution set is their intersection.
• The Rouché–Capelli theorem is the master rule — memorise the rank conditions.
• Never compute the determinant of an augmented matrix; it isn't square.
  :::

:::memory
"Det zero, then rank decides." When the coefficient determinant vanishes, the rank of the coefficient matrix versus the augmented matrix tells you whether it is zero solutions or infinite.
:::

:::recap

• Set the coefficient determinant to zero to find the critical parameter.
• At the critical parameter, compare rank(A) with rank([A | b]).
• Equal ranks below n ⇒ infinite solutions; unequal ⇒ no solution.
• Three planes in space: meet at point, share a line, or do not meet at all.
  :::

Eigenvalues are the "natural numbers" attached to a matrix — they reveal how the matrix stretches, rotates and twists space along its preferred directions. For GATE CSE, a small set of properties lets you read off most answers in seconds, without ever solving the characteristic polynomial.

Definition: For a square matrix A of size n × n, a non-zero vector v is an eigenvector and the scalar λ is its eigenvalue if Av = λv. The action of A on v is reduced to a simple scaling by λ — no rotation, no shear, just a stretch (and a flip if λ is negative).

Definition: The characteristic equation of A is det(A − λI) = 0. Its roots are exactly the eigenvalues of A; the equation packages all eigenvalues into one polynomial of degree n.

How the characteristic equation encodes everything

If you expand det(A − λI), you get a polynomial of degree n in λ called the characteristic polynomial. Its coefficients carry information about every algebraic invariant of the matrix. Two of these invariants matter most for GATE-style MCQs and NATs:

• The sum of the eigenvalues equals the trace of A (the sum of its diagonal entries): λ₁ + λ₂ + … + λₙ = tr(A).
• The product of the eigenvalues equals the determinant of A: λ₁ · λ₂ · … · λₙ = det(A).

These are not accidents. They are Vieta's formulas applied to the characteristic polynomial. Whenever a question gives you tr(A) and det(A) for a 2×2 matrix, you already have the eigenvalues, even without writing the polynomial.

Triangular and diagonal matrices: read eigenvalues straight off

For an upper-triangular, lower-triangular or diagonal matrix, the eigenvalues are simply the diagonal entries. This is because det(A − λI) for a triangular matrix is the product of its diagonal entries (a₁₁ − λ)(a₂₂ − λ)…(aₙₙ − λ), so its roots are a₁₁, a₂₂, …, aₙₙ. GATE often hides a triangular matrix inside a question — spot it and skip the algebra.

How eigenvalues transform under common operations

If λ is an eigenvalue of A with eigenvector v, then a function of A often has the same eigenvector with a transformed eigenvalue:

• A^k: eigenvalues are λ^k. Proof: A²v = A(Av) = A(λv) = λ(Av) = λ²v.
• A⁻¹ (only if A is invertible): eigenvalues are 1/λ. Proof: from Av = λv, multiply both sides by A⁻¹/λ to get A⁻¹v = (1/λ)v.
• A^T (transpose): same eigenvalues as A (though not the same eigenvectors in general). Because det(A^T − λI) = det((A − λI)^T) = det(A − λI).
• A + cI: eigenvalues shift by c, giving λ + c. The eigenvectors stay the same.
• kA (scalar multiple): eigenvalues are kλ.

Why it matters: many GATE problems give you a polynomial expression in A — say, A² − 3A + 2I — and ask for its eigenvalues. You don't have to compute the whole matrix. Just substitute each eigenvalue λ of A: the eigenvalues of A² − 3A + 2I are simply λ² − 3λ + 2. This spectral mapping rule is the single most useful trick in this topic.

A worked example using only the properties

Question: For A = [[4, 1], [2, 3]], find the eigenvalues of A² − 5A + 6I.
Solution:
Step 1: tr(A) = 4 + 3 = 7 and det(A) = 4·3 − 1·2 = 10. So sum of eigenvalues = 7 and product = 10.
Step 2: Solve λ² − 7λ + 10 = 0 to get λ = 2 and λ = 5.
Step 3: For any polynomial p, the eigenvalues of p(A) are p(λ). Here p(λ) = λ² − 5λ + 6.
Step 4: p(2) = 4 − 10 + 6 = 0; p(5) = 25 − 25 + 6 = 6.
Conclusion: Eigenvalues of A² − 5A + 6I are 0 and 6. Because 0 is one of them, the matrix is singular.

Singular matrices, symmetry and a few elegant facts

A matrix is singular (non-invertible) if and only if 0 is an eigenvalue of A — equivalent to det(A) = 0 — because the product of eigenvalues is the determinant. This single line answers many "is A invertible?" questions instantly.

For a real symmetric matrix (A = A^T), two famous facts hold:

1. All eigenvalues are real (no imaginary parts at all).
2. Eigenvectors corresponding to distinct eigenvalues are orthogonal.

These together drive the spectral theorem, which underlies PCA, Google's PageRank power-iteration, image compression by SVD, and the analysis of graph Laplacians.

The Cayley–Hamilton theorem

Cayley–Hamilton says: every square matrix satisfies its own characteristic equation. If p(λ) = det(λI − A) is the characteristic polynomial, then p(A) = 0 — the zero matrix. This lets you express A^n (for n ≥ size of A) as a polynomial in A of degree less than n, which is the GATE shortcut for computing high powers and inverses of matrices.

Real-world example: When Google's original PageRank algorithm ran, it was computing the dominant eigenvector of a 25-billion-row matrix representing the web. The dominant eigenvalue was exactly 1 (since the matrix is row-stochastic), and the corresponding eigenvector gave every web page its rank. Eigenvalues are the heartbeat of search engines, neural-network stability analysis, and quantum mechanics.

Common misconception: "Eigenvalues of A and A^T are different because the matrices are different." Wrong — they are equal, because det(A − λI) = det((A − λI)^T) = det(A^T − λI). The eigenvectors, however, are not generally the same.

Common misconception: "If A has eigenvalues 2 and 3, then A + I has eigenvalues 2 and 3 too." Wrong — shifting A by cI shifts every eigenvalue by c, so A + I has eigenvalues 3 and 4. You can verify by substituting (A + I)v = Av + v = λv + v = (λ + 1)v.

Common misconception: "An n×n matrix can have fewer than n eigenvalues." It always has exactly n eigenvalues counted with algebraic multiplicity (over complex numbers). It may have fewer distinct eigenvalues, but the total count from the characteristic polynomial is always n.

:::compare

:::keypoints

• Sum of eigenvalues = trace(A); product of eigenvalues = det(A).
• For triangular or diagonal matrices, eigenvalues are the diagonal entries.
• Eigenvalues of A^k, A⁻¹, A + cI, kA transform predictably while eigenvectors stay the same.
• A^T has the same eigenvalues as A.
• A matrix is singular iff 0 is an eigenvalue.
• Real symmetric matrices have real eigenvalues and orthogonal eigenvectors.
• An n×n matrix has exactly n eigenvalues counted with multiplicity (over ℂ).
• Cayley–Hamilton: A satisfies its own characteristic equation — use it to reduce high powers.
  :::

:::memory
"Trace = Sum, Det = Product" — TSDP. And remember: triangular matrices wear their eigenvalues on their sleeves.
:::

:::recap

• The characteristic equation det(A − λI) = 0 produces all eigenvalues at once.
• Trace and determinant give the sum and product of eigenvalues — often enough to solve a GATE MCQ.
• Spectral mapping: eigenvalues of any polynomial p(A) are just p(λ) for each eigenvalue λ.
• Symmetry, triangularity, and singularity each give powerful eigenvalue shortcuts.
  :::

A is diagonalizable iff it has n linearly independent eigenvectors; then A = PDP^-1 where D is diagonal with eigenvalues and P's columns are eigenvectors. This makes A^k = PD^kP^-1 trivial. Distinct eigenvalues guarantee diagonalizability (sufficient, not necessary). Algebraic multiplicity ≥ geometric multiplicity; defective matrices (geometric < algebraic) are NOT diagonalizable. Cayley-Hamilton theorem: if characteristic polynomial is p(λ), then p(A) = 0; this lets you express A^n and A^-1 in terms of lower powers. Symmetric matrices are always diagonalizable by an orthogonal matrix. Use these to compute high powers of matrices efficiently in exams.

Find eigenvalues of A = [[4,1],[2,3]]. Characteristic equation: det(A − λI) = (4−λ)(3−λ) − (1)(2) = 0. Expand: 12 − 4λ − 3λ + λ^2 − 2 = λ^2 − 7λ + 10 = 0. Factor: (λ − 5)(λ − 2) = 0, so λ = 5, 2. Verify: trace = 4 + 3 = 7 = 5 + 2 ✓; det = 4·3 − 1·2 = 10 = 5 × 2 ✓. Shortcut for 2×2: λ^2 − (trace)λ + det = 0. So you can write λ^2 − 7λ + 10 = 0 directly without expanding. Always cross-check with trace and determinant.

Vectors are linearly independent if c1v1 + ... + ckvk = 0 implies all ci = 0; otherwise dependent. A basis is a linearly independent set that spans the space; every basis of a space has the same number of vectors = the dimension. In R^n any n linearly independent vectors form a basis, and any set of more than n vectors is dependent. To test independence of n vectors in R^n, form a matrix and check det ≠ 0 (independent) or rank = n. The four fundamental subspaces of an m×n matrix A: column space (dim = rank), row space (dim = rank), null space (dim = n − rank), left null space (dim = m − rank). Memory aid: 'Independent + Spanning = Basis.'

For a linear transformation T: V → W (or matrix A, m×n), the Rank-Nullity Theorem states: rank(T) + nullity(T) = dim(domain) = n. Here rank = dim of image/column space, nullity = dim of kernel/null space. T is injective (one-one) iff nullity = 0; T is surjective (onto) iff rank = dim(W). A linear transformation satisfies T(av + bw) = aT(v) + bT(w). The matrix of T depends on chosen bases. Key shortcut: for a square matrix, injective ⟺ surjective ⟺ bijective ⟺ invertible ⟺ det ≠ 0 (all equivalent in finite dimensions). Remember: nullity counts free variables in Ax = 0.

Are v1 = (1,2,3), v2 = (2,4,6), v3 = (1,0,1) linearly independent in R^3? Form matrix rows and compute det of [[1,2,3],[2,4,6],[1,0,1]]. Notice row 2 = 2 × row 1, so two rows are proportional → det = 0 → the set is linearly DEPENDENT. Rank = 2 (v1 and v3 are independent, v2 is redundant). Thus they span only a 2-dimensional subspace (a plane), not all of R^3. Shortcut: whenever one vector is a scalar multiple of another, the set is immediately dependent without computing the full determinant. Dimension of span = rank = 2.