System of Linear Equations
A Comprehensive Mathematical Treatment
Contents
1 Introduction and Motivation 3
2 Basic Definitions and Notation 3
2.1 Linear Equation in n Unknowns . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 System of Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Matrix Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Solution and Solution Set . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Geometric Interpretation 5
3.1 Two Equations in Two Unknowns . . . . . . . . . . . . . . . . . . . . . . 5
3.2 General Case: Three Equations, Three Unknowns . . . . . . . . . . . . . 5
4 Classification of Systems 6
5 Elementary Row Operations 6
6 Row-Echelon Forms 7
6.1 Row-Echelon Form (REF) . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2 Reduced Row-Echelon Form (RREF) . . . . . . . . . . . . . . . . . . . . 8
6.3 Pivot Columns and Free Variables . . . . . . . . . . . . . . . . . . . . . . 8
7 Gaussian Elimination 9
7.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Worked Example — 3 × 3 System . . . . . . . . . . . . . . . . . . . . . . 10
,Comprehensive Notes System of Linear Equations
8 Rank of a Matrix 11
9 Existence and Uniqueness: The Fundamental Theorem 11
9.1 The Rouché–Capelli Theorem . . . . . . . . . . . . . . . . . . . . . . . . 11
9.2 The Square System: m = n . . . . . . . . . . . . . . . . . . . . . . . . . 12
10 Structure of the Solution Set 12
10.1 Homogeneous Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
10.2 General Solution of Non-Homogeneous System . . . . . . . . . . . . . . . 13
10.3 Expressing the General Solution via Free Variables . . . . . . . . . . . . 14
11 Special Cases and Important Theorems 14
11.1 Overdetermined Systems (m > n) . . . . . . . . . . . . . . . . . . . . . . 14
11.2 Underdetermined Systems (m < n) . . . . . . . . . . . . . . . . . . . . . 14
11.3 Homogeneous Systems — Key Theorem . . . . . . . . . . . . . . . . . . 15
12 Cramer’s Rule 15
13 LU Decomposition 16
14 Comprehensive Worked Examples 16
14.1 Unique Solution (m = n = 3) . . . . . . . . . . . . . . . . . . . . . . . . 16
14.2 Infinitely Many Solutions (Underdetermined) . . . . . . . . . . . . . . . . 17
14.3 Inconsistent System (No Solution) . . . . . . . . . . . . . . . . . . . . . . 19
15 Homogeneous Systems and the Null Space 19
15.1 Finding a Basis for the Null Space . . . . . . . . . . . . . . . . . . . . . . 19
16 Applications of Linear Systems 20
16.1 Network Flow Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
16.2 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
16.3 Least-Squares Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
17 Summary of Key Results 22
Appendix A: Determinants 23
Appendix B: Matrix Inverse 23
2
, Comprehensive Notes System of Linear Equations
1. Introduction and Motivation
A system of linear equations is one of the most fundamental structures in mathemat-
ics. It appears in virtually every branch of applied mathematics, physics, engineering,
economics and computer science. The theory underlying the solution of such systems
forms the backbone of linear algebra.
In its most abstract form, we seek vectors x in Rn (or more generally in any field F)
that simultaneously satisfy a collection of linear constraints. The power of the theory lies
in the fact that whether such solutions exist, and how many there are, can be determined
entirely from a few computable invariants of the coefficient matrix — principally its rank.
This document develops the theory from first principles: from the basic definition and
geometric interpretation, through the algorithmic machinery of Gaussian elimination and
row-echelon forms, to the fundamental existence and uniqueness theorems, the complete
solution structure, and finally to practical computational examples.
2. Basic Definitions and Notation
2.1. Linear Equation in n Unknowns
Definition
A linear equation in the n unknowns x1 , x2 , . . . , xn is an equation of the form
a1 x1 + a2 x2 + · · · + an xn = b,
where a1 , a2 , . . . , an ∈ R are called the coefficients and b ∈ R is called the constant
term (or right-hand side).
The equation is linear because each unknown appears to the first power and there are
no products of unknowns. The following are linear equations:
1 √
3x1 − 2x2 + 5x3 = 7, x − y = 0, x1 + 3 x2 − x3 + x4 = −1.
2
The following are not linear:
x21 + x2 = 3, x1 x2 = 4, sin(x1 ) + x2 = 0.
2.2. System of Linear Equations
3
A Comprehensive Mathematical Treatment
Contents
1 Introduction and Motivation 3
2 Basic Definitions and Notation 3
2.1 Linear Equation in n Unknowns . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 System of Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Matrix Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Solution and Solution Set . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Geometric Interpretation 5
3.1 Two Equations in Two Unknowns . . . . . . . . . . . . . . . . . . . . . . 5
3.2 General Case: Three Equations, Three Unknowns . . . . . . . . . . . . . 5
4 Classification of Systems 6
5 Elementary Row Operations 6
6 Row-Echelon Forms 7
6.1 Row-Echelon Form (REF) . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2 Reduced Row-Echelon Form (RREF) . . . . . . . . . . . . . . . . . . . . 8
6.3 Pivot Columns and Free Variables . . . . . . . . . . . . . . . . . . . . . . 8
7 Gaussian Elimination 9
7.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Worked Example — 3 × 3 System . . . . . . . . . . . . . . . . . . . . . . 10
,Comprehensive Notes System of Linear Equations
8 Rank of a Matrix 11
9 Existence and Uniqueness: The Fundamental Theorem 11
9.1 The Rouché–Capelli Theorem . . . . . . . . . . . . . . . . . . . . . . . . 11
9.2 The Square System: m = n . . . . . . . . . . . . . . . . . . . . . . . . . 12
10 Structure of the Solution Set 12
10.1 Homogeneous Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
10.2 General Solution of Non-Homogeneous System . . . . . . . . . . . . . . . 13
10.3 Expressing the General Solution via Free Variables . . . . . . . . . . . . 14
11 Special Cases and Important Theorems 14
11.1 Overdetermined Systems (m > n) . . . . . . . . . . . . . . . . . . . . . . 14
11.2 Underdetermined Systems (m < n) . . . . . . . . . . . . . . . . . . . . . 14
11.3 Homogeneous Systems — Key Theorem . . . . . . . . . . . . . . . . . . 15
12 Cramer’s Rule 15
13 LU Decomposition 16
14 Comprehensive Worked Examples 16
14.1 Unique Solution (m = n = 3) . . . . . . . . . . . . . . . . . . . . . . . . 16
14.2 Infinitely Many Solutions (Underdetermined) . . . . . . . . . . . . . . . . 17
14.3 Inconsistent System (No Solution) . . . . . . . . . . . . . . . . . . . . . . 19
15 Homogeneous Systems and the Null Space 19
15.1 Finding a Basis for the Null Space . . . . . . . . . . . . . . . . . . . . . . 19
16 Applications of Linear Systems 20
16.1 Network Flow Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
16.2 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
16.3 Least-Squares Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
17 Summary of Key Results 22
Appendix A: Determinants 23
Appendix B: Matrix Inverse 23
2
, Comprehensive Notes System of Linear Equations
1. Introduction and Motivation
A system of linear equations is one of the most fundamental structures in mathemat-
ics. It appears in virtually every branch of applied mathematics, physics, engineering,
economics and computer science. The theory underlying the solution of such systems
forms the backbone of linear algebra.
In its most abstract form, we seek vectors x in Rn (or more generally in any field F)
that simultaneously satisfy a collection of linear constraints. The power of the theory lies
in the fact that whether such solutions exist, and how many there are, can be determined
entirely from a few computable invariants of the coefficient matrix — principally its rank.
This document develops the theory from first principles: from the basic definition and
geometric interpretation, through the algorithmic machinery of Gaussian elimination and
row-echelon forms, to the fundamental existence and uniqueness theorems, the complete
solution structure, and finally to practical computational examples.
2. Basic Definitions and Notation
2.1. Linear Equation in n Unknowns
Definition
A linear equation in the n unknowns x1 , x2 , . . . , xn is an equation of the form
a1 x1 + a2 x2 + · · · + an xn = b,
where a1 , a2 , . . . , an ∈ R are called the coefficients and b ∈ R is called the constant
term (or right-hand side).
The equation is linear because each unknown appears to the first power and there are
no products of unknowns. The following are linear equations:
1 √
3x1 − 2x2 + 5x3 = 7, x − y = 0, x1 + 3 x2 − x3 + x4 = −1.
2
The following are not linear:
x21 + x2 = 3, x1 x2 = 4, sin(x1 ) + x2 = 0.
2.2. System of Linear Equations
3
