UNIT III: Linear Algebra (Foundations and Applications)

Pravin Chandra

USICT, GGSIPU

November 3, 2025

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 1 / 135
Outline
1 Matrices, Systems, and Vector Spaces
2 Solutions, Cramer’s Rule, and Gauss–Jordan
3 Eigenvalue Problems and Diagonalization
4 Advanced Concepts and Decompositions
5 Questions for Students
6 A few things that I missed in first writing
Cholesky Decomposition (A = LL> )
Skew-Symmetric Matrices
Geometric Interpretation of Matrices
MoorePenrose Pseudoinverse and Least Squares
Numerical Stability and Condition Numbers
Orthogonal Matrices
Eigenvalue Characterization of Special Matrices
References

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 2 / 135
Fundamentals: Matrices and Determinants I
1.1. Matrix Definitions and Operations
Definition and Notation: An m × n matrix A = [aij ]. Entries aij can be complex numbers.
Matrix Operations (Examples): Addition, Scalar Multiplication, and Matrix Multiplication.
Assertion: Matrix Multiplication is Generally Non-Commutative (AB 6= BA)
   
0 1 0 0
Proof: Let A = and B = .
0 0 1 0
    
0 1 0 0 1 0
AB = =
0 0 1 0 0 0
    
0 0 0 1 0 0
BA = =
1 0 0 0 0 1
Since AB 6= BA, the assertion is proved.
1.2. Conjugation and Transposition
Transpose (A> ): (A> )ij = aji .
Complex Conjugate (Ā): (Ā)ij = āij .
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 3 / 135
Fundamentals: Matrices and Determinants II
Hermitian Conjugate (A∗ ): A∗ = (Ā)> . (A∗ )ij = āji .
   
1+i 2 ∗ 1−i 3
A= =⇒ A =
3 4−i 2 4+i

Special Matrices:
Symmetric: A> = A.
Hermitian Matrix: A∗ = A.
Assertion: (AB)> = B> A>
Proof: Let C = AB and D = B> A> . X
(C)ij = aik bkj
k
X
(C> )ij = (C)ji = ajk bki
k

Now, let bik0 = (B> )ik = bki and akj

0
= (A> )kj = ajk .
X 0 0 X X
(D)ij = bik akj = bki ajk = ajk bki
k k k
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 4 / 135
Fundamentals: Matrices and Determinants III

Since (C> )ij = (D)ij for all i, j, the assertion holds.

Assertion: (AB)∗ = B∗ A∗
Proof: By definition, (AB)∗ = (AB)> . Using the transpose property:

(AB)∗ = (B> A> ) = (B> )(A> )

Since (B> ) = B∗ and (A> ) = A∗ , we have (AB)∗ = B∗ A∗ .

1.3. Determinants and Invertibility
Determinants (det(A)): Defined via cofactor expansion.
n
X
det(A) = aij Cij where Cij = (−1)i+j Mij
j=1

Assertion: det(A> ) = det(A)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 5 / 135
Fundamentals: Matrices and Determinants IV
   
a b a c
Proof: For 2 × 2, det = ad − bc. det = ad − cb. They are equal. For n > 2, the
c d b d
proof is by induction on n, noting that the cofactors of A> are the cofactors of A’s corresponding
transpose submatrices.
Assertion: A is invertible if and only if det(A) 6= 0
Proof (⇒): If A is invertible, AA−1 = I. By the multiplicative property of the determinant
(det(AB) = det(A) det(B)):

det(AA−1 ) = det(A) det(A−1 ) = det(I) = 1

Since det(A) det(A−1 ) = 1, det(A) must be non-zero.

1
Proof (⇐): If det(A) 6= 0, the Adjoint Formula (proved below) defines a matrix B = det(A)
adj(A).
Since AB = I, B is the inverse of A, and thus A is invertible.
1.4. The Inverse Matrix and Adjoint Formula
Inverse Definition: A−1 exists if AA−1 = A−1 A = I.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 6 / 135
Fundamentals: Matrices and Determinants V

Adjoint Matrix (adj(A)): The transpose of the matrix of cofactors, adj(A) = [Cij ]> .

1
A−1 = adj(A)
det(A)

Proof (Adjoint Formula): We must show A · adj(A) = det(A)I.

1 The ij-th entry of A · adj(A) is:
n
X n
X
(A · adj(A))ij = aik (adj(A))kj = aik Cjk
k=1 k=1

2 Case i = j (Diagonal Entries):

n
X
aik Cik = det(A)
k=1

This is the standard cofactor expansion definition for det(A) along row i.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 7 / 135
Fundamentals: Matrices and Determinants VI

3 Case i 6= j (Off-Diagonal Entries):

n
X
aik Cjk = 0
k=1

This is the Laplace Expansion Theorem (or cofactor property): the sum of the entries of row i
multiplied by the cofactors of a different row j is the determinant of a matrix with two identical rows
(row j replaced by row i), which must be zero.
Since the product matrix is det(A) on the diagonal and 0 elsewhere, A · adj(A) = det(A)I. Division
by det(A) (when non-zero) yields the formula for A−1 .

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 8 / 135
Example: Calculating the Inverse of a 3x3 Matrix I
1
Method 1: Adjoint Formula (A−1 = det(A)
adj(A))

 
1 2 3
Problem: Find the inverse of the matrix A = 0 1 4.
5 6 0
Step 1: Calculate the Determinant of A Using cofactor expansion along the first column (fewer non-zero
terms):      
1 4 2 3 2 3
det(A) = 1 · det − 0 · det + 5 · det
6 0 6 0 1 4
det(A) = 1 · (1 · 0 − 4 · 6) − 0 + 5 · (2 · 4 − 3 · 1)
det(A) = 1 · (−24) + 5 · (8 − 3) = −24 + 5 · 5 = −24 + 25 = 1
Since det(A) = 1 6= 0, the inverse exists.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 9 / 135
Example: Calculating the Inverse of a 3x3 Matrix II
1
Method 1: Adjoint Formula (A−1 = det(A)
adj(A))

Step 2: Calculate the Matrix of Cofactors C Cij = (−1)i+j Mij .

   
1 4 0 4
C11 = + det = (0 − 24) = −24 C12 = − det = −(0 − 20) = 20
6 0 5 0
   
0 1 2 3
C13 = + det = (0 − 5) = −5 C21 = − det = −(0 − 18) = 18
5 6 6 0
   
1 3 1 2
C22 = + det = (0 − 15) = −15 C23 = − det = −(6 − 10) = 4
5 0 5 6
   
2 3 1 3
C31 = + det = (8 − 3) = 5 C32 = − det = −(4 − 0) = −4
1 4 0 4
 
1 2
C33 = + det = (1 − 0) = 1
0 1
 
−24 20 −5
The matrix of cofactors is C =  18 −15 4 .
5 −4 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 10 / 135
Example: Calculating the Inverse of a 3x3 Matrix III
1
Method 1: Adjoint Formula (A−1 = det(A)
adj(A))

Step 3: Calculate the Adjoint Matrix adj(A) adj(A) = C> :

 
−24 18 5
adj(A) =  20 −15 −4
−5 4 1
   
−24 18 5 −24 18 5
Step 4: Calculate A−1 A−1 = 1
det(A)
adj(A) = 1
1
 20 −15 −4 =  20 −15 −4.
−5 4 1 −5 4 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 11 / 135
Example: Calculating the Inverse of a 3x3 Matrix I
Method 2: Gauss-Jordan Elimination ([A|I] → [I|A−1 ])

 
1 2 3
Problem: Find the inverse of the matrix A = 0 1 4.
5 6 0
Step 1: Form the Augmented Matrix [A|I]
 
1 2 3 1 0 0
 0 1 4 0 1 0 
5 6 0 0 0 1

Step 2: Apply Elementary Row Operations to transform A to I

1 R3 ← R3 − 5R1 : (Eliminate 5 in column 1)
 
1 2 3 1 0 0
 0 1 4 0 1 0 
0 −4 −15 −5 0 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 12 / 135
Example: Calculating the Inverse of a 3x3 Matrix II
Method 2: Gauss-Jordan Elimination ([A|I] → [I|A−1 ])

2 R3 ← R3 + 4R2 : (Eliminate -4 in column 2)

 
1 2 3 1 0 0
 0 1 4 0 1 0 
0 0 1 −5 4 1

3 R2 ← R2 − 4R3 : (Eliminate 4 in column 3)

 
1 2 3 1 0 0
 0 1 0 20 −15 −4 
0 0 1 −5 4 1

4 R1 ← R1 − 3R3 : (Eliminate 3 in column 3)

 
1 2 0 16 −12 −3
 0 1 0 20 −15 −4 
0 0 1 −5 4 1
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 13 / 135
Example: Calculating the Inverse of a 3x3 Matrix III
Method 2: Gauss-Jordan Elimination ([A|I] → [I|A−1 ])

5 R1 ← R1 − 2R2 : (Eliminate 2 in column 2)

 
1 0 0 −24 18 5
 0 1 0 20 −15 −4 
0 0 1 −5 4 1

Step 3: Identify A−1 The right-hand side of the augmented matrix is A−1 :
 
−24 18 5
A−1 =  20 −15 −4
−5 4 1

Both methods yield the same result, confirming the calculation.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 14 / 135
Gauss Elimination, Rank, and Independence I
1.1. Gauss Elimination and Row Equivalence
Gauss Elimination: A systematic procedure using Elementary Row Operations (EROs) on the
augmented matrix [A|b].
Elementary Row Operations (EROs): These operations do not change the solution set of the
linear system, establishing that the resulting matrix is row equivalent to the original.
1 Interchange two rows (Ri ↔ Rj ).
2 Multiply a row by a non-zero scalar (cRi → Ri ).
3 Replace a row by the sum of itself and a multiple of another row (Ri + cRj → Ri ).
Row Echelon Form (REF): Defined by the position of the pivot (leading non-zero entry) in each
row.
Reduced Row Echelon Form (RREF): The unique Echelon form for every matrix; every pivot is
1 and the only non − zero entry in its column.
1.2. Linear Independence and Rank Properties
Linear Independence: Vectors {v1 , . . . , vn } are linearly independent if the equation
c1 v1 + · · · + cn vn = 0 has only the trivial solution (ci = 0).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 15 / 135
Gauss Elimination, Rank, and Independence II
Maximum Rank: For an m × n matrix A, the maximum possible rank is min(m, n). If
rank(A) = min(m, n), the matrix is said to have full rank.
Basis Existence (Established): Every vector space (or subspace) has a basis. The basis vectors
are linearly independent and span the space.
Rank of a Matrix (rank(A)): The number of pivot positions (non-zero rows) in REF.
Theorem (Established): Row Rank = Column Rank = rank(A)
1 Proof Sketch: Row operations preserve the row space; dim(Row(A)) = r . Column dependence
relations are maintained; the r pivot columns form a basis for Col(A).
1.3. Example 1: Finding REF, Rank, and Basis
 
1 3 4
Problem: A = −2 −6 −8. Find rank(A) and bases.
3 5 7
Gauss Elimination to REF:
   
R2 ←R2 +2R1 1 3 4 1 3 4
R3 ←R3 −3R1 R2 ↔R3
A −− −−−−−→ 0 0 0  −− −−→ R = 0 −4 −5
0 −4 −5 0 0 0
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 16 / 135
Gauss Elimination, Rank, and Independence III

Rank and Nullity: rank(A) = 2. Number of free variables (x3 ) is 1. Thus, nullity(A) = 1.
Row Space Basis (Row(A)): Non-zero rows of REF.
    
> >
 1
 0 

Basis(Row(A)) =  3 , −4
 
 4 −5
 


Column Space Basis (Col(A)): Pivot columns (C1, C2) of the original matrix A.
   
 1 3 
Basis(Col(A)) = −2 , −6
3 5
 

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 17 / 135
Gauss Elimination, Rank, and Independence IV
 
−1/4
Null Space Basis (Null(A)): Solving Rx = 0 yields the general solution x = t −5/4.
1
 
 −1 
Basis(Null(A)) = −5 (scaled)
4
 

1.4. The Rank-Nullity Theorem

Assertion: rank(A) + nullity(A) = n (number of columns).
Proof (Detailed): Let r = rank(A). There are r pivot columns and n − r non-pivot (free)
columns. Since nullity(A) equals the number of free variables, nullity(A) = n − r . Summing these
dimensions proves the assertion: r + (n − r ) = n.
Verification for Ex 1: 2 + 1 = 3 (Correct).
1.5. Example 2: Non-Square Matrix

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 18 / 135
Gauss Elimination, Rank, and Independence V

 
1 0 2 1
Problem: Find the rank and the null space basis for B = 0 1 3 0. B is 3 × 4.
1 1 5 1
Gauss Elimination to RREF:
   
1 0 2 1 1 0 2 1
R ←R −R1 R ←R −R2
B −−3−−−3−−→ 0 1 3 0 −−3−−−3−−→ R0 = 0 1 3 0
0 1 3 0 0 0 0 0

R0 is in RREF.
Rank and Nullity: rank(B) = 2 (Pivots in C1, C2). n = 4.

nullity(B) = n − r = 4 − 2 = 2

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 19 / 135
Gauss Elimination, Rank, and Independence VI

Null Space Basis (Null(B)): Solve R0 x = 0. Free variables: x3 = t1 , x4 = t2 .

x2 + 3x3 = 0 =⇒ x2 = −3t1
x1 + 2x3 + x4 = 0 =⇒ x1 = −2t1 − t2
     
x1 −2 −1
x2  −3 0
x= x3  = t1  1  + t2  0 
    

x4 0 1
    

 −2 −1 
    
−3 , 0 

Basis(Null(B)) = 
 1
    0 

0 1
 

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 20 / 135
Vector Space (V): Comprehensive Theory and Applications I
1.1. Vector Space Definition and Axioms
Definition: A Vector Space (V) over a field F (usually R or C) is a non-empty set of objects
(vectors) closed under vector addition and scalar multiplication, satisfying the following 10 axioms.
Axioms (Detailed):
1 Closure under Addition: u + v ∈ V (Internal operation).
2 Commutativity of Addition: u + v = v + u.
3 Associativity of Addition: (u + v) + w = u + (v + w).
4 Zero Vector: There exists a unique 0 ∈ V such that u + 0 = u.
5 Negative Vector (Additive Inverse): For each u, there is a unique −u such that u + (−u) = 0.
6 Closure under Scalar Multiplication: cu ∈ V for all c ∈ F (External operation).
7 Distributivity I: c(u + v) = cu + cv.
8 Distributivity II: (c + d)u = cu + du.
9 Associativity of Scalar Multiplication: c(du) = (cd)u.
10 Multiplicative Identity: 1u = u.
1.2. Example Proof: Pn is a Vector Space
Assertion: The set of polynomials Pn (degree ≤ n) is a vector space over R.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 21 / 135
Vector Space (V): Comprehensive Theory and Applications II
Proof Sketch (Closure):
1 Closure under Addition: deg(p + q) ≤ max(deg(p), deg(q)) ≤ n. The sum remains in Pn .
2 Closure under Scalar Multiplication: deg(cp) = deg(p) ≤ n. The scalar multiple remains in Pn .
3 The remaining 8 axioms are satisfied because polynomial addition and scalar multiplication are
performed component-wise on the real coefficients, inheriting the field properties. The zero
polynomial is the additive identity.
1.3. Subspaces and Linear Span
Subspaces (W): A subset W of V that is itself a vector space.
Subspace Test (Established): A non-empty subset W is a subspace if it satisfies the
three closure properties: 1) contains the zero vector (or W is non-empty), 2)
closed under addition, and 3) closed under scalar multiplication.
Linear Span (span(S)): The set of all possible linear combinations of the vectors in
S = {v1 , . . . , vk }.
Assertion (Established): The span of any finite set of vectors is always a subspace of V.
Key Subspaces Related to A:
Null(A) (Kernel): Solution space to Ax = 0. (Subspace of Rn ).
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 22 / 135
Vector Space (V): Comprehensive Theory and Applications III
Col(A) (Range): Span of the columns of A. (Subspace of Rm ).
Row(A): Span of the rows of A. (Subspace of Rn ).
1.4. Example: Checking for a Subspace
  
x1
Problem: Is W = : x2 = 2x1 ⊂ R2 a subspace?
x2
Subspace Test Check:
1 Zero Vector: 0 = 2(0), so 0 ∈W. (Satisfied)
   
x1 y1 x1 + y1
2 Closed under Addition: u = ,v= . u+v = . (Satisfied)
2x1 2y 2(x1 + y1 )
1 
cx1
3 Closed under Scalar Multiplication: cu = . (Satisfied)
2(cx1 )
Conclusion: W is a subspace of R2 .
1.5. Basis, Dimension, and Unique Representation
Basis: A set of vectors that is both linearly independent and spans V. It is a
maximal linearly independent set and a minimal spanning set.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 23 / 135
Vector Space (V): Comprehensive Theory and Applications IV

Dimension (dim(V)): The unique number of vectors in any basis for V.

Assertion (Established): Invariance of Dimension Theorem
1 Theorem: If V has a basis of n vectors, then every basis of V must consist of exactly n vectors.
2 Proof Sketch: Relies on the fact that if a set of vectors spans a space, then any linearly independent
set in that space cannot have more vectors than the spanning set (Steinitz Exchange Lemma).
Assertion: Unique Representation Theorem
Theorem (Detailed Proof): If B = {b1 , . . . , bn } is a basis for V, then every vector v ∈ V has a
unique representation v = c1 b1 + · · · + cn bn .
1 Existence: Guaranteed by the spanning property. P P
2 Uniqueness
P (Proof): Assume v has two representations, v = ci b i = di bi . Subtracting gives
0 = (ci − di )bi . By the linear independence of B, all coefficients must be zero:
ci − di = 0 =⇒ ci = di .
Coordinates Relative to a Basis ([v]B ): The unique coefficients {c1 , . . . , cn } form the
coordinate vector of v relative to B.
1.6. Example: Coordinates and Dimension

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 24 / 135
Vector Space (V): Comprehensive Theory and Applications V

Example (Dimension of P2 ): The standard basis B = {1, x, x 2 } is linearly independent and spans
P2 . dim(P2 ) = 3.
Example (Coordinates): Let p(x) = 5 − 2x + 4x 2 in P2 .
The coordinates of p(x) relative to the standard basis B = {1, x, x 2 } are:
 
5
[p(x)]B = −2
4

Geometric Interpretation: The coordinate vector [v]B maps the vector v from the abstract vector
space V to a unique coordinate vector in Rn , allowing the use of matrix tools.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 25 / 135
Solutions to Linear Systems: Existence and Uniqueness I
Ranks, Consistency Theorem, and Solution Types

1.1. Existence and Consistency

Linear System: Ax = b, where A is the m × n coefficient matrix, x is the n × 1 vector of
variables, and b is the m × 1 constant vector.
Vector Equation Form: The system is equivalent to a vector equation:
x1 a1 + x2 a2 + · · · + xn an = b, where ai are the columns of A.
Consistency Theorem (Proof of Existence in Column Space): The system Ax = b is
consistent (has a solution) if and only if b lies in the Column Space (Col(A)) of A. This is the
fundamental definition of consistency in terms of vector combinations.
Rank Criterion for Consistency (Proof by Pivot Analysis): Ax = b has a solution if and only if:

rank(A) = rank([A|b])

1 Proof:

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 26 / 135
Solutions to Linear Systems: Existence and Uniqueness II
Ranks, Consistency Theorem, and Solution Types

(⇒) If consistent, then ranks are equal. If Ax = b is consistent, b is a linear combination of A’s
columns. Therefore, the column space of A and the column space of [A|b] are identical
(Col(A) = Col([A|b])). Since the rank is the dimension of the column space, their ranks must be equal:
rank(A) = rank([A|b]). b introduces no new pivot column in the REF.
(⇐) If ranks are equal, then consistent. Assume rank(A) = rank([A|b]) = r . When the augmented
matrix [A|b] is reduced to its Row Echelon Form (REF), the equality of ranks guarantees that the last
column (the b column) does not contain a pivot. The only way the system Ax = b can be inconsistent is
if the REF contains a row representing the contradiction 0 = c where c 6= 0, i.e., a row of the form
[0 . . . 0|c]. This row would introduce a pivot in the last column, making rank([A|b]) = r + 1, which
contradicts the initial assumption rank(A) = rank([A|b]). Thus, the system must be consistent.
1.2. Uniqueness of Solutions
Unique Solution: The system is consistent AND:

rank(A) = n (number of variables/columns)

This implies that every column in A is a pivot column, leading to no free variables in the
solution set. The Null Space of A is trivial (Null(A) = {0}).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 27 / 135
Solutions to Linear Systems: Existence and Uniqueness III
Ranks, Consistency Theorem, and Solution Types

Infinitely Many Solutions: The system is consistent AND:

rank(A) < n

The number of free variables is n − rank(A) (the Nullity), which defines the dimension of the
non-trivial Null Space. Any vector in the Null Space can be added to a particular solution to form
an infinite number of solutions.
No Solution (Inconsistent): rank(A) < rank([A|b]).
1.3. Summary for Square Matrices A (m = n)
det(A) 6= 0 ⇐⇒ rank(A) = n ⇐⇒ Ax = b has a Unique solution.
det(A) = 0 ⇐⇒ rank(A) < n ⇐⇒ No solution or Infinitely many solutions.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 28 / 135
II. Gaussian Elimination (Forward Elimination) I
Method for Solving Ax = b and Identifying Solution Set

2.1. Method Overview and Terminology

Goal: Transform the augmented matrix [A|b] into its Row Echelon Form(REF) using
Elementary Row Operations(EROs): (1) Row swapping (Ri ↔ Rj ), (2) Scaling a row
(cRi → Ri ), and (3) Row replacement (Ri + cRj → Ri ).
REF Properties: (1) All non-zero rows are above any rows of all zeros. (2) Each leading entry
(pivot) of a row is in a column to the right of the leading entry of the row above it. (3) All entries
in a column below a pivot are zero.
Procedure (Forward Pass): Systematically create zeros below each pivot position (the first
non-zero entry in a row), starting from the top-left, until the matrix is in REF.
Solution Method (Back Substitution): Once in REF, solve the resulting upper triangular system
by expressing the basic variables (those corresponding to pivot columns) in terms of the constants
and free variables (those corresponding to non-pivot columns), starting from the bottom equation.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 29 / 135
II. Gaussian Elimination (Forward Elimination) II
Method for Solving Ax = b and Identifying Solution Set

2.2. Complete Worked Example: Unique Solution

Problem: Solve the system x1 + 2x2 + x3 = 0, 2x1 + 2x2 + x3 = 0, x1 + 2x2 + 3x3 = 2.
Step 1: Form and Eliminate to REF (Forward Pass)
   
1 2 1 0 R2 ←R2 −2R1 1 2 1 0
R3 ←R3 −R1
[A|b] =  2 2 1 0  −−−−−−−→  0 −2 −1 0  (REF reached)
1 2 3 2 0 0 2 2

Step 2: Back Substitution (Reverse Pass) System in REF:

x1 + 2x2 + x3 = 0, −2x2 − x3 = 0, 2x3 = 2.
1 x3 from R3 : 2x3 = 2 =⇒ x3 = 1.
2 x2 from R2 : −2x2 − (1) = 0 =⇒ −2x2 = 1 =⇒ x2 = −1/2.
3 x1 from R1 : x1 + 2(−1/2) + 1 = 0 =⇒ x1 − 1 + 1 = 0 =⇒ x1 = 0.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 30 / 135
II. Gaussian Elimination (Forward Elimination) III
Method for Solving Ax = b and Identifying Solution Set



0
Solution: x = −1/2.
1
2.3. Complete Worked Example: Infinite Solutions
Problem: Solve x1 + 2x2 − 3x3 = 1, 2x1 + 4x2 − 6x3 = 2.
   
1 2 −3 1 R2 ←R2 −2R1 1 2 −3 1
[A|b] = −−−−−−−→
2 4 −6 2 0 0 0 0

rank(A) = 1 (one pivot). n = 3. System is consistent.

Basic variable: x1 . Free variables: x2 , x3 . nullity(A) = 3 − 1 = 2.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 31 / 135
II. Gaussian Elimination (Forward Elimination) IV
Method for Solving Ax = b and Identifying Solution Set

General Solution (Parametric Vector Form): Let x2 = t1 ∈ R, x3 = t2 ∈ R.

x1 = 1 − 2x2 + 3x3 = 1 − 2t1 + 3t2

       
1 − 2t1 + 3t2 1 −2 3
x= t1  = 0 + t1  1  + t2 0 (Infinitely many solutions)
t2 0 0 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 32 / 135
Cramer’s Rule: Theory and Detailed Example I
Determinant-Based Solution for Non-Singular Systems

3.1. Statement and Prerequisite

Prerequisite: Applies exclusively to square (n × n) systems where the coefficient matrix A is
non − singular (det(A) 6= 0). It is rarely used for systems n > 3 due to high computational cost
(O(n!)) compared to Gaussian Elimination (O(n3 )).
Formula: The unique solution components xi are given by the ratio of determinants:

det(Ai )
xi = for i = 1, 2, . . . , n
det(A)

where Ai is the matrix formed by replacing the i-th column of A with the constant vector b.
3.2. Proof of Cramer’s Rule (Complete Derivation)
Since det(A) 6= 0, the unique solution is x = A−1 b. We use the Adjoint Formula for the inverse:

1 1
A−1 = adj(A) =⇒ x = adj(A)b
det(A) det(A)
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 33 / 135
Cramer’s Rule: Theory and Detailed Example II
Determinant-Based Solution for Non-Singular Systems

The i-th component of the solution vector x is (x)i :

n
1 X
(x)i = (adj(A))ij bj
det(A)
j=1

By the definition of the adjoint matrix, (adj(A))ij = Cji (the cofactor of aji ):
n
1 X
(x)i = bj Cji
det(A)
j=1

Now, consider det(Ai ). Expanding det(Ai ) along the i-th column (which is b), we get
P n 0 0
j=1 (Ai )ji Cji . Since (Ai )ji = bj and the cofactors Cji are identical to Cji (because cofactors do not
involve the column being expanded), we have:
n
X
det(Ai ) = bj Cji
j=1
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 34 / 135
Cramer’s Rule: Theory and Detailed Example III
Determinant-Based Solution for Non-Singular Systems

Substituting this back into the expression for (x)i :

det(Ai )
xi =
det(A)

3.3. Complete Worked Example: Cramer’s Rule

Problem: Solve the system 2x1 + x2 = 7 and −x1 + 3x2 = 0.
   
2 1 7
A= , b=
−1 3 0

Steps:
1 Calculate det(A): det(A) = (2)(3) − (1)(−1) = 6 − (−1) = 7.
 
7 1
2 Calculate det(A1 ): A1 = =⇒ det(A1 ) = (7)(3) − (1)(0) = 21.
0 3
 
2 7
3 Calculate det(A2 ): A2 = =⇒ det(A2 ) = (2)(0) − (7)(−1) = 7.
−1 0
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 35 / 135
Cramer’s Rule: Theory and Detailed Example IV
Determinant-Based Solution for Non-Singular Systems

Solution:
det(A1 ) 21 det(A2 ) 7
x1 = = = 3, x2 = = =1
det(A) 7 det(A) 7

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 36 / 135
Gauss–Jordan Elimination for Matrix Inverse I
Finding A−1 via Reduced Row Echelon Form (RREF)

4.1. Method Overview and RREF Definition

Goal: To find the unique inverse of a non-singular square matrix A.
Procedure: Form the augmented matrix [A|I] and apply EROs until the left side is transformed
into RREF.
RREF Properties: The matrix satisfies all REF properties AND (4) Each pivot is equal to 1. (5)
Each pivot is the only non − zero entry in its column (i.e., zeros are created above and below
each pivot).
Result: Since A is non-singular, its RREF is I, leading to the final form [I|A−1 ].
Justification (Complete Proof):
1 The sequence of EROs applied to A is equivalent to premultiplying A by a product of
Elementary Matrices, E = Ek · · · E1 .
2 The operation on the augmented matrix is E[A|I] = [EA|EI].
3 Since the sequence transforms A to I, we must have EA = I. By the definition of the inverse, this
product E must be the inverse matrix, E = A−1 .

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 37 / 135
Gauss–Jordan Elimination for Matrix Inverse II
Finding A−1 via Reduced Row Echelon Form (RREF)

4 Consequently, the right-hand side is EI = A−1 I = A−1 , proving that the final augmented form is
[I|A−1 ].
4.2. Complete Worked Example:
 Gauss–Jordan
 (3x3)
1 0 3
Problem: Find A−1 for A =  2 1 7.
−3 2 0
Step 1: Form [A|I]  
1 0 3 1 0 0
 2 1 7 0 1 0 
−3 2 0 0 0 1
Step 2-3: Forward Pass (Gaussian Elimination to REF)
R2 ← R2 − 2R1 , R3 ← R3 + 3R1
R3 ← R3 − 2R2

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 38 / 135
Gauss–Jordan Elimination for Matrix Inverse III
Finding A−1 via Reduced Row Echelon Form (RREF)

 
1 0 3 1 0 0
 0 1 1 −2 1 0 
0 0 7 7 −2 1
Step 4: Normalize and Backward Pass (RREF)
R3 ← 17 R3 (Normalizing the last pivot to 1)
 
1 0 3 1 0 0
 0 1 1 −2 1 0 
0 0 1 1 −2/7 1/7

R2 ← R2 − R3 , R1 ← R1 − 3R3 (Clearing entries above pivots)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 39 / 135
Gauss–Jordan Elimination for Matrix Inverse IV
Finding A−1 via Reduced Row Echelon Form (RREF)

 
1 0 0 −2 6/7 −3/7
 0 1 0 −3 9/7 −1/7 
0 0 1 1 −2/7 1/7
Conclusion: The RREF of A is I, and the inverse is:
 
−2 6/7 −3/7
A−1 = −3 9/7 −1/7
1 −2/7 1/7

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 40 / 135
Gauss–Jordan Elimination for Solving Ax = b I
Solving Linear Systems and Characterizing All Solution Types via RREF

5.1. Method Definition and Theoretical Basis

Goal: Transform the augmented matrix [A|b] into its Reduced Row Echelon Form(RREF). The
RREF is unique for any given matrix.
Procedure (RREF): The method consists of two main passes using Elementary Row Operations
(EROs):
1 Forward Pass (Gaussian Elimination): Create zeros below each pivot to reach
Row Echelon Form(REF).
2 Backward Pass (Gauss–Jordan):
Normalization: Convert all pivots to 1 (e.g., Ri ← c1 Ri ).
Zeroing Above: Use EROs to create zeros above each pivot, starting from the rightmost pivot and
moving left/upwards.
Advantage: The RREF of [A|b] immediately provides the values of the basic variables in terms of
the constants and any free variables (if they exist), eliminating the need for separate
back-substitution.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 41 / 135
Gauss–Jordan Elimination for Solving Ax = b II
Solving Linear Systems and Characterizing All Solution Types via RREF

5.2. Detailed Analysis of Solution Types via RREF

The RREF of [A|b] allows for immediate and definitive identification of the solution type based on rank
and the location of pivots:
1 Unique Solution (Consistent & Full Rank)
Conditions: The number of pivot columns in A is equal to the number of variables n.
rank(A) = rank([A|b]) = n.
Interpretation: Every variable is a basic variable; there are no free variables.
RREF Form: The matrix A is reduced to the identity matrix I.
General Form (RREF): The solution vector x is explicitly read from the constant column c where
xi = ci .    
1 0 0 . . . c1 c1
 0 1 0 . . . c2  c2 
 0 0 1 . . . c3  =⇒ x = xp = c3 
   
.. .. .. . . .. ..
   
. . . . . .
2 Infinitely Many Solutions (Consistent & Rank Deficient)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 42 / 135
Gauss–Jordan Elimination for Solving Ax = b III
Solving Linear Systems and Characterizing All Solution Types via RREF

Conditions: rank(A) = rank([A|b]) = r < n. There are n − r non-pivot columns, corresponding to

n − r free variables (nullity > 0).
Interpretation: The free variables can be chosen arbitrarily (e.g., set to parameters t1 , t2 , . . . ), and
the basic variables are expressed in terms of these parameters.
RREF Form: The matrix has at least one row of all zeros, and pivot columns alternate with non-pivot
columns.
General Solution Structure: x = xp + xh , where:
xp is the particular solution (obtained by setting all free variables to zero).
xh is the homogeneous solution (a linear combination of the basis vectors for the Null Space, derived
from the free variables).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 43 / 135
Gauss–Jordan Elimination for Solving Ax = b IV
Solving Linear Systems and Characterizing All Solution Types via RREF

Example (3 × 3, rank = 2, x3 is free):


x3 = t (free variable, t ∈ R)
 
1 0 d1 k1 
 0 1 d2 k2  =⇒ x2 = k2 − d2 t
0 0 0 0

x1 = k1 − d1 t


The parametric vector form is derived by separating constants and parameter multiples:
   
k1 −d1
x = k2  + t −d2  (Infinitely many solutions)
0 1

3 No Solution (Inconsistent)
Conditions: The number of pivot columns in A is strictly less than the number of pivot columns in
[A|b]. rank(A) < rank([A|b]).
Interpretation: The system is inconsistent because the final row operations yield a mathematical
contradiction.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 44 / 135
Gauss–Jordan Elimination for Solving Ax = b V
Solving Linear Systems and Characterizing All Solution Types via RREF

RREF Form: The RREF contains a zero row in A with a non − zero entry in the constant column b.
Example (3 × 3):
 
1 0 ∗ ∗
 0 1 ∗ ∗  where c 6= 0
0 0 0 c
The last row explicitly translates to 0x1 + 0x2 + 0x3 = c. Since c 6= 0, this is the statement 0 = c,
which is impossible, meaning the system has no solution.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 45 / 135
LU Decomposition and System Solving (A = LU) I
Detailed Factorization, PLU Generalization, and Fast System Resolution

1. Definition and Detailed Structure of A = LU

Definition: A is a square matrix factored into A = LU. This factorization exists if and only if all
leading principal minors (determinants of the top-left square submatrices) of A are non-zero.
L is a Unit Lower Triangular matrix:
 
1 0 ... 0
l21 1 . . . 0
L= . (Stores Gaussian Elimination multipliers lij )
 
.. .. .. 
 .. . . .
ln1 ln2 ... 1

U is an Upper Triangular matrix:

 
u11 u12 ... u1n
 0 u22 ... u2n 
U= . (The Row Echelon Form (REF) of A)
 
.. .. .. 
 .. . . . 
0 0 ... unn
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 46 / 135
LU Decomposition and System Solving (A = LU) II
Detailed Factorization, PLU Generalization, and Fast System Resolution

Derivation Principle: A = LU is realized by recognizing that the product of the inverses of the
elementary row matrices Ek used in elimination (where Ek · · · E1 A = U) forms the lower triangular
matrix L.
2. The General PLU Factorization (Handling Pivoting/Row Exchanges)
Necessity of Permutation: When a pivot element uii is zero, A = LU fails, and a row swap
(pivoting) is necessary for elimination to continue.
PLU Form: The most general and robust factorization, which exists for any non-singular matrix
A, is:
PA = LU
P is a Permutation Matrix (formed by rearranging the rows of I). It records the necessary row
exchanges to bring non-zero pivots into the diagonal position, ensuring all leading principal minors
of PA are non-singular.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 47 / 135
LU Decomposition and System Solving (A = LU) III
Detailed Factorization, PLU Generalization, and Fast System Resolution

3. Step-by-Step Solution of Ax = b using LU

The computational cost for solving systems drops from O(n3 ) (for direct Gaussian elimination on A for
every b) to O(n2 ) (after a single O(n3 ) factorization).
1 Pre-Step: Factorization: Find L and U such that A = LU.
2 Step 1: Forward Substitution (Solve Ly = b)
Substitute A = LU into Ax = b to get L(Ux) = b.
Let y = Ux. The first intermediate system is Ly = b.
Solve this lower triangular system for y sequentially, starting with the first equation (y1 ).
3 Step 2: Back Substitution (Solve Ux = y)
Substitute the calculated vector y into Ux = y.
Solve this upper triangular system for x sequentially, starting with the last equation (xn ).
4. Worked Example for
 LUFactorization
2 1
Problem: Factor A = into LU and confirm LU = A.
4 7

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 48 / 135
LU Decomposition and System Solving (A = LU) IV
Detailed Factorization, PLU Generalization, and Fast System Resolution

1 Elimination (Finding U): Apply R2 ← R2 − 2R1 . The multiplier m21 = 2 is stored for L.
   
2 1 R2 −2R1 2 1
A= −−−−−→ U =
4 7 0 5

2 Construct L: Place the multiplier m21 = 2 in position (2, 1) of the unit lower triangular matrix.
 
1 0
L=
2 1

3 Verification:
      
1 0 2 1 (1)(2) + (0)(0) (1)(1) + (0)(5) 2 1
LU = = = =A
2 1 0 5 (2)(2) + (1)(0) (2)(1) + (1)(5) 4 7

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 49 / 135
Cholesky Decomposition (A = LL> ) I
Symmetric Positive Definite Matrices and Recursive Algorithms

1. Condition for Existence and Special Form

Condition for Existence (Establishment): Cholesky decomposition exists if and only if A is a
Symmetric Positive Definite (SPD) matrix.
Symmetry: A = A> (or A = A∗ for complex matrices).
Positive Definite: x> Ax > 0 for all non-zero vectors x ∈ Rn . Equivalently, all eigenvalues must be
positive.
Formulation: The decomposition is A = LL> , where L is a Lower Triangular matrix with
positive diagonal entries. This L is unique.
 
l11 0 ... 0
l21 l22 ... 0
L= .
 
.. .. .. 
 .. . . .
ln1 ln2 ... lnn

2. Computational Advantages and Proof Justification

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 50 / 135
Cholesky Decomposition (A = LL> ) II
Symmetric Positive Definite Matrices and Recursive Algorithms

Efficiency: Cholesky factorization is approximately twice as fast as generic LU factorization

because it computes only n(n + 1)/2 elements of L (exploiting A’s symmetry) compared to n2 for
LU. The complexity is O( 31 n3 ).
Stability: It is inherently numerically stable and does not require pivoting (row swaps), provided
A is genuinely SPD.
Proof of Positive Definite Requirement: The formulas used in the Cholesky algorithm require
calculating the square root of aii − lik2 . For the entries of L to be real numbers, the term inside
P
the square root must always be positive. This is guaranteed if and only if A is positive definite. If
A is merely symmetric, this decomposition might not exist in the real number domain.
3. Detailed Cholesky–Banachiewicz Algorithm (Recursive Formulas)
The entries of L are calculated column by column, from top to bottom, using the following recursive
formulas, derived from equating Aij = (LL> )ij :
For j = 1 to n (Column Index):

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 51 / 135
Cholesky Decomposition (A = LL> ) III
Symmetric Positive Definite Matrices and Recursive Algorithms

1 Calculate Diagonal Entry (ljj ): v

u
u j−1
X
ljj = tajj − ljk2
k=1

This step requires taking the square root, which confirms the numerical requirement for SPD. The
sum term represents the contribution from the previously calculated entries in the j-th row of L.
2 Calculate Off-Diagonal Entries (lij for i > j):
j−1
!
1 X
lij = aij − lik ljk
ljj
k=1

This step expresses the off-diagonal entries as a difference between the matrix entry aij and the dot
product of the j-th column and i-th row of the already calculated part of L, normalized by the
diagonal entry ljj .

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 52 / 135
Cholesky Decomposition (A = LL> ) IV
Symmetric Positive Definite Matrices and Recursive Algorithms

4. Worked Example:  Cholesky

 Factorization
4 12
Problem: Factor A = into LL> . (Note: A is SPD.)
12 37
 
l 0
The matrix L has the form L = 11 .
l21 l22
1 Column 1 (j = 1):
q √
a11 − 0k=1 . . . = 4 = 2.
P
l11 (Diagonal, i = j = 1): l11 =
1
(a21 − 0k=1 . . . ) = 12 (12) = 6.
P
l21 (Off-Diagonal, i = 2, j = 1): l21 = l11
2 Column 2 (j = 2):
q √ √
a22 − 1k=1 l2k
p
2 2
P
l22 (Diagonal, i = j = 2): l22 = = a22 − l21 = 37 − 62 = 37 − 36 = 1.
Result:       
2 0 2 0 2 6 4 12
L= =⇒ LL> = = =A
6 1 6 1 0 1 12 37

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 53 / 135
The Matrix Eigenvalue Problem: Fundamentals (Expanded) I
Determining Eigenvalues, Eigenvectors, Eigenspaces, and Related Theorems

1. Definition and Core Equation

Definition: The Eigenvalue Problem seeks non-zero vectors x and scalars λ that satisfy the
relationship:
Ax = λx
λ: The Eigenvalue (or characteristic value). It represents a scaling factor. If λ = 0, the
eigenvector lies in the Null Space of A.
x: The Eigenvector (or characteristic vector, x 6= 0). It represents a direction that is preserved
under the linear transformation A.
Geometric Interpretation: When the transformation A is applied to x, the resulting vector Ax is
simply a scalar multiple (λ) of the original vector x, meaning x’s direction is unchanged (or
reversed if λ < 0).
Normalization: Any scalar multiple of an eigenvector is also an eigenvector. Often, eigenvectors
are normalized to be unit vectors (length 1).
2. The Characteristic Equation (The Algorithm for λ)
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 54 / 135
The Matrix Eigenvalue Problem: Fundamentals (Expanded) II
Determining Eigenvalues, Eigenvectors, Eigenspaces, and Related Theorems

Rearrangement: The core equation is rewritten as Ax − λx = 0, which requires factoring out x by

inserting the identity matrix I:
(A − λI)x = 0
Existence Condition: For a non-zero solution x to exist, the coefficient matrix (A − λI) must be
singular (non-invertible). This is crucial because only non-invertible matrices have a non-trivial null
space.
Characteristic Equation: The condition for singularity is det(A − λI) = 0. The roots of this
polynomial equation (in λ) are the Eigenvalues.
Characteristic Polynomial: The polynomial p(λ) = det(A − λI) has degree n for an n × n matrix
A. By the Fundamental Theorem of Algebra, A has n eigenvalues (counting complex and repeated
roots).
Matrix Property Connection: For any matrix A:
Pn
The Trace of A (sum of diagonal entries) equals the sum of the eigenvalues:
Qn tr(A) = i=1 λi .
The Determinant of A equals the product of the eigenvalues: det(A) = i=1 λi . This implies A is
invertible if and only if all λi 6= 0.
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 55 / 135
The Matrix Eigenvalue Problem: Fundamentals (Expanded) III
Determining Eigenvalues, Eigenvectors, Eigenspaces, and Related Theorems

3. Eigenspaces and Multiplicity

Eigenspace (Eλ ): For a given eigenvalue λ, the set of all solutions x to (A − λI)x = 0 is the
Eigenspace corresponding to λ. It is precisely the Null Space of the matrix (A − λI):

Eλ = Null(A − λI)

Since it is a Null Space, it is a subspace of Rn . The basis vectors for Eλ are the linearly
independent eigenvectors.
Algebraic Multiplicity (AM): The number of times λ appears as a root of the characteristic
polynomial p(λ). It dictates the maximum number of independent eigenvectors associated with λ.
Geometric Multiplicity (GM): The dimension of the Eigenspace Eλ , which is the number of
linearly independent eigenvectors associated with λ. It is calculated using the Rank-Nullity
Theorem:
GM(λ) = dim(Null(A − λI)) = n − rank(A − λI)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 56 / 135
The Matrix Eigenvalue Problem: Fundamentals (Expanded) IV
Determining Eigenvalues, Eigenvectors, Eigenspaces, and Related Theorems

Fundamental Relationship: For any eigenvalue λ, the geometric multiplicity is always

less than or equal to the algebraic multiplicity: GM(λ) ≤ AM(λ). If GM < AM, the matrix is
defective and not diagonalizable.
4. Complex Eigenvalues and Related Theorems
Complex Eigenvalues: If the characteristic polynomial has real coefficients (i.e., A is a real
matrix), complex eigenvalues always occur in conjugate pairs (λ and λ). Their corresponding
eigenvectors are also complex conjugates.
Cayley–Hamilton Theorem: Every square matrix A satisfies its own characteristic equation. If
p(λ) is the characteristic polynomial of A, then substituting A for λ yields the zero matrix:

p(A) = 0

Triangular Matrices: The eigenvalues of a triangular matrix (upper or lower) are simply the
entries on its main diagonal.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 57 / 135
Example: Full Eigenvalue and Eigenvector Calculation I
Detailed Step-by-Step Procedure for a 2 × 2 Matrix
 
2 1
Problem: Find the eigenvalues and a basis for the eigenspaces of A = .
1 2
Step 1: Determine Eigenvalues using the Characteristic Equation
Form the matrix (A − λI) and set its determinant to zero:
 
2−λ 1
det(A − λI) = det
1 2−λ

= (2 − λ)(2 − λ) − (1)(1) = (2 − λ)2 − 1 = 0

Expand and solve the characteristic polynomial:

(λ2 − 4λ + 4) − 1 = 0 =⇒ λ2 − 4λ + 3 = 0

Factorization yields the roots:

(λ − 3)(λ − 1) = 0
Eigenvalues: λ1 = 3 and λ2 = 1. (AM=1 for both).
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 58 / 135
Example: Full Eigenvalue and Eigenvector Calculation II
Detailed Step-by-Step Procedure for a 2 × 2 Matrix

Step 2: Find Eigenspace for λ1 = 3

Solve the homogeneous system (A − 3I)x = 0:
   
2−3 1 −1 1
A − 3I = =
1 2−3 1 −1

The corresponding system of equations is:

−x1 + x2 = 0 and x1 − x2 = 0

Both equations reduce

 to x1=x2 . Let x2 = t (free variable). Then x1 = t. The general form of the
t 1
eigenvector is x = =t .
t 1
 
1
Eigenspace E3 basis: x1 = . (GM(λ1 ) = 1).
1
Step 3: Find Eigenspace for λ2 = 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 59 / 135
Example: Full Eigenvalue and Eigenvector Calculation III
Detailed Step-by-Step Procedure for a 2 × 2 Matrix

Solve the homogeneous system (A − 1I)x = 0:

   
2−1 1 1 1
A − 1I = =
1 2−1 1 1

The corresponding system of equations is:

x1 + x2 = 0

= −x2 . Letx2 =
This reduces to x1   s (free variable). Then x1 = −s. The general form of the
−s −1
eigenvector is x = =s .
s 1
 
−1
Eigenspace E1 basis: x2 = . (GM(λ2 ) = 1).
1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 60 / 135
Diagonalization and Eigenbases I
Conditions for Diagonalizability and The Diagonalization Process

1. Diagonalization Principle
Goal: To find a factorization A = PDP−1 such that D is a diagonal matrix containing the
eigenvalues of A.
The Relationship: Multiplying by P−1 on the left gives the similarity transformation:

D = P−1 AP

D: The diagonal matrix where Dii = λi .

P: The Modal Matrix, composed of the corresponding linearly independent eigenvectors as its
columns.
2. Conditions for Diagonalizability
Theorem 1 (Fundamental Condition): An n × n matrix A is diagonalizable if and only if there
exists an Eigenbasis for Rn (i.e., a set of n linearly independent eigenvectors of A).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 61 / 135
Diagonalization and Eigenbases II
Conditions for Diagonalizability and The Diagonalization Process

Theorem 2 (Multiplicity Test): A is diagonalizable if and only if GM(λ) = AM(λ) for every
eigenvalue λ of A.
Theorem 3 (Distinct Eigenvalues): If an n × n matrix A has n distinct eigenvalues, then A is
automatically diagonalizable (since the eigenvectors are guaranteed to be linearly independent).
3. Special Matrix Properties
Symmetric Matrix (A = A> ):
1 All eigenvalues are real. (No complex eigenvalues).
2 Eigenvectors corresponding to distinct eigenvalues are orthogonal.
3 The matrix is always diagonalizable.
Orthogonal Matrix (Q> = Q−1 ):
1 Eigenvalues always have a magnitude of one: |λ| = 1.
2 The matrix preserves the length of a vector (kQxk = kxk) and the angle between two vectors.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 62 / 135
Diagonalization and Eigenbases III
Conditions for Diagonalizability and The Diagonalization Process

Spectral Theorem (for Symmetric A): If A is symmetric, it is orthogonally diagonalizable.

This means the matrix P can be chosen to be an Orthogonal Matrix (P−1 = P> ), simplifying the
diagonalization:

D = P> AP (P is orthogonal and its columns form an orthonormal eigenbasis)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 63 / 135
Quadratic Forms and Principal Axes (Comprehensive) I
Analyzing Second-Degree Polynomials via Orthogonal Diagonalization

1. Definition and Matrix Representation

Definition: A Quadratic Form in n variables is a function Q(x) : Rn → R that is a second-degree
polynomial with no constant or first-degree terms. For n = 2: Q(x1 , x2 ) = ax12 + bx22 + cx1 x2 .

Q(x) = a11 x12 + a22 x22 + · · · + ann xn2 + 2a12 x1 x2 + . . .

Matrix Form: Every quadratic form can be uniquely written as:

Q(x) = x> Ax

where A is a Symmetric Matrix (A = A> ). The diagonal entries of A are the coefficients of the
squared terms (aii ), and the off-diagonal entries are half the coefficients of the mixed terms
(aij = aji = 12 · coefficient of xi xj ).
Example Construction (n = 2): For Q(x) = 5x12 + 3x22 + 4x1 x2 :
 
5 2 1
A= (Note: a12 = a21 = (4) = 2)
2 3 2
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 64 / 135
Quadratic Forms and Principal Axes (Comprehensive) II
Analyzing Second-Degree Polynomials via Orthogonal Diagonalization

2. The Principal Axes Theorem (Eliminating Cross-Terms)

Purpose: The theorem provides a method to eliminate the cross − product terms (xi xj terms
where i 6= j) in the quadratic form, simplifying its geometry.
Mechanism (Spectral Theorem): Since A is symmetric, the Spectral Theorem guarantees it is
orthogonally diagonalizable. We find an orthogonal matrix P (columns are orthonormal
eigenvectors) and a diagonal matrix D (diagonal entries are eigenvalues λi ) such that:

D = P> AP

Coordinate Change: By performing an orthogonal change of variable x = Py (where y is the new

coordinate vector), the form is transformed into its Canonical Form (a weighted sum of squares):

Q(x) = y> Dy = λ1 y12 + λ2 y22 + · · · + λn yn2

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 65 / 135
Quadratic Forms and Principal Axes (Comprehensive) III
Analyzing Second-Degree Polynomials via Orthogonal Diagonalization

Principal Axes: The new coordinate axes (y1 , y2 , . . . , yn ) are called the Principal Axes. These
axes are aligned with the eigenvectors (columns of P) of the matrix A. This transformation P
corresponds to a pure rotation or reflection of the coordinate system, rotating the axes to align
with the shape’s natural symmetry.
3. Classification of Quadratic Forms (Definiteness)
The nature of the quadratic form (and the surface it defines, e.g., a conic section or quadric surface) is
entirely determined by the signs of the eigenvalues (λi ) of the associated symmetric matrix A.
Alternative Test (Leading Principal Minors): For a test that avoids finding eigenvalues (often
complex), one can use the sign pattern of the Leading Principal Minors (determinants of the
top-left square submatrices Ak ):
1 Positive Definite: det(Ak ) > 0 for all k = 1, . . . , n.
2 Negative Definite: The signs of det(Ak ) alternate, starting with negative: det(A1 ) < 0,
det(A2 ) > 0, det(A3 ) < 0, and so on.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 66 / 135
Quadratic Forms and Principal Axes (Comprehensive) IV
Analyzing Second-Degree Polynomials via Orthogonal Diagonalization

Classification Eigenvalue Conic/Quadric Value Range of

Condition Surface Q(x)
Positive All Ellipse / Ellipsoid Q(x) > 0 for all
Definite λi > 0 x 6= 0
Negative All Ellipse Q(x) < 0 for all
Definite λi < 0 (opening downward) x 6= 0
Indefinite λi are Hyperbola / Q(x) takes both
mixed Hyperboloid / Saddle +ve and -ve values
Positive All λi ≥ 0 Parabolic Q(x) ≥ 0
Semidefinite (at least one λi = 0) Cylinder
Negative All λi ≤ 0 Parabolic Q(x) ≤ 0
Semidefinite (at least one λi = 0) Cylinder

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 67 / 135
Gram-Schmidt Process (Expanded and Detailed Example) I
Constructing Orthonormal Bases and the Projection Formula

1. Goal and Motivation

Goal: Transform a linearly independent set of vectors {a1 , . . . , ak } that spans a subspace W into
an orthonormal set {q1 , . . . , qk } that spans the same subspace W .
Why Orthonormal? Orthonormal bases simplify calculations significantly, especially projections,
coordinates, and least-squares problems (since Q> Q = I). This means the inverse of the matrix
formed by the basis vectors is simply its transpose.
Procedure Core: The process recursively ensures that each new vector vk is orthogonal to all
previously constructed vectors {v1 , . . . , vk−1 }.
2. The Gram-Schmidt Procedure (Detailed Steps)
1 Start (First Vector): The first orthogonal vector is simply the first given vector:

v1 = a1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 68 / 135
Gram-Schmidt Process (Expanded and Detailed Example) II
Constructing Orthonormal Bases and the Projection Formula

2 Orthogonalization (General Step): For each subsequent vector ak , subtract its projection onto
the subspace spanned by the previously found orthogonal vectors {v1 , . . . , vk−1 }:
k−1
X
vk = ak − projvj (ak )
j=1

The projection formula (the component of ak parallel to vj ) is explicitly given by:

 
ak · v1 ak · v2 ak · vk−1
vk = ak − v1 + v 2 + · · · + vk−1
||v1 ||2 ||v2 ||2 ||vk−1 ||2
3 Normalization (Converting to Unit Length): Convert the orthogonal vectors {vk } into
orthonormal unit vectors {qk }:
vk
qk =
||vk ||

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 69 / 135
Gram-Schmidt Process (Expanded and Detailed Example) III
Constructing Orthonormal Bases and the Projection Formula

3. Worked Example (n = 2)    
1 2
Problem: Orthonormalize the basis vectors a1 = 1 and a2 = 1.
0 1
1 Step 1: Orthogonal Vector v1  
1
v1 = a1 = 1
0
2 Step 2: Orthogonal Vector v2 Calculate the projection of a2 onto v1 :
a2 · v1
projv1 (a2 ) = v1
||v1 ||2

Dot Product: a2 · v1 = (2)(1) + (1)(1) + (1)(0) = 3.

Squared Length: ||v1 ||2 = 12 + 12 + 02 = 2.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 70 / 135
Gram-Schmidt Process (Expanded and Detailed Example) IV
Constructing Orthonormal Bases and the Projection Formula

   
1 3/2
3 3 1 = 3/2.
Projection: projv1 (a2 ) = v
2 1
= 2
0 0
Subtract the projection from a2 :
     
2 3/2 1/2
v2 = a2 − projv1 (a2 ) = 1 − 3/2 = −1/2
1 0 1

(Check orthogonality: v1 · v2 = 1(1/2) + 1(−1/2) + 0(1) = 0. Confirmed.)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 71 / 135
Gram-Schmidt Process (Expanded and Detailed Example) V
Constructing Orthonormal Bases and the Projection Formula

3 Step 3: Normalization (Finding q1 and q2 )

For q1 :  
√ 1
v1 1  
||v1 || = 2 =⇒ q1 = =√ 1
||v1 || 2 0

For q2 :
||v2 ||2 = (1/2)2 + (−1/2)2 + 12 = 1/4 + 1/4 + 1 = 6/4 = 3/2
√ √
   
1/2 1
p 3 v2 2 1
||v2 || = 3/2 = √ =⇒ q2 = =√ −1/2 = √ −1
2 ||v2 || 3 6
1 2
Final Orthonormal Basis: {q1 , q2 }
4. QR Factorization Connection
The Gram-Schmidt process leads directly to the QR Factorization: A = QR.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 72 / 135
Gram-Schmidt Process (Expanded and Detailed Example) VI
Constructing Orthonormal Bases and the Projection Formula

A: The matrix whose columns are the original vectors {a1 , . . . , ak }.

Q: The matrix whose columns are the resulting orthonormal vectors {q1 , . . . , qk }. Q is an
orthogonal matrix (Q> Q = I).
R: An Upper Triangular matrix derived from the projection coefficients and normalizations used
in the Gram-Schmidt process.
Geometric Interpretation of QR: A (the initial basis) is factored into Q (a rotation/reflection)
and R (a scaling/shear transformation).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 73 / 135
QR Factorization (A = QR) I
Decomposition via Orthonormal Columns and Applications

1. Definition and Construction

Definition: The QR Factorization decomposes an m × n matrix A (with linearly independent
columns) into the product of an orthogonal/orthonormal matrix Q and an upper triangular matrix
R:
A = QR
Q: An m × n matrix with orthonormal columns. (Q> Q = I, where I is n × n).
R: An n × n Upper Triangular matrix with positive diagonal entries.
Construction Method: The factorization is directly generated by applying the
Gram − Schmidt Process to the columns of A.
1 The columns of Q are the orthonormal vectors {q1 , . . . , qn } obtained from the Gram-Schmidt process.
2 The entries of R are derived from the projection coefficients and the lengths of the orthogonal vectors
(vk ):
i−1
X
rij = aj · qi for i < j and rii = ||ai − projqk (ai )|| = ||vi ||
k=1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 74 / 135
QR Factorization (A = QR) II
Decomposition via Orthonormal Columns and Applications

2. Geometric Interpretation and Properties

Interpretation: The factorization represents the columns of A (an arbitrary basis for Col(A))
being expressed in terms of the orthonormal basis Q. The R matrix holds the necessary
rotation, scaling, and projection coefficients to transform the orthonormal basis Q back to the
original basis A.
Determinant Property: Since R is triangular, det(R) is the product of its diagonal entries. For
square matrices, det(A) = det(Q) det(R). If Q is square (i.e., A is square), det(Q) = ±1, so
| det(A)| = det(R).
Uniqueness: The QR factorization is unique if we require the diagonal entries of R to be positive
(which is standard).
3. Applications in Numerical Linear Algebra

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 75 / 135
QR Factorization (A = QR) III
Decomposition via Orthonormal Columns and Applications

1. Solving Least-Squares Problems: The system Ax = b for inconsistent systems is solved by

the normal equations A> Ax = A> b. Using A = QR:

(QR)> (QR)x = (QR)> b =⇒ R> (Q> Q)Rx = R> Q> b

Since Q> Q = I, this simplifies to R> Rx = R> Q> b. Since R is full rank, R> is invertible, allowing
us to simplify further:
Rx = Q> b
This final system is solved quickly and stably using Back Substitution, making QR the preferred
numerical method for least-squares.
2. Eigenvalue Computation (The QR Algorithm): Repeatedly applying the QR factorization
iteratively, Ak = Qk Rk and setting Ak+1 = Rk Qk , causes the sequence of matrices Ak to
converge to a triangular (or block-triangular) form, from which the eigenvalues can be read
directly from the diagonal. This is one of the most stable and widely used methods for finding all
eigenvalues of a general matrix.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 76 / 135
Cayley Hamilton Theorem (Statement and Explicit Applications) I
Matrix Polynomials and The Power to Invert and Simplify

1. Formal Statement
Statement: Every square matrix A satisfies its own characteristic equation. This means that if
we substitute the matrix A for the scalar variable λ in the characteristic polynomial p(λ), the result
is the zero matrix.
Characteristic Polynomial: For an n × n matrix A, the characteristic polynomial p(λ) is:

p(λ) = det(A − λI) = (−1)n λn + cn−1 λn−1 + · · · + c1 λ + c0

Matrix Equation: The theorem states that:

p(A) = (−1)n An + cn−1 An−1 + · · · + c1 A + c0 I = 0 (The zero matrix)

Theoretical Significance: The theorem establishes a fundamental link between the algebraic
properties (eigenvalues) and the matrix structure, showing that the matrix is implicitly ”defined” by
its own eigenvalues.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 77 / 135
Cayley Hamilton Theorem (Statement and Explicit Applications)
II
Matrix Polynomials and The Power to Invert and Simplify

2. Application 1: Computing the Matrix Inverse (A−1 )

The theorem provides an explicit, non-iterative formula for the inverse, provided the matrix is
non-singular.
Invertibility Condition: A is invertible if and only if its determinant is non-zero. Since
c0 = det(A), we require c0 6= 0.
Derivation: Start with the characteristic equation evaluated at A:

(−1)n An + cn−1 An−1 + · · · + c1 A + c0 I = 0

Isolate the constant term (which is multiplied by I):

c0 I = −A (−1)n An−1 + cn−1 An−2 + · · · + c1 I

Since AA−1 = I, multiply both sides by A−1 and divide by −c0 :

1 
A−1 = − (−1)n An−1 + cn−1 An−2 + · · · + c1 I

c0
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 78 / 135
Cayley Hamilton Theorem (Statement and Explicit Applications)
III
Matrix Polynomials and The Power to Invert and Simplify

Completeness Note: This method gives A−1 as a linear combination of integer powers of A
(from A0 = I up to An−1 ).
3. Application 2: Computing High Powers of A (Ak )
The Cayley-Hamilton equation allows us to express the highest power, An , as a linear combination
of lower powers (I, A, . . . , An−1 ).

(−1)n An = −cn−1 An−1 − · · · − c1 A − c0 I

By multiplying this relationship by A, we can express An+1 in terms of powers up to An , and then
substitute the expression for An to reduce the expression back down to powers of An−1 or less.
This means any power Ak (for k ≥ n) can be efficiently computed as a matrix polynomial of
degree at most n − 1:
Ak = dn−1 An−1 + · · · + d1 A + d0 I

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 79 / 135
Singular Value Decomposition (SVD) (Comprehensive) I
The Most General Factorization for Any Matrix and Its Geometric Meaning

1. Definition and Detailed Structure

Universality: SVD is the only major matrix decomposition that exists for any m × n matrix A,
regardless of whether it is square, invertible, or symmetric.
Decomposition Form: For any m × n matrix A, the factorization is:

A = UΣV>

U (m × m): The Left Singular Vectors. An Orthogonal Matrix (U> U = I). Its columns form
an orthonormal basis for the Column Space and Null Space of A> .
V (n × n): The Right Singular Vectors. An Orthogonal Matrix (V> V = I). Its columns form
an orthonormal basis for the Row Space and Null Space of A.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 80 / 135
Singular Value Decomposition (SVD) (Comprehensive) II
The Most General Factorization for Any Matrix and Its Geometric Meaning

Σ (m × n): A generalized diagonal matrix. Its non-zero diagonal entries are the Singular Values
(σi ), arranged in non-increasing order:
 
σ1 0

 σ2 

Σ=
 . .. 

 
0 σr 
0 0

2. Relationship to Eigenvalue Decomposition

Singular Values (σi ): The singular values are the square roots of the eigenvalues of the
symmetric, positive semi-definite matrix A> A (or AA> ):
q
σi = λi (A> A) (where λi (A> A) ≥ 0)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 81 / 135
Singular Value Decomposition (SVD) (Comprehensive) III
The Most General Factorization for Any Matrix and Its Geometric Meaning

Connecting Bases:
1 The columns of V (Right Singular Vectors) are the Eigenvectors of A> A.
2 The columns of U (Left Singular Vectors) are the Eigenvectors of AA> .
3. The Four Fundamental Subspaces
SVD provides canonical orthonormal bases for all four fundamental subspaces associated with A. Let r
be the number of non-zero singular values.

Subspace SVD Basis Vectors

Row Space (Col(A> )) {v1 , . . . , vr } (First r columns of V)
Null Space (Null(A)) {vr +1 , . . . , vn } (Last n − r columns of V)
Column Space (Col(A)) {u1 , . . . , ur } (First r columns of U)
Left Null Space (Null(A> )) {ur +1 , . . . , um } (Last m − r columns of U)

4. Key Applications

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 82 / 135
Singular Value Decomposition (SVD) (Comprehensive) IV
The Most General Factorization for Any Matrix and Its Geometric Meaning

1 Rank and Structure: The Rank of A is exactly r , the number of non-zero singular values
(σi > 0).
2 Pseudo − inverse (A† ): SVD allows the construction of the Moore-Penrose Pseudoinverse, which
generalizes the matrix inverse to non-square or singular matrices:

A† = VΣ† U>

where Σ† is formed by taking the reciprocal of the non-zero singular values (σi → 1/σi ) and
transposing. This is crucial for solving general Least Squares problems (Ax ≈ b).
3 Low − Rank Approximation: The Eckart − Young Theorem states that the best rank-k
approximation (Ak ) to A is achieved by retaining only the first k terms in the outer product
expansion of A. This is the foundation for Data Compression (e.g., image and data processing):
r
X k
X
A= σi ui vi> =⇒ Ak = σi ui vi> (k < r )
i=1 i=1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 83 / 135
Calculating the Singular Value Decomposition (A = UΣV> ) I
Two Primary Methods for SVD Construction

1. Method 1: Eigenvalue Decomposition (The Standard Theoretical Method)

This method relies on computing the eigenvalues and eigenvectors of the symmetric matrix A> A (or
AA> ) to find V, Σ, and then U. This is the most common method taught for manual computation.
Step 1: Compute V and Σ from A> A
1 Calculate the symmetric matrix B = A> A.
2 Find the eigenvalues (λi ) of B and order them: λ1 ≥√λ2 ≥ · · · ≥ λn ≥ 0.
3 The Singular Values (σi ) are the square roots: σi = λi .
4 Construct the diagonal matrix Σ using σi (padding with zeros if m 6= n).
5 Find the orthonormal eigenvectors (vi ) of B. These vectors form the columns of the V matrix:
V = [v1 |v2 | . . . |vn ].
Step 2: Compute U (Left Singular Vectors)
1 For i = 1 to r (where r is the rank, or number of non-zero σi ), calculate the left singular vectors
directly using the singular values and right singular vectors:
1
ui = Avi
σi
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 84 / 135
Calculating the Singular Value Decomposition (A = UΣV> ) II
Two Primary Methods for SVD Construction

2 If m > r , find the remaining m − r columns of U ({ur +1 , . . . , um }) by finding an orthonormal basis

for the Null Space of A> (or by using Gram-Schmidt on a random set of vectors orthogonal to
{u1 , . . . , ur }).
Detailed Worked Example (Method
 1)

1 1
Problem: Find the SVD of A = . (m = 2, n = 2)
0 0
Step 1.1: Calculate B = A> A
    
> 1 0 1 1 1 1
A A= =
1 0 0 0 1 1

Step 1.2: Find Eigenvalues of B

 
1−λ 1
det(B − λI) = det = (1 − λ)2 − 1 = λ2 − 2λ = 0
1 1−λ

Eigenvalues are λ1 = 2 and λ2 = 0.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 85 / 135
Calculating the Singular Value Decomposition (A = UΣV> ) III
Two Primary Methods for SVD Construction

Step 1.3: Find Σ and σi

√ √
√ 
2 0
σ1 = 2 and σ2 = 0 = 0 =⇒ Σ =
0 0

Step 1.4: Find Eigenvectors of B (Columns of V)

   
−1 1 1 1
For λ1 = 2: (B − 2I)v1 = 0 =⇒ v = 0 =⇒ v1 = v2 . Normalizing: v1 = 2
√ .
1 −1 1 1
   
1 1 1
For λ2 = 0: (B − 0I)v2 = 0 =⇒ v = 0 =⇒ v1 = −v2 . Normalizing: v2 = √12 .
1 1 2 −1
 
1 1 1
V= √
2 1 −1
√
Step 2: Find U Only one non-zero singular value (σ1 = 2), so r = 1.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 86 / 135
Calculating the Singular Value Decomposition (A = UΣV> ) IV
Two Primary Methods for SVD Construction
√
For σ1 = 2:        
1 1 1 1 1 1 1 2 1
u1 = Av1 = √ √ = =
σ1 2 0 0 2 1 2 0 0
For u2 (Orthogonal complement / Null Space of A> ): We need a unit vector orthogonal to u1 .
 
0
u2 =
1
 
1 0
U=
0 1
Final Check:
  √    √     
> 1 0 2 0 1 1 1 2 0 1 1 1 1 1
UΣV = √ = √ = =A
0 1 0 0 2 1 −1 0 0 2 1 −1 0 0

2. Method 2: Iterative QR Algorithm (Numerical Method)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 87 / 135
Calculating the Singular Value Decomposition (A = UΣV> ) V
Two Primary Methods for SVD Construction

Principle: The numerical computation of SVD (as used in software like MATLAB or NumPy)
typically uses a stable, iterative process, most famously an adaptation of the QR Algorithm or
variations of the Jacobi Method.
Initial Reduction: First, the matrix A is usually reduced to a bidiagonal matrix B using
Householder reflections: A = U0 BV0> .
Iteration: The QR algorithm is then applied to B> B (or implicitly to B) to find its
eigenvalues/singular values. This iterative process converges to the final diagonal matrix Σ.
Advantage: While complex for manual work, this method is significantly
more numerically stable and faster for large matrices than the explicit eigenvalue method
(Method 1), which involves calculating A> A and its entire eigen-decomposition.
Note: A detailed worked example of the full iterative QR algorithm is beyond the scope of a
presentation slide and is generally reserved for specialized numerical analysis courses.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 88 / 135
Student Exercises (1-9): Rank, Systems, and Subspaces I
 
1 2 1
Q1. Rank and Nullity Find the rank and nullity of A = 2 4 2. Solution Q1:
    0 1 1
1 2 1 1 2 1
R2 ←R2 −2R1 R2 ↔R3
A −− −−−−−→ 0 0 0 −− −−→ 0 1 1. Rank = 2 (2 pivots). Nullity = 3 − 2 = 1.
0 1 1 0 0 0
—    
1 2 3
Q2. System Consistency Is Ax = b consistent for A = and b = ? Solution Q2:
   2 4 5

1 2 | 3 R2 ←R2 −2R1 1 2 | 3
Augmented matrix: −−−−−−−→ . The last row 0 = −1 is a
2 4 | 5 0 0 | −1
contradiction. The system is inconsistent.
—  
1 2
Q3. Invertibility Determine if B = is invertible. Solution Q3: Invertible if det(B) 6= 0.
3 4
det(B) = (1)(4) − (2)(3) = 4 − 6 = −2. Since det(B) 6= 0, B is invertible.
—

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 89 / 135
Student Exercises (1-9): Rank, Systems, and Subspaces II
 
1 0 1
Q4. Basis for Column Space Find a basis for Col(C) where C = 2 1 3. Solution Q4:
  3 1 4
1 0 1
RREF
C −−−→ 0 1 1. Pivots are in columns 1 and 2. Basis for Col(C) are the pivot columns of C:
  0 0 0
 1 0 
2 , 1 .
3 1
 
—    
1 0
Q5. Linear Independence Are v1 = and v2 = linearly independent? Solution Q5: Yes.
  0 1
1 0
The determinant of the matrix is 1, which is non-zero. They are linearly independent.
0 1
—

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 90 / 135
Student Exercises (1-9): Rank, Systems, and Subspaces III
 
a
Q6. Subspace Check Is the set of all vectors in R2 of the form a subspace of R2 ? Solution Q6:
  0      
0 a b a+b
Yes. 1. Zero vector is included (a = 0). 2. Closed under addition: + = . 3.
0     0 0 0
a ca
Closed under scalar multiplication: c = . It is a subspace.
0 0
—  
2 1
Q7. Determinant Calculation Calculate det . Solution Q7:
4 3
det = (2)(3) − (1)(4) = 6 − 4 = 2.
—   
1 2 4 0
Q8. Matrix Multiplication Compute . Solution Q8:
  0 3  1 1
(1)(4) + (2)(1) (1)(0) + (2)(1) 6 2
= .
(0)(4) + (3)(1) (0)(0) + (3)(1) 3 3
—

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 91 / 135
Student Exercises (1-9): Rank, Systems, and Subspaces IV



1 2
Q9. Transpose Property If A = , find det(A> ). Solution Q9: det(A> ) = det(A).
3 4
det(A) = 1(4) − 2(3) = −2. det(A> ) = −2.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 92 / 135
Student Exercises (10-18): Eigenvalues and Diagonalization I

 
2 0
Q10. Characteristic Polynomial Find the characteristic polynomial p(λ) for A = . Solution
0 5
 
2−λ 0
Q10: p(λ) = det(A − λI) = det = (2 − λ)(5 − λ) = λ2 − 7λ + 10.
0 5−λ
—  
4 7
Q11. Eigenvalues (Triangular Matrix) Find the eigenvalues of B = . Solution Q11: For a
0 3
triangular matrix, eigenvalues are the diagonal entries. λ1 = 4, λ2 = 3.
—    
1 3 1
Q12. Eigenvector Check Is x = an eigenvector of C = ? If so, what is the eigenvalue?
  1     1 3
3 1 1 4 1
Solution Q12: Cx = = =4 . Yes, x is an eigenvector with eigenvalue λ = 4.
1 3 1 4 1
—

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 93 / 135
Student Exercises (10-18): Eigenvalues and Diagonalization II
 
5 0
Q13. Eigenspace Basis Given λ = 5 is an eigenvalue of D = , find a basis for the eigenspace
0 5
 
0 0
E5 . Solution Q13: (D − 5I)x = 0 =⇒ x = 0. Both x1 and x2 are free.
0 0
       
1 0 1 0
x = x1 + x2 . Basis for E5 : , .
0 1 0 1
—  
1 1
Q14. Diagonalizability Check Is E = diagonalizable? Solution Q14: Eigenvalues are λ1 = 1
  0 1
0 1
(AM=2). Eigenspace E1 : x = 0 =⇒ x2 = 0. x1 is free. GM(λ1 )=1. Since GM(λ) < AM(λ),
0 0
E is not diagonalizable.
—
Q15. Trace and Eigenvalues If F has eigenvalues λ1 = 1, λ2 = 3, λ3 = 5, what is tr(F)? Solution
Q15: The Trace is the sum of the eigenvalues. tr(F) = 1 + 3 + 5 = 9.
—

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 94 / 135
Student Exercises (10-18): Eigenvalues and Diagonalization III

Q16. Determinant and Eigenvalues If G has eigenvalues λ1 = 2, λ2 = −1, what is det(G)? Solution
Q16: The Determinant is the product of the eigenvalues. det(G) = (2)(−1) = −2.
—
Q17. Similarity Transformation If H is similar to K, what is the relationship between their
characteristic polynomials? Solution Q17: Similar matrices share the same characteristic polynomial
and therefore the same eigenvalues.
—
Q18. Power of a Diagonalizable Matrix If A = PDP−1 , compute A3 . Solution Q18:
A3 = (PDP−1 )(PDP−1 )(PDP−1 ) = PD(P−1 P)D(P−1 P)DP−1 = PD3 P−1 .

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 95 / 135
Student Exercises (19-25): Orthonormal Bases, SVD, and Forms I

   
1 1
Q19. Gram-Schmidt (Orthogonal Step) For a1 = and a2 = , find the orthogonal vector
0 1
 
1 a2 ·v1 2
v2 . Solution Q19: v1 = a1 = . v2 = a2 − ||v 1 ||
2 v1 . a2 · v1 = 1. ||v1 || = 1.
      0
1 1 1 0
v2 = −1 = .
1 0 1
—  
cos θ − sin θ
Q20. Orthogonal Matrix If Q = , compute Q> Q. Solution Q20:
sin θ cos θ
cos2 θ + sin2 θ
    
> cos θ sin θ cos θ − sin θ − cos θ sin θ + sin θ cos θ
Q Q= = =
 
− sin θ cos θ sin θ cos θ − sin θ cos θ + cos θ sin θ sin2 θ + cos2 θ
1 0
= I.
0 1
—

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 96 / 135
Student Exercises (19-25): Orthonormal Bases, SVD, and Forms II
2 2
Q21. Quadratic Form Classification  the quadratic form Q(x1 , x2 ) = x1 + 4x2 . Solution
 Classify
1 0
Q21: The associated matrix is A = . Eigenvalues are λ1 = 1, λ2 = 4. Since both are strictly
0 4
positive, the form is Positive Definite.
—
Q22. Quadratic Form Matrix Write the symmetric matrix A for Q(x1 , x2 ) = 2x12 + 6x1 x2 + 5x22 .
Solution Q22:Diagonal  entries are 2 and 5. Off-diagonal entries are half of the cross-term coefficient
2 3
(6/2=3). A = .
3 5
—
Q23. SVD: Singular Value Source The singular values of A are σi . What are the eigenvalues of
A> A? Solution Q23: The eigenvalues of A> A are the squares of the singular values: λi = σi2 .
—
Q24. SVD and Rank If A has singular values {5, 3, 0.1, 0, 0}, what is the rank of A? Solution Q24:
The rank is the number of non − zero singular values. Rank = 3.
—

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 97 / 135
Student Exercises (19-25): Orthonormal Bases, SVD, and Forms
III

Q25. Cayley-Hamilton (Application) Given p(λ) = λ2 − 3λ + 2 for A, write the equation to solve for
A−1 . Solution Q25: p(A) = A2 − 3A + 2I = 0. 2I = −A2 + 3A = A(−A + 3I). Multiplying by A−1 :
A−1 (2I) = −A + 3I. A−1 = 12 (3I − A).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 98 / 135
Unsolved Practice Exercises (1-25) I
 
1 3
Q1. Compute the Null Space basis for A = .
  2 6
1 0
Q2. For A = , find A−1 .
0 2      
1 0 2
Q3. What is the dimension of the subspace spanned by v1 = 0 , v2 = 1 , v3 = 2?
0 0 0
>
Q4. If A is 3 × 5 with rank(A) = 3, what is the dimensionof the Left
 Null Space (Null(A ))?
0 1 0
Q5. Calculate the determinant of the permutation matrix 0 0 1.
    1 0 0
1 0
Q6. Find the least − squares solution to 1 x = 1.
1 2
 
1 3
Q7. Find the eigenvalues of B = .
0 4

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 99 / 135
Unsolved Practice Exercises (1-25) II

0 1
Q8. For C = , find the eigenvector corresponding to λ = 4.
0
4  
5 0 0
Q9. Is the matrix D = 0 5 1 diagonalizable?
0 0 5 
−1 2 0
Q10. If A = PDP with D = , compute A2 .
0 −1
Q11. The matrix E has tr(E) = 5 and det(E) = 6.  Find
 its eigenvalues.
 
1 0
Q12. Apply the Gram − Schmidt process to a1 = and a2 = to find q2 .
0 2
Q13. Write the symmetric matrix A for Q(x1 , x2 ) = 7x12 − 10x1 x2 + x22 .
2 2
Q14.  form Q(x1 , x2 ) = −x1 − 2x2 .
Classify thequadratic
1 0
Q15. Given A = , find the Singular Values.
0 0
Q16. If A is a 4 × 4 matrix and rank(A) = 3, how many zero  singular
 values does A have?
3 −4
Q17. What is the inverse of the orthogonal matrix P = 51 ?
4 3
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 100 / 135
Unsolved Practice Exercises (1-25) III
Q18. If A is invertible, what is the relationship between the eigenvalues of A and A−1 ?
Q19. Use the Cayley-Hamilton theorem to simplify A3 if the characteristic polynomial is
p(λ) = λ2 − 2λ + 1.  
1 1 1
Q20. Find the Nullity of F = 1 1 1.
1 1 1
 
1 2
Q21. Find a non-zero vector x in the column space of G = .
 1 2
1 0
Q22. State the dimension of the Row Space of H = 0 1.
0 0
Q23. If A is a 2 × 2 matrix with det(A) = 5 and det(B) = 2, compute det(2AB> ).
Q24. Given the SVD A = UΣV> , what is the dimension of the Null Space of A if Σ has 2 non-zero
singular values, U is 3 × 3, and V is 3 × 3?    
1 1
Q25. Find the orthogonal projection of b = onto the line spanned by a = .
0 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 101 / 135
Cholesky Decomposition: Statement and Existence I

Statement: Let A ∈ Rn×n be symmetric (A = A> ). Then A has a unique factorization

A = LL>

with L lower-triangular with positive diagonal entries if and only if A is positive definite (i.e. x > Ax > 0
for all x 6= 0).

Goal: Prove equivalence and give explicit recursive formulas (Cholesky–Banachiewicz).

Proof:
⇒ Suppose A = LL> with L lower triangular and diag(L) > 0. For any x 6= 0,

x > Ax = x > LL> x = (L> x)> (L> x) = kL> xk2 > 0,

since L invertible (positive diagonal =⇒ det(L) 6= 0) and L> x 6= 0. Hence A is positive

definite.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 102 / 135
Cholesky Decomposition: Statement and Existence II

⇐ Suppose A is symmetric positive definite. Construct L by induction.

Let A = [aij ]. We compute column by column.
For j = 1:
√
l11 = a11 > 0 (since a11 = e1> Ae1 > 0).
For i > 1,
ai1
li1 = .
l11
Assume columns 1, . . . , j − 1 of L are determined. For column j compute
v
u
u j−1
X
ljj = ajj −
t ljk2 .
k=1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 103 / 135
Cholesky Decomposition: Statement and Existence III

We must show the radicand is positive. That radicand equals the Schur complement of
the (j − 1) × (j − 1) leading principal submatrix of A, which is positive because leading
principal minors of an SPD matrix are positive. Thus ljj > 0. Then for i > j,

j−1
1 X 
lij = aij − lik ljk .
ljj
k=1

Proceeding by induction builds L with positive diagonals and A = LL> .

Uniqueness: If A = LL> = L̃L̃> with both lower-triangular and positive diagonal, then L−1 L̃ is
lower-triangular and orthogonal ⇒ must be I (only lower-triangular orthogonal matrix with positive
diagonal is I ). Hence L = L̃.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 104 / 135
Cholesky–Banachiewicz Algorithm and Worked Example I

Algorithm (column-oriented): For j = 1, . . . , n

v
u
u Xj−1
ljj = tajj − ljk2 ,
k=1
j−1
1 X 
lij = aij − lik ljk , i = j + 1, . . . , n.
ljj
k=1

Worked Example: Factor  

4 12 −16
A =  12 37 −43 .
−16 −43 98
Step-by-step: √
l11 = 4 = 2.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 105 / 135
Cholesky–Banachiewicz Algorithm and Worked Example II

12 −16
l21 = = 6, l31 = = −8.
2 2
p √
l22 = 37 − 62 = 1 = 1.
−43 − (−8)(6) −43 + 48
l32 = = = 5.
1 1
p √ √
l33 = 98 − (−8)2 − 52 = 98 − 64 − 25 = 9 = 3.
So  
2 0 0
L= 6 1 0 , LL> = A.
−8 5 3

Complexity Note: Cholesky requires about n3 /3 flops (roughly half of generic LU).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 106 / 135
Skew-Symmetric Matrices: Definitions and Properties I

Definition: A ∈ Rn×n is skew-symmetric if

A> = −A.

Thus diagonal entries satisfy aii = −aii ⇒ aii = 0.

Property 1 Diagonals zero: trivial from definition.

Property 2 Determinant for odd n:

det(A) = det(A> ) = det(−A) = (−1)n det(A).

If n odd then (−1)n = −1, so det(A) = − det(A) ⇒ det(A) = 0.

Property 3 Eigenvalues: For real skew-symmetric A, nonzero eigenvalues are purely imaginary and
come in conjugate pairs.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 107 / 135
Skew-Symmetric Matrices: Definitions and Properties II
Proof: Let Ax = λx with x 6= 0 (allow complex λ, x). Then

x ∗ Ax = λx ∗ x,

where x ∗ is conjugate transpose. But

x ∗ Ax = (x ∗ Ax)∗ = x ∗ A∗ x = x ∗ (−A)x = −x ∗ Ax,

so x ∗ Ax = −x ∗ Ax ⇒ x ∗ Ax = 0. Then λx ∗ x = 0 so either λ = 0 or x ∗ x = 0 (impossible). To refine:

more carefully, with complex eigenpair Ax = λx, take conjugate transpose:

x ∗ Ax = λx ∗ x,

and
(x ∗ Ax)∗ = x ∗ A∗ x = x ∗ (−A)x = −x ∗ Ax.
Hence x ∗ Ax is purely imaginary (equal to negative of its conjugate). Since x ∗ x > 0, λ must be purely
imaginary. Real entries guarantee conjugate pairs.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 108 / 135
Skew-Symmetric Matrices: Definitions and Properties III

Property 4 Exponential is orthogonal: If A> = −A, then

>
(e A )> e A = e A e A = e −A e A = I ,

so e A is orthogonal.

Example: Rotation generator in R2

   
0 −ω tA cos(tω) − sin(tω)
A= , e = .
ω 0 sin(tω) cos(tω)

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 109 / 135
Matrices as Linear Maps Examples in R2 I

A matrix A ∈ R2×2 represents a linear map x 7→ Ax. We analyze via action on unit circle, eigenvectors,
SVD.

Examples:
 
cos θ − sin θ
Rotation: R(θ) = . Preserves inner products and lengths.
sin θ cos θ
 
α 0
Scaling: D(α, β) = . Scales axes; eigenvectors are coordinate axes.
0 β
 
1 k
Shear: H(k) = . Preserves area (det=1) but not lengths/angles.
0 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 110 / 135
Matrices as Linear Maps Examples in R2 II

Unit circle → ellipse via SVD: If A = UΣV > , then for x on unit circle x = Vy with ky k = 1, we have

Ax = UΣy ,

so the image is the ellipse {Σy : ky k = 1} whose semi-axes lengths are singular values σi and axes
directions are columns of U.

Interpretation of eigenvectors vs singular vectors:

Eigenvectors: directions scaled by A (may change angle).
Singular vectors: directions of maximal/minimal stretching of the unit sphere (orthonormal).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 111 / 135
SVD and MoorePenrose Pseudoinverse I
SVD Recap: For any m × n matrix A, there exist orthogonal U ∈ Rm×m and V ∈ Rn×n and diagonal
Σ ∈ Rm×n with nonnegative entries (singular values) such that

A = UΣV > .

MoorePenrose pseudoinverse: Define Σ† by replacing each nonzero σi by 1/σi and transposing the
matrix shape. Then
A† = V Σ† U > .

Penrose conditions (unique characterization): A† is the unique matrix satisfying

AA† A = A,
A† AA† = A† ,
(AA† )> = AA† ,
(A† A)> = A† A.
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 112 / 135
SVD and MoorePenrose Pseudoinverse II

Least squares solution: For overdetermined Ax ≈ b, the minimum-norm least-squares solution is

xLS = A† b.

Proof sketch: With SVD A = UΣV > and let y = V > x, c = U > b. Minimizing
kAx − bk2 = kΣy − ck2 decouples per singular component; set yi = ci /σi for σi 6= 0 and yi = 0 when
σi = 0 to obtain minimal norm solution. Then x = Vy = A† b.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 113 / 135
Worked Example: Pseudoinverse and Least Squares I

Problem: Find least-squares solution for the system

   
1 0
1 x ≈ 1 .
1 2
 
1
Here A = 1 is 3 × 1.
1
√
Compute SVD: A> A = (1 1 1)(1 1 1)> = 3. So single singular value σ1 = 3.
 
1
1  
U = I3 projected to √ 1 , V = 1.
3 1

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 114 / 135
Worked Example: Pseudoinverse and Least Squares II
Concretely,
√  
√1

3 ···
 √13 · · ·
Σ =  0 , U=  3 ,
0 √1 ···
3

but easier: pseudoinverse formula for rank-1 column A is

1 1
A† = 2
A> = (1 1 1).
kAk 3

Thus  
0
1 1+2
xLS = A† b = (1 1 1) 1 = = 1.
3 3
2
Check residual: AxLS = (1, 1, 1)> · 1 = (1, 1, 1)> and √
residual
kAxLS − bk = k(1, 1, 1) − (0, 1, 2)k = k(1, 0, −1)k = 2 minimal among all x.
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 115 / 135
Condition Number, Sensitivity, and Practical Advice I
Definition (2-norm) For invertible A,
σmax (A)
κ2 (A) = kAk2 kA−1 k2 = .
σmin (A)

Interpretation: If Ax = b and b perturbs to b + δb, the solution x perturbs to x + δx with (first-order

bound)
kδxk kδbk
≤ κ2 (A) + O(kδbk2 ).
kxk kbk
Thus larger κ means more sensitivity (ill-conditioned).

Why avoid normal equations for least squares: Normal equations solve (A> A)x = A> b. Condition
number squares:
κ2 (A> A) = κ2 (A)2 .
Thus forming A> A worsens conditioning prefer QR or SVD-based solvers.

Practical recommendations:
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 116 / 135
Condition Number, Sensitivity, and Practical Advice II

Use Cholesky for SPD problems (fast, stable if SPD).

Use LU with partial pivoting (PLU) for general linear systems.
For least squares, prefer QR (Householder) or SVD for rank-deficient cases.
Scale columns to reduce condition issues when appropriate.

Example (Vandermonde ill-conditioning): Vandermonde matrices (powers of points) become

severely ill-conditioned as degree grows; QR or SVD recommended.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 117 / 135
Orthogonal Matrices: Definition and Equivalent Characterizations I

Definition: A real square matrix Q ∈ Rn×n is orthogonal if

Q > Q = In (equivalently, QQ > = In ).

Hence Q −1 = Q > .

Equivalent characterizations:
Columns of Q form an orthonormal basis of Rn .
Rows of Q form an orthonormal basis of Rn .
kQxk2 = kxk2 for all x ∈ Rn (norm-preserving).
(Qx, Qy ) = (x, y ) for all x, y preserves inner products and angles.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 118 / 135
Orthogonal Matrices: Definition and Equivalent Characterizations II

Proof of equivalence:
(Q > Q = I ) ⇐⇒ columns are orthonormal.
If columns {qi } satisfy qi> qj = δij , then for any x,

kQxk2 = (Qx)> (Qx) = x > (Q > Q)x = x > x = kxk2 .

Conversely, if kQxk = kxk for all x, then (Q > Q − I ) is zero because x > (Q > Q − I )x = 0 for all x.
Hence Q > Q = I .

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 119 / 135
Fundamental Properties and Proofs I

1. Inverse equals transpose:

Q > Q = I ⇒ Q −1 = Q > .
Thus orthogonal matrices are always invertible and det(Q) 6= 0.

2. Determinant: Taking determinant both sides:

det(Q > Q) = det(I ) =⇒ (det Q)2 = 1 =⇒ det Q = ±1.

Hence orthogonal matrices are of two types:

det Q = +1: Proper orthogonal corresponds to rotation.
det Q = −1: Improper orthogonal corresponds to reflection.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 120 / 135
Fundamental Properties and Proofs II

3. Preservation of lengths and angles: For any x, y ,

(Qx)> (Qy ) = x > Q > Qy = x > y .

Hence kQxk = kxk and cos ∠(Qx, Qy ) = cos ∠(x, y ).

4. Eigenvalues: If Q is orthogonal, Q > = Q −1 , so for eigenpair Qx = λx,

kxk = kQxk = |λ|kxk ⇒ |λ| = 1.

Thus eigenvalues lie on the unit circle in C (e.g., λ = e iθ ).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 121 / 135
Geometric Interpretation and Examples I
Geometric interpretation: Orthogonal matrices represent rigid motions rotations and reflections that
preserve:
Euclidean length,
Inner product (angles),
Orientation (if det Q = +1).

Example 1 Rotation in R2 :  
cos θ − sin θ
R(θ) = .
sin θ cos θ
Check: R(θ)> R(θ) = I , det R(θ) = +1. Action: Rotates every vector by θ counterclockwise.

Example 2 Reflection in R2 :  
1 0
M= .
0 −1
Then M > M = I , det M = −1, reflection across the x-axis.
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 122 / 135
Geometric Interpretation and Examples II

Example 3 3D Rotation: A rotation about unit axis û = (ux , uy , uz ) by angle θ:

Q = I + (sin θ)[û]× + (1 − cos θ)[û]2× ,

where [û]× is the skew-symmetric cross-product matrix. This form links orthogonal matrices to
skew-symmetric generators (via matrix exponentials Q = e [û]× θ ).

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 123 / 135
Orthogonal Matrices in Computation (QR and Stability) I

Orthogonal matrices in numerical algorithms:

In QR factorization, A = QR, with Q orthogonal and R upper-triangular.
Multiplication by Q does not magnify errors since kQxk = kxk.
Hence algorithms built on orthogonal transformations (e.g. Householder, Givens rotations) are
numerically stable.

Householder transformation:
vv >
Q =I −2 , v 6= 0.
v >v
Proof of orthogonality:

vv > 2 vv > vv > vv > vv > v > v vv >

Q > Q = (I − 2 ) = I − 4 + 4 = I − 4 + 4 = I.
v >v v >v (v > v )2 v >v (v > v )2

Geometric meaning: Reflection across hyperplane orthogonal to v .

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 124 / 135
Orthogonal Matrices in Computation (QR and Stability) II

Example (QR via Householder): To zero out subdiagonal entries of A, apply successive Qi :

R = Qk · · · Q2 Q1 A, Q = Q1> Q2> · · · Qk> .

Each Qi is orthogonal ⇒ kQk2 = 1 and no amplification of round-off error.

Summary: Orthogonal matrices ⇒ preserve geometry and stability crucial in modern numerical linear
algebra.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 125 / 135
Overview: Eigenvalues and Special Matrices

Recall: For a square matrix A ∈ Cn×n , an eigenpair (λ, x) satisfies

Ax = λx, x 6= 0.

Different matrix structures impose distinct constraints on eigenvalues and eigenvectors.

Main categories:
1 Symmetric (real) matrices
2 Skew-symmetric matrices
3 Orthogonal matrices
4 Hermitian and skew-Hermitian matrices
5 Unitary matrices
6 Positive definite matrices

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 126 / 135
Symmetric Matrices (A = AT )
Theorem (Spectral Theorem for Real Symmetric Matrices): If A = AT , then:
1 All eigenvalues of A are real.
2 Eigenvectors corresponding to distinct eigenvalues are orthogonal.
3 A can be diagonalized by an orthogonal matrix:
A = QΛQ T , QT Q = I .
Proof (Eigenvalues are real): Let A = AT and Ax = λx. Then
x T Ax = x T (λx) = λ(x T x),
and also
x T Ax = (Ax)T x = (λx)T x = λ(x T x).
Thus λ = λ̄, so λ ∈ R.
Example:  
2 1
A= , |A − λI | = (2 − λ)2 − 1 = 0
1 2
⇒ λ1 = 3, λ2 = 1, x1 = (1, 1)T , x2 = (1, −1)T .
The normalized eigenvectors form an orthonormal basis.
Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 127 / 135
Skew-Symmetric Matrices (AT = −A)

Theorem: If AT = −A, then

1 All non-zero eigenvalues are purely imaginary.
2 Eigenvalues occur in conjugate pairs ±iµ, with µ ∈ R.
Proof: Let Ax = λx, with x T x = 1. Then

x T Ax = λ, (x T Ax)T = x T AT x = −x T Ax = −λ.

Thus λ = −λ̄, so λ is purely imaginary.

Example:  
0 −2
A= ⇒ |A − λI | = λ2 + 4 = 0 ⇒ λ = ±2i.
2 0
Geometrically, such matrices represent infinitesimal rotations.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 128 / 135
Orthogonal Matrices (Q T Q = I )

Theorem: If Q is real orthogonal, then all eigenvalues satisfy |λ| = 1.

Proof: Let Qx = λx. Then

kxk2 = kQxk2 = (Qx)T (Qx) = x T (Q T Q)x = x T x.

Hence |λ|2 = 1 ⇒ |λ| = 1.

Example:  
0 −1
Q= ⇒ λ = ±i.
1 0
Interpretation: Orthogonal matrices represent rotations or reflections in Rn .

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 129 / 135
Hermitian Matrices (A∗ = A)
Theorem (Spectral Theorem): If A = A∗ , then:
1 All eigenvalues are real.
2 Eigenvectors corresponding to distinct eigenvalues are orthogonal.
3 A is unitarily diagonalizable:
A = UΛU ∗ , U ∗U = I .
Proof: Let Ax = λx. Then
x ∗ Ax = x ∗ (λx) = λx ∗ x,
and since A∗ = A,
(x ∗ Ax)∗ = x ∗ A∗ x = x ∗ Ax = λ̄x ∗ x.
Thus λ = λ̄, implying λ ∈ R.
Example:  
2 i
A= ⇒ |A − λI | = (2 − λ)2 − 1 = 0 ⇒ λ = 1, 3.
−i 2

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 130 / 135
Skew-Hermitian Matrices (A∗ = −A)

Theorem: If A∗ = −A, then all eigenvalues are purely imaginary.

Proof: Let Ax = λx. Then

x ∗ Ax = λx ∗ x, (x ∗ Ax)∗ = x ∗ A∗ x = −x ∗ Ax = −λx ∗ x.

Hence λ = −λ̄, so λ is purely imaginary.

Example:  
0 −i
A= ⇒ λ = ±i.
i 0

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 131 / 135
Unitary Matrices (U ∗ U = I )

Theorem: If U is unitary, then all eigenvalues satisfy |λ| = 1.

Proof: Let Ux = λx. Then

kUxk2 = (Ux)∗ (Ux) = x ∗ (U ∗ U)x = x ∗ x,

which gives |λ|2 = 1.

Example:  
0 1
U= ⇒ λ = ±i.
−1 0
Interpretation: Unitary matrices represent complex rotations that preserve length and angle.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 132 / 135
Positive (Semi)Definite Matrices

Definition: A Hermitian matrix A is

Positive definite (PD) if x ∗ Ax > 0 for all x 6= 0.
Positive semidefinite (PSD) if x ∗ Ax ≥ 0 for all x.
Theorem: All eigenvalues of a PD (PSD) matrix are positive (non-negative).
Proof: Let Ax = λx, with x ∗ x = 1. Then λ = x ∗ Ax. If A is PD, x ∗ Ax > 0 ⇒ λ > 0.
Example:  
2 1
A= , λ = 3, 1 > 0 ⇒ A is PD.
1 2

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 133 / 135
Summary: Eigenvalue Characteristics of Special Matrices

Matrix Type Condition Eigenvalue Properties

Symmetric (real) AT = A Real eigenvalues, orthogonal eigenvectors
T
Skew-symmetric A = −A Purely imaginary, conjugate pairs
T
Orthogonal Q Q=I |λ| = 1
∗
Hermitian A =A Real eigenvalues
∗
Skew-Hermitian A = −A Purely imaginary eigenvalues
∗
Unitary U U=I |λ| = 1
∗
Positive definite x Ax > 0 λi > 0
∗
Positive semidefinite x Ax ≥ 0 λi ≥ 0

Observation: All these classes are subsets of normal matrices (A∗ A = AA∗ ), which are exactly those
that are unitarily diagonalizable.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 134 / 135
References and Further Reading

Gene H. Golub and Charles F. Van Loan, Matrix Computations chapters on Cholesky, SVD, and
stability.
Gilbert Strang, Linear Algebra and Its Applications geometric perspective and applications.
Erwin Kreyszig, Advanced Engineering Mathematics introductory chapters for engineering
students.
Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra numerical stability, condition
numbers.

Pravin Chandra (USICT, GGSIPU) UNIT III: Linear Algebra (Foundations and Applications) November 3, 2025 135 / 135