Solving linear Systems
Z. ABBAS
LAU
February 1, 2024
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 1 / 36
Contents
1 2.3: Inverse of a matrix
Definition of inverse of a matrix
Cancelation Property
Finding the inverse of (n × n) matrix.
2 Solving a system of Linear Equation using Inverse of Matrices
3 LU factorization
4 Trace of a matrix
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 2 / 36
Question I
Let A, M and N be three (n × n) matrices. Show that if AM = In and
NA = In then M = N.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 3 / 36
Question I
Let A, M and N be three (n × n) matrices. Show that if AM = In and
NA = In then M = N.
Answer: we have NA = In . Multiplying by M, we get:
NAM = (NA)M = In M = M and also NAM = N(AM) = NIn = N. Hence
the equality holds.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 3 / 36
Inverse of a square matrix
Definition
A square matrix A of order n is said to be invertible/non-singular if there is
a matrix B of order n such that AB = BA = In .
Remark: It’s enough to show that AB = In or BA = In to conclude that A
is invertible and it’s inverse is B.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 4 / 36
Question II
Let A be square matrix of order n . Suppose that A is invertible, show that:
1 A−1 invertible.
2 AT also written as tA is invertible.
3 If B also is an invertible square matrix of order n, then AB is
invertible.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 5 / 36
Question II-Answer
1 since A is invertible, then there exists a square matrix of order n
denoted A−1 such that AA−1 = In , thus evidently A−1 is invertible
and (A−1 )−1 = A .
2 since A is invertible, we have AA−1 = In .
Then (AA−1 )T = (In )T = In .
Thus (A−1 )T AT = In , so AT is invertible and (AT )−1 = (A−1 )T .
3 B −1 A−1 (AB) = B −1 (A−1 A)B = B −1 (In B) = B −1 B = In . so Ab is
invertible and (AB)−1 = B −1 A−1
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 6 / 36
Properties of inverses
If A is an invertible matrix, k is a positive integer and c is a scalar not
equal to zero. Then A−1 , Ak , cA and AT are invertible and the following
statements are true:
a) (A−1 )−1 = A.
b) (AT )−1 = (A−1 )T .
c) (Ak )−1 = (A−1 )k .
d) (cA)−1 = c1 A−1 .
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 7 / 36
Question III
a b d −b
1 Calculate the product AB where A = and B =
c d −c a
2 What do you deduce?.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 8 / 36
Answer
a b d −b ad − bc 0
1 AB = =
c d −c a 0 ad − bc
2 From part 1, we have AB = (ad − bc)In . If (ad − bc) ̸= 0, then
1 1 1
A( (ad−bc) B) = (ad−bc) AB = (ad−bc) (ad − bc)In = In . Thus, if
(ad-bc)̸= 0 , then A is invertible and
−1
a b 1 d −b
= (ad−bc)
c d −c a
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 9 / 36
Inverse of a (2 × 2) matrix
Strategy
a b
If A = is an 2 × 2 matrix
c d
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 10 / 36
Inverse of a (2 × 2) matrix
Strategy
a b
If A = is an 2 × 2 matrix such that ad − bc ̸= 0,
c d
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 10 / 36
Inverse of a (2 × 2) matrix
Strategy
a b
If A = is an 2 × 2 matrix such that ad − bc ̸= 0,then A is
c d
invertible and its inverse is given by
−1 1 d −b
A = .
ad − bc −c a
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 10 / 36
Example
2 4
a) A = .
1 −3
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Example
2 4
a) A = . ad − bc = −10 ̸= 0
1 −3
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Example
2 4
a) A = . ad − bc = −10 ̸= 0
1 −3
=⇒ A−1 =
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Example
2 4
a) A = . ad − bc = −10 ̸= 0
1 −3
−1 1 −3 −4
=⇒ A = − =
10 −1 2
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Example
2 4
a) A = . ad − bc = −10 ̸= 0
1 −3
3 2
−1 1 −3 −4
=⇒ A = − = 10
1
5
1 .
10 −1 2 10 −5
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Example
2 4
a) A = . ad − bc = −10 ̸= 0
1 −3
3 2
−1 1 −3 −4
=⇒ A = − = 10
1
5
1 .
10 −1 2 10 −5
1 2
b) B = .
2 4
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Example
2 4
a) A = . ad − bc = −10 ̸= 0
1 −3
3 2
−1 1 −3 −4
=⇒ A = − = 10
1
5
1 .
10 −1 2 10 −5
1 2
b) B = . ad − bc = 0
2 4
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Example
2 4
a) A = . ad − bc = −10 ̸= 0
1 −3
3 2
−1 1 −3 −4
=⇒ A = − = 10
1
5
1 .
10 −1 2 10 −5
1 2
b) B = . ad − bc = 0 =⇒ B is a singular matrix.
2 4
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 11 / 36
Question IV
1 1
Compute A−2 in two different ways for A = .
2 4
Solution:
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 12 / 36
Question IV
1 1
Compute A−2
in two different ways for A = .
2 4
9
− 54
−2 2 −1
Solution: A = (A ) = (A ) = −1 2 2
3 .
− 52 4
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 12 / 36
Question V
Find the inverse of AB with
1 3 3 1 2 3
A = 1 4 3 and B = 1 3 3.
1 3 4 2 4 3
using two different methods.
Solution:
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 13 / 36
Question V
Find the inverse of AB with
1 3 3 1 2 3
A = 1 4 3 and B = 1 3 3.
1 3 4 2 4 3
using two different methods.
7 −3 −3 1 −2 1
Solution: A−1 = −1 1 0 and B −1 = −1 1 0 .
2
−1 0 1 3 0 − 13
−1
method 1: (AB) = B A −1 −1
method 2: Compute −1
AB then findits inverse which is (AB) .
8 −5 −2
Hence (AB)−1 = −8 4 3
5 −2 − 37
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 13 / 36
1 2.3: Inverse of a matrix
Definition of inverse of a matrix
Cancelation Property
Finding the inverse of (n × n) matrix.
2 Solving a system of Linear Equation using Inverse of Matrices
3 LU factorization
4 Trace of a matrix
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 14 / 36
Theorem:
If C is an invertible matrix, then the following statements hold:
a) IfAC = BC =⇒ A = B.
b) If CA = CB =⇒ A = B.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 15 / 36
Example
Solve the following matrix equation AX + 2B = B T where
1 3 3 1 2 3
A= 1 4 3
and B= 1 3 3
1 3 4 2 4 3
Solution
X = A−1 (B T − 2B)
so
7 −3 −3 1 1 2 1 2 3 !
X = −1 1 0 2 3 4 − 2 1 3 3 = · · ·
−1 0 1 3 3 3 2 4 3
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 16 / 36
Elementary matrices
definition
We call elementary matrix each of the following matrices:
1 In (Rt ↔ Rs ).
2 In (Rt → Rt + αRs ).
3 In (Rt → αRt ), where α ̸= 0.
Let A be a (n × m) matrix. The following hold:
1 A(Rt ↔ Rs ) = In (Rt ↔ Rs )A.
2 A(Rt → Rt + αRs ) = In (Rt → Rt + αRs )A.
3 A(Rt → αRt ) = In (Rt → αRt )A, where α ̸= 0.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 17 / 36
Show that A(Rt ↔ Rs ) = In (Rt ↔ Rs )A.
Let 1 ≤ i ≤ n. Then:
1 if i=t:
Ri (In (Rt ↔ Rs )A) = Rt (In (Rt ↔ Rs )A) = Rt (In (Rt ↔ Rs ))A =
Rs (In )A = Rs (A).
2 if i=s:
Ri (A(Rt ↔ Rs )) = Rs (A(Rt ↔ Rs )) = Rs (In (Rt ↔ Rs )A) =
Rs (In (Rt ↔ Rs ))A = Rt (In )A = Rt (A).
3 if i ̸= s and i ̸= t:
Ri (A(Rt ↔ Rs )) = Ri (In (Rt ↔ Rs )A) = Ri (In (Rt ↔ Rs ))A =
Ri (In )A = Ri (A).
Hence In (Rt ↔ Rs )A = A(Rt ↔ Rs )
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 18 / 36
Inverses of elementary matrices
The inverse of
1 In (Rt ↔ Rs ) is In (Rt ↔ Rs ) .
2 for s ̸= t, In (Rt → Rt + αRs ) is In (Rt → Rt − αRs ).
3 In (Rt → αRt ), where α ̸= 0 is In (Rt → α−1 Rt ) .
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 19 / 36
Theorem
If A is a (n × n) invertible matrix over K, then A can be changed to In by
a finite sequence of elementary row operations.
Proof: By induction on n.
Theorem
Let A be a (n × n) matrix over K. Then A is invertible if and only if A can
be changed to In by a finite sequence of elementary row operations.
Proof: The N.C is the previous theorem. Here is the sufficient condition.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 20 / 36
Question
Check if the following matrix is invertible.
Then A is not invertible.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 21 / 36
Corollary
If A is a (n × n) invertible matrix over K, then A−1 is obtained from In by
carrying the same row operations after which A is changed to In .
Proof: Let E1 , E2 , · · · , En be the elementary matrices corresponding to the
elementary operations after which A is changed to In . Then
En En−1 · · · E1 A = In
. Then A−1 = En En−1 · · · E1 , thus A−1 is obtained from In by carrying the
same elementary operations after which A is changed to In .
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 22 / 36
J.G.R to find A−1
Let A be an n × n matrix.
To determine its inverse, we follow these steps:
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 23 / 36
J.G.R to find A−1
Let A be an n × n matrix.
To determine its inverse, we follow these steps:
1) Write the n × 2n matrix [A|In ].
2) Apply, to the whole matrix [A|In ], the row operations used in J.G.R
method to find the r.r.e.f of A.
Theorem
A (n × n) matrix A is invertible iff it’s row equivelant to In .
If the previous n × 2n matrix is transformed to [In |B]. The matrix A is
then invertible and B is the inverse of A, equivalently, B = A−1 .
remark. If A can’t be tranformed into In through elementary row
operations, then it’s not invertible.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 23 / 36
Example (Find the inverse of the following matrices)
1 4 3
a) A = −1 −2 0.
2 2 3
Solution:
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 24 / 36
Example (Find the inverse of the following matrices)
1 4 3
a) A = −1 −2 0.
2 2 3
Solution:
[A|I3 ] =
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 24 / 36
Example (Find the inverse of the following matrices)
1 4 3
a) A = −1 −2 0.
2 2 3
Solution:
1 4 3 1 0 0
[A|I3 ] = −1 −2 0 0 1 0
2 2 3 0 0 1
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 24 / 36
Example (Find the inverse of the following matrices)
1 4 3
a) A = −1 −2 0.
2 2 3
Solution:
1 4 3 1 0 0
R + R1 −→ R2
[A|I3 ] = −1 −2 0 0 1 0 2 =⇒
R3 − 2R1 −→ R3
2 2 3 0 0 1
1 4 3 1 0 0
0 2 3 1 1 0 R3 + 3R2 −→ R3 =⇒
0 −6 −3 −2 0 1
1 4 3 1 0 0
R − 1 R −→ R2
0 2 3 1 1 0 2 21 3 =⇒
R1 − 2 R3 −→ R1
0 0 6 1 3 1
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 24 / 36
Example
1
− 23 − 12
1 4 0 2
1
− 21 − 12
0
2 0 2 R1 − 2R2 −→ R1 =⇒
0 0 6 1 3 1
0 0 − 21 − 12 1
1 2
1
1 R2 × −→ R2
− 12 − 12
0 2 0 2 =⇒
2 1
R3
× 6 −→ R3
0 0 6 1 3 1
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 25 / 36
Example
1 0 0 − 12 − 21 1
2
0 1 0 1 − 41 − 14
4 = [I3 |B].
0 0 1 16 1
2
1
6
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 26 / 36
Example
1 0 0 − 12 − 21 1
2
1 1 1
0 1 0
4 −4 −4 = [I3 |B].
1 1 1
0 0 1 6 2 6
1 1 1
−2 −2 2
1 4 3 1
1 0 0
1 1
AB = −1 −2 0 4 − 4 − 4 = 0 1 0 = I3
2 2 3 0 0 1
1 1 1
6 2 6
and
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 26 / 36
Example
BA =
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 27 / 36
Example
1
− 12 1
−2 2
1 4 3 1 0 0
1
− 41 − 14
BA = −1 −2 0 = 0 1 0 = I3 .
4
2 2 3 0 0 1
1 1 1
6 2 6
Thus, B = A−1 .
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 27 / 36
Example
1
− 12 1
−2 2
1 4 3 1 0 0
1
− 41 − 14
BA = −1 −2 0 = 0 1 0 = I3 .
4
2 2 3 0 0 1
1 1 1
6 2 6
Thus, B = A−1 .
1 −1 0
b) A = 1 0 −1.
−6 2 3
Solution: Homework.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 27 / 36
1 2.3: Inverse of a matrix
Definition of inverse of a matrix
Cancelation Property
Finding the inverse of (n × n) matrix.
2 Solving a system of Linear Equation using Inverse of Matrices
3 LU factorization
4 Trace of a matrix
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 28 / 36
Theorem
The system AX = b of n linear equations in n unknowns has a unique
solution if and only if A is Invertible. In this case, the solution X is given
by X = A−1 b.
Note that at this point we have shown that the following statements are
equivalent for an (n × n) matrix A:
1 A is nonsingular.
2 Ax = 0 has a unique solution-the trivial solution.
3 A is row (column) equivalent to In ( the r.r.e.f of A is In ).
4 The linear system Ax = b has a unique solution for every (n × n)
matrix b.
5 A is a product of elementary matrices.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 29 / 36
Example (Solve the system using the inverse of Matrices)
a)
x1 +4x2 +3x3 = 12,
(S) −x1 −2x2 = −12,
2x1 +2x2 +3x3 = 8.
Solution:
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 30 / 36
Example (Solve the system using the inverse of Matrices)
a)
x1 +4x2 +3x3 = 12,
(S) −x1 −2x2 = −12,
2x1 +2x2 +3x3 = 8.
Solution:System (S) can be written as AX = b with
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 30 / 36
Example (Solve the system using the inverse of Matrices)
a)
x1 +4x2 +3x3 = 12,
(S) −x1 −2x2 = −12,
2x1 +2x2 +3x3 = 8.
Solution:System
(S)
can be written as AX = b with
1 4 3
A = −1 −2 0,
2 2 3
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 30 / 36
Example (Solve the system using the inverse of Matrices)
a)
x1 +4x2 +3x3 = 12,
(S) −x1 −2x2 = −12,
2x1 +2x2 +3x3 = 8.
Solution:System
(S)
can be written as AX = b with
1 4 3 x1
A = −1 −2 0,X = x2
2 2 3 x3
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 30 / 36
Example (Solve the system using the inverse of Matrices)
a)
x1 +4x2 +3x3 = 12,
(S) −x1 −2x2 = −12,
2x1 +2x2 +3x3 = 8.
Solution:System
(S)
can be written as AX
= b with
1 4 3 x1 12
A = −1 −2 0,X = x2 and b = −12.
2 2 3 x3 8
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 30 / 36
Example (Solve the system using the inverse of Matrices)
In the previous example, we have find that the inverse of A is given by
1
− 2 − 21 1
2
A−1 = 1 1 1
4 − 4 − 4 .
1 1 1
6 2 6
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 31 / 36
Example (Solve the system using the inverse of Matrices)
In the previous example, we have find that the inverse of A is given by
1
− 2 − 21 1
2
A−1 = 1 1 1
4 − 4 − 4 .
1 1 1
6 2 6
Then, system (S) has a unique solution given by
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 31 / 36
Example (Solve the system using the inverse of Matrices)
In the previous example, we have find that the inverse of A is given by
1
− 2 − 21 1
2
A−1 = 1 1 1
4 − 4 − 4 .
1 1 1
6 2 6
Then, system (S) has a unique solution given by
X =
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 31 / 36
Example (Solve the system using the inverse of Matrices)
In the previous example, we have find that the inverse of A is given by
1
− 2 − 21 1
2
A−1 = 1 1 1
4 − 4 − 4 .
1 1 1
6 2 6
Then, system (S) has a unique solution given by
1
− 2 − 21 1
2
12 4
X = A−1 b = 1 1 1
4 − 4 − 4 −12 = 4 .
8 − 38
1 1 1
6 2 6
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 31 / 36
Example (Solve the system using the inverse of Matrices)
Hence, x1 = 4, x2 = 4 and x3 = − 83 is the solution of system (S).
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 32 / 36
Introduction
Our aim is to write a matrix A = [aij ] ∈ Mn (C) as follows:
A = LU,
where L = [lij ] ∈ Mn (C) is a Lower Triangular matrix and
U = [uij ] ∈ Mn (C) is an Upper Triangular one.
Equivalently lij = 0 for all i < j and uij = 0 for all i > j. We will assume in
addition, that lii = 1.
Thus
1 0 0
L = l21 1 0 ,
l31 l32 1
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 33 / 36
Introduction
Our aim is to write a matrix A = [aij ] ∈ Mn (C) as follows:
A = LU,
where L = [lij ] ∈ Mn (C) is a Lower Triangular matrix and
U = [uij ] ∈ Mn (C) is an Upper Triangular one.
Equivalently lij = 0 for all i < j and uij = 0 for all i > j. We will assume in
addition, that lii = 1.
Thus
1 0 0 u11 u12 u13
L = l21 1 0 , U = 0 u22 u23 .
l31 l32 1 0 0 u33
By applying the matrix multiplication between L and U and by comparing
with A, we can find the entries of the matrices L and U.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 33 / 36
Solve using the LU decomposition the following statement
x1 +4x2 +3x3 = 12,
(S) −x1 −2x2 = −12,
2x1 +2x2 +3x3 = 8.
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 34 / 36
Exs
Example
Find the LU factorization of the following matrices:
1 2 4
1- A = 3 8 14.
2 6 13
3 1 6
2- B = −6 0 −16.
0 8 −17
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 35 / 36
Definition
Let A = [aij ] ∈ Mn (C). The trace function tr defined by
tr : Mn (C) −→ C, is given by
n
X
tr (A) = aii .
i=1
Let A, B ∈ Mn (C) and let α and β be two scalars. Then:
1- tr (αA + βB) = αtr (A) + βtr (B).
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 36 / 36
Definition
Let A = [aij ] ∈ Mn (C). The trace function tr defined by
tr : Mn (C) −→ C, is given by
n
X
tr (A) = aii .
i=1
Let A, B ∈ Mn (C) and let α and β be two scalars. Then:
1- tr (αA + βB) = αtr (A) + βtr (B).
2- tr (AT ) = tr (A).
3- tr (AB) = tr (BA).
Z. ABBAS (LAU) Solving linear Systems February 1, 2024 36 / 36
