Mathematical Analysis and Linear Algebra – Section 3: Systems of linear equations.

Lecture
Section 3 Systems of linear equations.
3.1. Rank of a matrix.
3.2. General system of linear equations and its matrix form.
3.3. Cramer’s system.
3.4. General rules of linear equation systems. Kronecker-Capelli’s theorem.
3.5. Gauss and Gauss-Jordan methods of solving systems of linear equations.
Matrices are especially useful in the theory of equations. They can be used to solve systems of simultaneous
linear equations. Solving systems of equations is a frequently occurring problem in economic theory. For example,
equilibrium conditions can be formulated as equations, and if we want to look for equilibrium in several markets
simultaneously, we obtain a whole set (or system) of equations. Determinants of matrices are useful for determining
whether or not a unique solution exists. In this section, we study systems of equations and how to solve them with
matrices.

3.1. Rank of a matrix

Let be given a matrix 𝐴 ∈ 𝑀𝑚×𝑛 (ℝ).
The rank of a matrix is a natural number or zero uniquely associated with each matrix.
We will denote the rank of a matrix 𝐴: 𝑟𝑎𝑛𝑘(𝐴) or 𝑟(𝐴) or 𝑅(𝐴), 𝑟(𝐴) ∈ ℕ ∪ {0}.

Definition 3.1
1) If 𝐴 = 𝟎, then 𝑟(𝐴) = 0.
2) If 𝐴 ≠ 𝟎, then the rank 𝑟(𝐴) of the matrix 𝐴 is the order of the largest square submatrix of 𝐴 with nonzero
determinant.
Remarks
 The rank of a matrix 𝐴 is less or equal to its dimensions: 𝑟(𝐴) ≤ min{𝑚, 𝑛}.
 For a square matrix 𝐴 ∈ 𝑀𝑛 (ℝ) ∶
a) if 𝑑𝑒𝑡𝐴 ≠ 0 then 𝑟(𝐴) = 𝑛,
b) if 𝑑𝑒𝑡𝐴 = 0 then 𝑟(𝐴) < 𝑛.
 Elementary operations on rows or columns do not change the rank of a matrix.
 The rank of a matrix 𝐴 is the maximum number of linearly independent columns (rows) in the matrix
Example 3.1a) Find the rank of the given matrix:
1 3 1 2 3 1 2 3 1 2
𝐴=[ ] 𝐵=[ ] 𝐶=[ ] 𝐷=[ ]
2 4 2 4 0 4 1 0 4 1

Example 3.1b) Find the rank of the following matrix 𝐷 by using elementary rows or columns operations
- we may transform a determinant with the help of elementary transformations into a form such that it contains as
many zeros as possible (elementary transformations do not change the rank of matrix) or
- we may transform the given matrix into a stair-shape matrix/echelon form of the matrix (the rank of a matrix
equals the number of steps).
 Delete each row and column with all zero entries.
 If there is a row (column) with only one nonzero entry, delete this row (column) and column (row) with
the nonzero number and add one (1) to the rank.
3 0 −2 3 1 4
𝐷 = [ 2 22
−1 4
2
0
3
4 −1]
5 3
5 2 0 6 6 7
 Beata Ciałowicz ~ 22 ~
 Mathematical Analysis and Linear Algebra – Section 3: Systems of linear equations. Lecture
3.2. General system of linear equations and its matrix form

Definition 3.2 A general system of 𝒎 equations and 𝒏 variables can be written in a form:
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1
𝑎 𝑥 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2
(∗) { 21 1 where 𝑎𝑖𝑗 , 𝑏𝑗 ∈ ℝ (are given real numbers).
⋮
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = 𝑏𝑚

Elements 𝑎𝑖𝑗 (𝑖 = 1,2, … , 𝑛, 𝑗 = 1,2, … 𝑚) are called coefficients of the system.

Components 𝑏𝑗 (𝑗 = 1,2, … 𝑚) are called constants (or free coefficients).
Components 𝑥𝑖 (𝑖 = 1,2, … , 𝑛) are unknowns.
From this system we can create a few matrices:
𝑎11 𝑎12 … 𝑎1𝑛
𝑎21 𝑎22 … 𝑎2𝑛
 The matrix formed by the coefficients of the system is: 𝐴 = [ ⋮ ⋮ ⋱ ⋮ ]
𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑚×𝑛
a matrix of coefficients
𝑥1
𝑥2
 The matrix formed from the unknowns: 𝑋=[⋮] a matrix of unknowns
𝑥𝑛 𝑛×1
𝑏1
𝑏
 The matrix formed from the constant terms is: 𝐵 = [ 2 ] a matrix of constants
⋮
𝑏𝑚 𝑚×1
0
If the matrix of constants is the zero vector 𝐵 = 𝟎 = [0] , then the system of equations is called
⋮
0 𝑚×1
a homogeneous system, otherwise (𝐵 ≠ 𝟎) it is called an inhomogeneous system of equations.
 Using coefficients and constants, we can write a matrix called an augmented matrix (matrix of coefficients
is completed by a column of constants):
𝑎11 𝑎12 … 𝑎1𝑛 𝑏1
𝑎 21 𝑎 22 … 𝑎2𝑛 𝑏2
𝐴𝐵 = [𝐴|𝐵] = [ ]
⋮ ⋮ ⋱ ⋮ ⋮
𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑏𝑚 𝑚×(𝑛+1)

A system of equations (∗) can be expressed as the matrix equation (can be written in matrix notation):

(∗) ⟺ 𝐴 ∙ 𝑋 = 𝐵 matrix form of a system

𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1
𝑎21 𝑎22 … 𝑎2𝑛 𝑥2 𝑏2
[ ⋮ ⋮ ⋱ ⋮ ] ∙ [⋮] = [ ⋮ ]
𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑥𝑛 𝑏𝑚
↑ ↑ ↑
matrix of coefficients vector of unknowns constant matrix

 Beata Ciałowicz ~ 23 ~
 Mathematical Analysis and Linear Algebra – Section 3: Systems of linear equations. Lecture
Example 3.2. Find all matrices which characterized the given system of equations:
𝑥 − 2𝑦 + 3𝑧 + 𝑡 = 3
{ 3𝑥 − 𝑦 + 2𝑧 − 𝑡 = −2
−5𝑥 + 𝑦 + 𝑧 + 5𝑡 = 0

Solvability of a linear system of equations

A system of equations (∗) is called solvable or consistent if it has a solution, i.e. there exists at least one vector
(𝑥10 , 𝑥20 , … , 𝑥𝑛0 ) (a sequence of 𝑛 numbers) such that all 𝑚 equations in (∗) are satisfied.
Otherwise, it is called inconsistent (contradictory).
A solution (∗) need not exist, if a solution exists, it need not be unique.
The solvability of a system of linear equations will depend on the ranks of matrices 𝐴 and 𝐴𝐵 .
There are three possibilities:
1. system has no solution (inconsistent system - the system has contradictory equations).
2. system has an infinite number of solutions (indeterminate system).
3. system has an unique solution (determinate system).

3.3. Cramer’s system

Definition 3.3 Let 𝐴 = [𝑎𝑖𝑗 ]𝑛×𝑛 and 𝑑𝑒𝑡𝐴 ≠ 0.
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2
Then the system (∗∗) { is called a Cramer’s system.
⋮
𝑎𝑛1 𝑥1 + 𝑎𝑛2 𝑥2 + ⋯ + 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛

Remarks
 A Cramer’s system has always a unique solution.
 The determinant of a matrix of coefficients 𝐷 = 𝑑𝑒𝑡𝐴 is called the coefficient determinant (or main
determinant).

Theorem 3.1 (Cramer’s theorem) A Cramer system has a unique solution in the form: 𝑋 = 𝐴−1 ∙ 𝐵.

Example 3.3. Find the solution of the given system by using Cramer’s theorem (an inverse matrix)
2𝑥 + 𝑦 = 4
{ .
4𝑥 + 3𝑦 = 6

Theorem 3.2. (Cramer’s rule) The solution of a Cramer’s system is given by (𝑥1 , 𝑥2 , … , 𝑥𝑛 ),
𝑎11 𝑎12 … 𝑏1 … 𝑎1𝑛
𝐷𝑖 𝑎21 𝑎22 … 𝑏2 … 𝑎2𝑛
where: 𝑥𝑖 = , 𝐷𝑖 = det [ ]
𝐷 ⋮ ⋮ ⋱ ⋮ ⋱ ⋮
𝑎𝑛1 𝑎𝑛2 … 𝑏𝑛 … 𝑎𝑛𝑛
↑
𝑖th 𝑐𝑜𝑙𝑢𝑚𝑛
is the determinant obtained from 𝐷 by replacing the 𝑖th column by the column of constants 𝐵.
Example 3.4 Find the solution of the given system by using Cramer’s rule (determinants)
2𝑥 + 𝑦 = 4
{ where 𝐷 = det𝐴 = 2
4𝑥 + 3𝑦 = 6

 Beata Ciałowicz ~ 24 ~
 Mathematical Analysis and Linear Algebra – Section 3: Systems of linear equations. Lecture
3.4. General rules of linear equation systems
Theorem 3.3 (Kronecker – Cappelli) (necessary and sufficient condition)
A system of equations (∗) has at least one solution (is consistent) if and only if 𝑟(𝐴) = 𝑟(𝐴𝐵 ).

Remarks
 If 𝑟(𝐴) ≠ 𝑟(𝐴𝐵 ) the system has no solution (is inconsistent).
 If 𝑟 denotes the rank of equations, i.e. 𝑟 = 𝑟(𝐴) = 𝑟(𝐴𝐵 ), then:
a) for 𝑟 = 𝑛 the system has a unique solution,
b) for 𝑟 < 𝑛 the system has a infinitely many solutions.
 The homogeneous system of equations (𝐵 = 𝟎) always has at least one solution, the so-called trivial
solution: 𝑥1 = 𝑥2 = ⋯ = 𝑥𝑛 = 0.

The basic idea underlying the method of the solution described below is that certain transformations of a system
of linear equations do not affect the solution of the system, such that the solution of the transformed system is easy
to find. Generally, we want to change the system (∗) into the equivalent Cramer’s system.
We say that two systems of equations are equivalent if they have the same solution.

Algorithm for solving systems of linear equations 𝑨 ∙ 𝑿 = 𝑩:

Step 1. Find the ranks of matrices A and 𝐴𝐵 .
Step 2. If 𝑟(𝐴) ≠ 𝑟(𝐴𝐵 ) then end, the system is inconsistent (no solution).
If 𝑟(𝐴) = 𝑟(𝐴𝐵 ) then the system is consistent (has at least one solution).
Step 3. Compare ranks with the number of unknowns.
If 𝑟(𝐴) = 𝑟(𝐴𝐵 ) = 𝑟 = 𝑛 then the system has only one solution.
If 𝑟(𝐴) = 𝑟(𝐴𝐵 ) = 𝑟 < 𝑛 then the system has infinitely many solutions with 𝑛 − 𝑟 parameters.
Step 4. If 𝑟 = 𝑛 = 𝑚 then the system is Cramer’s system and can be solved using Cramer’s rule
(determinants) or Cramer’s theorem (inverse matrix 𝐴−1).
If 𝑟 = 𝑛 < 𝑚 or 𝑟 < 𝑛 ≤ 𝑚 then then the system is not Cramer’s system and you must modify this
system into equivalent Cramer’s system:
1) erase all the equations (if any) corresponding to the rows that have not be used for the minor 𝐴̃ which
gave the rank of the matrix 𝐴,
2) move all the terms of equations (only if 𝑟 < 𝑛) that contain unknowns in columns not used for the minor
𝐴̃ to the right side of the system; these unknowns remain arbitrary and are called parameters.
Step 5. Solve the modified system using Cramer’s rule or Cramer’s theorem. The coefficient matrix for this system
is 𝐴̃ and its main determinant is 𝐷 = det(𝐴̃).
Example 3.5 Solve the given system of equations:
−2𝑥 + 3𝑦 = 2
1) {
4𝑥 − 6𝑦 = 1
−2𝑥 + 3𝑦 − 𝑧 = 2
2) {
𝑥 − 6𝑦 + 3𝑧 = −4
−2𝑥 + 3𝑦 = 2
3) { 𝑥 − 𝑦 = 1
3𝑥 − 5𝑦 = −5
 Beata Ciałowicz ~ 25 ~
 Mathematical Analysis and Linear Algebra – Section 3: Systems of linear equations.
Lecture
3.6 Gauss and Gauss-Jordan methods of solving systems of linear equations.
Definition 3.4 Two systems of linear equations 𝐴1 ∙ 𝑋 = 𝐵1 and 𝐴2 ∙ 𝑋 = 𝐵2 using the same set of variables
(unknowns) are equivalent if they have the same solution(s).

Elementary row or column operations (elementary transformations) are:

1. The interchanging of any two rows (columns) of a matrix (𝑟𝑖 ↔ 𝑟𝑗 ; ↔ means “change”).
2. Multiplying each element of a row (column) by the same nonzero number (𝑘𝑟𝑖 ↦ 𝑟𝑖′ ; ↦ means “replaces”).
3. The replacement of any row (column) by the sum of that row (column) and a nonzero multiple of some other
row (column) (𝑟𝑖 + 𝑘𝑟𝑗 ↦ 𝑟𝑖′ ).

Applications:
1. Calculating determinants (Section 2).
2. Finding the inverse of a matrix (Section 2).
3. Finding the rank of a matrix (Example 3.1b).
4. Solving a general system of linear equations (the Gauss and Gauss-Jordan elimination method)

Remark The row operations on the augmented matrix of a system produce the augmented matrix of
an equivalent system.

 The Gauss elimination method to solve a system of linear equations is described in the following steps
(operations 2 and 3 are performed only on rows!):
Step 1. Write the augmented matrix of the system.
Step 2. Perform elementary row operations to put the augmented matrix into the upper triangular form (TF).
Stop the process in step 2 if you obtain a row whose elements are all zeros except the last one on the right. In
that case, the system is inconsistent and has no solution.

Triangular form (row echelon form) of a matrix (TF):

𝑎̃11 𝑎̃12 … 𝑎̃1𝑘
̃ 𝑅 ], where 𝐴 = [ 0 𝑎̃22 … 𝑎̃2𝑘
Each matrix 𝐴 ∈ 𝑀𝑚,𝑛 (ℝ) has an equivalent triangular form: [𝐴𝑘 𝑘 ] is an
𝟎 𝟎 ⋮ ⋮ ⋱ ⋮
0 0 … 𝑎̃𝑘𝑘
upper triangular matrix of dimensions 𝑘 × 𝑘; 𝑅 is a (nonzero) matrix of rests, 𝟎 is a zero matrix.

Step 3. Solve the equation of the 𝑘 −th row for 𝑥𝑘 , then substitute back into the equation of the (𝑘 − 1) −st row
to obtain a solution for 𝑥𝑘−1 , etc., according to the formula:
𝑘
1
𝑥𝑖 = (𝑏̃𝑖 − ∑ 𝑎̃𝑖𝑗 ∙ 𝑥𝑗 )
𝑎̃𝑖𝑖
𝑗=𝑖+1

Remarks. If the matrix of rests 𝑅 is a column matrix, then the system has one solution.
If the matrix of rests 𝑅 is not a column matrix, then the system has infinitely many solutions.

 Beata Ciałowicz ~ 26 ~
 Mathematical Analysis and Linear Algebra – Section 3: Systems of linear equations. Lecture
 The Gauss-Jordan elimination method to solve a system of linear equations is described in the
following steps:
Step 1. Write the augmented matrix of the system.
Step 2. Use row operations to transform the augmented matrix in the form described below, which is called the
reduced echelon form (REF).

Reduced echelon form/row canonical form (REF):

A matrix 𝐴 ∈ 𝑀𝑚,𝑛 (ℝ) is in reduced echelon form if it has leading ones on the main diagonal and zeros above and
𝐼 𝑅
below the leading ones: [ 𝑘 ], where 𝐼𝑘 is n identity matrix of dimension 𝑘; 𝑅 is a (nonzero) matrix of rests,
𝟎 𝟎
𝟎 is a zero matrix.
Step 3. Stop the process in step 2 if you obtain a row whose elements are all zeros except the last one on the
right. In that case, the system is inconsistent and has no solution. Otherwise, finish step 2 and read the solutions
of the system from the final matrix.

Example 3.6. Solve the system of equations by using the Gauss or the Gauss-Jordan elimination method:
−2𝑥 + 3𝑦 = 2
𝟏) { 𝑥 + 4𝑦 = 1
3𝑥 + 𝑦 = 3
−3𝑥 + 2𝑦 − 𝑧 + 𝑡 = 4
2) {
6𝑥 − 4𝑦 + 2𝑧 − 3𝑡 = 1
𝑥 − 2𝑦 = 3
3){3𝑥 + 5𝑦 = −1
𝑥 + 9𝑦 = −7
2𝑥 + 𝑦 − 3𝑧 = −2
4){ 3𝑥 − 4𝑦 + 2𝑧 = 1
𝑥 + 6𝑦 − 8𝑧 = −5

Remark. During the tests and the final exam substitution method is FORBIDDEN (to use the
substitution method we solve one equation for one of the variables, then we substitute in the other
equation and solve).

 Beata Ciałowicz ~ 27 ~