LINEAR ALGEBRA WITH PROGRAMMING

Chapter 1
VECTORS AND MATRICES
LINEAR ALGEBRA WITH PYTHON

Question
We saw that a system of linear equations
can be represented by the matrix equation

𝐴𝒙 = 𝒃.
Is there a way to write the equation in terms
of 𝒙 to find the solution of the system?
 LINEAR ALGEBRA WITH PROGRAMMING

1.2 Inverse of a matrix

LOOPS WHILE ON PYTHON
Powers and idempotency

Given a square matrix 𝐴 and 𝑘 ∈ ℕ, we write 𝐴𝑘 to denote the product

𝐴𝑘 = 𝐴 .... 𝐴,
of 𝑘 factors of 𝐴.

If 𝐴 verifies 𝐴2 = 𝐴, 𝐴 is said to be an idempotent matrix.

Convention: 𝐴0 = 𝐼.

4
Invertible matrices and singular matrices
A square matrix 𝐴 ∈ 𝑀𝑛 is said to be an invertible matrix if there exists a matrix 𝐵 ∈
𝑀𝑛 such that
𝐴𝐵 = 𝐼𝑛 = 𝐵𝐴.

In that case, such matrix 𝐵 is unique and said to be the inverse of 𝐴, denoted by 𝐴−1 ,

𝐴𝐴−1 = 𝐼𝑛 = 𝐴−1 𝐴.

A square matrix that is not invertible is said to be a singular matrix.

5
Proposition
Let 𝑀 be a square matrix, let 𝑟, 𝑠 ∈ ℤ, let 𝐴 and 𝐵 be invertible matrices of the same
order and 𝑘 ∈ ℝ ∖ 0 . Then:

• 𝑀𝑟 𝑀 𝑠 = 𝑀𝑟+𝑠
• (𝑀𝑟 )𝑠 = 𝑀𝑟𝑠
• 𝐴−1 is invertible and (𝐴−1 )−1 = 𝐴
• 𝐴𝐵 is invertible and (𝐴𝐵)−1 = 𝐵−1 𝐴−1
• 𝑘𝐴 is invertible and (𝑘𝐴)−1 = 𝑘 −1 𝐴−1
• 𝐴𝑇 is invertible and (𝐴𝑇 )−1 = (𝐴−1 )𝑇

6
 Example
2 1
How to check if the matrix 𝐴 = is invertible? Is there a matrix 𝐵 such that 𝐴𝐵 = 𝐼2 ?
4 3
𝑎 + 2𝑐 = 1 1 2 1
ቊ ⇝
1 2 𝑎 𝑏 1 0 𝑎 + 2𝑐 𝑏 + 2𝑑 1 0 3𝑎 + 4𝑐 = 0 3 4 0 1 2 1 0
= ⟺ = ⇝
3 4 𝑐 𝑑 0 1 3𝑎 + 4𝑐 3𝑏 + 4𝑑 0 1 𝑏 + 2𝑑 = 0 1 2 0 3 4 0 1
ቊ ⇝
3𝑏 + 4𝑑 = 1 3 4 1

1 2 1 0 ′ 1 2 1 0 ′ 1 1 2 1 0 1 0 −2 1
𝑅2 = 𝑅2 − 3𝑅1 𝑅2 = − 𝑅2 𝑅1′ = 𝑅1 − 2𝑅2
3 4 0 1 0 −2 −3 1 2 0 1 3/2 −1/2 0 1 3/2 −1/2

1 0 −2 𝑎 = −2
⇝ ቊ
1 0 −2 1 0 1 3/2 𝑐 = 3/2 −2 1
∴𝐵=
0 1 3/2 −1/2 1 0 1 𝑏=1 3/2 −1/2
⇝ቊ
0 1 −1/2 𝑑 = −1/2

Notice that:
1 −2 1 0 1 0 1 −2 1 0 1 0
𝐴 = 𝐼2 and = 𝐵.
0 1 0 −1/2 −3 1 0 1 0 −1/2 −3 1
7
Elementary matrices

An elementary matrix is a square matrix that is obtained from the identity matrix of
the same order by performing a single elementary operation.

8
Examples
1 0 ′ 1 0 1 0
𝑅2 = 𝑅2 − 3𝑅1 so, the matrix is an elementary matrix
0 1 −3 1 −3 1

1 0 0 1 0 0 1 0 0
0 1 0 𝑅2′ = 5𝑅2 0 5 0 so, the matrix 0 5 0 is an elementary matrix
0 0 1 0 0 1 0 0 1

1 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 1 0 0 0 1 0 0
𝑅 ⟷ 𝑅4 so, the matrix is an elementary matrix
0 0 1 0 1 0 0 1 0 0 0 1 0
0 0 0 1 1 0 0 0 1 0 0 0

9
Remark

There is a one-to-one correspondence between elementary operations and

elementary matrices: multiplying an elementary matrix 𝐸 ∈ 𝑀𝑛 to the left of a matrix
𝐴 ∈ 𝑀𝑛×𝑝 consists of applying to 𝐴 the elementary operation corresponding to 𝐸.

10
Examples
1 2 ′ 1 2 1 0 1 2 1 2
𝑅2 = 𝑅2 − 3𝑅1 and also =
3 4 0 −2 −3 1 3 4 0 −2

1 2 1 2 1 0 0 1 2 1 2
3 4 𝑅2′ = 5𝑅2 15 20 and also 0 5 0 3 4 = 15 20
5 6 5 6 0 0 1 5 6 5 6

1 0 0 0 4 4 4 4 0 0 0 1 1 0 0 0 4 4 4 4
2 2 0 0 2 2 0 0 0 1 0 0 2 2 0 0 2 2 0 0
𝑅 ⟷ 𝑅4 and also =
3 3 3 0 1 3 3 3 0 0 0 1 0 3 3 3 0 3 3 3 0
4 4 4 4 1 0 0 0 1 0 0 0 4 4 4 4 1 0 0 0

11
Proposition

Each elementary matrix is invertible and its inverse is an elementary matrix.

12
Remark
If, by performing a finite number of elementary operations on 𝐴 ∈ 𝑀𝑛 ,

𝐴 ~ 𝐸1 𝐴 ~ … … … ~ 𝐸𝑘 … 𝐸2 𝐸1 𝐴,

it is possible to obtain 𝐼𝑛 , that is,

𝐸𝑘 … 𝐸2 𝐸1 𝐴 = 𝐼𝑛 ,

then 𝐴 is invertible and

𝐴−1 = 𝐸𝑘 … 𝐸2 𝐸1 .

𝐴 | 𝐼𝑛 ~ 𝐸1 𝐴 | 𝐸1 ~ … … … ~ 𝐸𝑘 … 𝐸2 𝐸1 𝐴 | 𝐸𝑘 … 𝐸2 𝐸1 = 𝐼𝑛 | 𝐴−1

13
Theorem

If 𝐴, 𝐵 ∈ 𝑀𝑛 are such that 𝐴𝐵 = 𝐼𝑛 , then both 𝐴 and 𝐵 are invertible and 𝐵 = 𝐴−1 or,
equivalently, 𝐴 = 𝐵−1 .

14
 CHALLENGE

Complete the code to count the number of loops till

you get a singular matrix. The output should be
something like this:
Theorem

Let 𝐴 be a square matrix of order 𝑛. The following propositions are equivalent:

• rank 𝐴 = 𝑛.
• The reduced echelon form of 𝐴 is the identity matrix 𝐼𝑛 .
• 𝐴 is invertible.
• A can be written as a product of elementary matrices.
• The system 𝐴𝒙 = 𝒃 is consistent independent, ∀𝑏 ∈ ℝ𝑛 .

16
 Example
1 2
How can I write the matrix 𝐴 = as a product of elementary matrices?
3 4

1 2 1 0 1 2 1 0 1 2 1 0 1 0 −2 1
𝐴|𝐼2 = 𝑅2′ =𝑅2 −3𝑅1 1 𝑅1′ =𝑅1 −2𝑅2 = 𝐼2 |𝐴−1
3 4 0 1 0 −2 −3 1 𝑅2′ =−2𝑅2 0 1 3/2 −1/2 0 1 3/2 −1/2

1 0 1 0 1 −2
𝐸1 = 𝐸2 = 𝐸3 =
−3 1 0 −1/2 0 1

𝐸3 𝐸2 𝐸1 𝐴 = 𝐼2 ⇔ 𝐴 = 𝐸1 −1 𝐸2 −1 𝐸3 −1

1 0 1 0 1 2
∴𝐴=
3 1 0 −2 0 1

17
LINEAR ALGEBRA WITH PYTHON

Answer
If a system of linear equations can be
represented by the matrix equation

𝐴𝒙 = 𝒃
and 𝑨 is invertible, then the system is
consistent independent and the unique
solution of it can be found by
𝒙 = 𝐴−1 𝒃.
1.3.1 Find, if possible, the inverse of the following matrices. Exercises
1 0 −2 1 2 3
8 6
a) b) −3 1 4 c) 4 5 6
5 4
2 −3 4 7 8 9

1.3.2. Consider 𝑋 = 𝑋𝐴𝑋 + 𝑋𝐵𝐴𝑋, where 𝐴, 𝐵 and 𝑋 are non-singular matrices.

a) Solve with respect to 𝑋.
b) Consider now the following matrices:

1 2 −1/2 0
𝐴= and 𝐵= .
2 5 0 −2/3
i. Find 𝐴−1 .
ii. Find 𝑋.

19
 1 0 Exercises
1.3.3 Consider the matrix 𝐴 = 0 1 .
1 0
a) Find the matrix 𝑃 = 𝐴(𝐴𝑇 𝐴)−1 𝐴𝑇 .
b) Obtain, justifying, 𝑃100 .
c) If 𝐴 is the coefficient matrix of a system of linear equations, state, justifying, what
are the possible classifications of the system.

1 0
1.3.4. Consider 𝐴 = −1 1 and 𝐵 = 2 1 1 .
1 1
a) Find, if possible, 𝐴𝐵, 𝐵𝐴 and 𝐵𝑇 𝐵.
b) Knowing that 𝑋𝐴𝑇 𝐴 = 𝐴, find 𝑋.

20
1.3.5 Let 𝐴, 𝐵 and 𝐶 be invertible matrices. Simplify the expressions.
Exercises
a) (𝐴2 )𝑇 (𝐴(2𝐴−1 )𝐴𝑇 )−1 𝐴−1
b) ((𝐴 + 𝐵𝑇 )𝑇 −(𝐵𝐴𝐵 + 𝐴𝑇 𝐴𝐵))(𝐼 − 𝐴𝐵)−1
c) (𝐴 − 𝐵𝑇 )𝑇 +𝐶(𝐵−1 𝐶)−1

0 1 0 0 0 −1 0 0
1 −2 0 0 0 2 0 0
1.3.6 Consider 𝐴 = and 𝐵 = .
−3 6 1 0 0 −6 −1 0
−4 8 0 5 0 0 0 −5
a) Write 𝐴 as the product of elementary matrices.
b) Is it possible to find a 𝒃 ∈ ℝ4 such that 𝐴𝒙 = 𝒃 is consistent dependent?
c) Show that 𝐶 = 𝐴 − 𝐴𝑇 is antisymmetric.
d) For 𝐷 = 𝐴 + 𝐵, find the smallest natural 𝑘 such that 𝐷 𝑘 = 𝟎4 where 𝟎4 represents
the null matrix 4 × 4.

21
 Exercises

1 2 0 1
1.3.7 Consider 𝐴 = 3 6 0 3 and its reduced echelon form, 𝑅.
0 0 2 4
a) Find 𝑅.
b) Write the elementary matrix associated to each elementary operation used in a).
c) Find a matrix 𝐶 such that 𝐶𝐴 = 𝑅. Is this matrix unique?

1.3.8 True or false?

a) There are systems of linear equations 𝐴𝒙 = 𝒃 with only two distinct solutions.
b) For any 𝑛 × 𝑛 matrix 𝐴, if 𝐴2 is invertible then 𝐴 is invertible.

22
1.3.9 Carefully explain the output of the following programs.
Exercises
i. A

ii. B

iii. C

23
1.3.1 a)
2 −3
8
b) 10
3
4
1
1 c) Not invertible Solutions
−5/2 4
7/2 3/2 1/2
5 −2 10 −6
1.3.2 a) 𝑋 = 𝐴−1 𝐵 + 𝐼 −1 b) i. ii.
−2 1 −4 3
1 1
0
2 2
1.3.3 a) 𝑃 = 0 1 0 b) 𝑃100 = 𝑃 c) Inconsistent, consistent independent
1 1
0
2 2
4 2 2 1/3 0
1.3.4 a) 𝐴𝐵 not defined, 𝐵𝐴 = 2 2 ,𝐵 𝐵= 2
𝑇
1 1 b) 𝑋 = −1/3 1/2
2 1 1 1/3 1/2
1.3.5 a) 1/2𝐴𝑇 𝐴−1 ; b) 𝐴𝑇 + 𝐵; c) 𝐴𝑇
0 1 0 0 1 0 0 0 1 0 0 0 1 −2 0 0 1 0 0 0
1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0
1.3.6 a) For eg, b) Yes d) 𝑘 = 3
0 0 1 0 −3 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 −4 0 0 1 0 0 0 1 0 0 0 5
1 2 0 1 1 0 0 1 0 0 1 0 0
1.3.7 a) 𝑅 = 0 0 1 2 b) For instance, 𝐸1 = −3 1 0 , 𝐸2 = 0 0 1 , 𝐸3 = 0 1/2 0 c) For instance, 𝐶 =
0 0 0 0 0 0 1 0 1 0 0 0 1
1 0 0
0 0 1/2 . Not unique.
−3 1 0
1.3.8 a) False; b) True

24