Linear Algebra & Geometry

LECTURE 10

• Matrices
• Elementary row operations (EROS)
• Rank of a matrix
Fact.
1 𝑖𝑓 𝑠 = 𝑡
The 𝑛𝑛 matrix 𝐼 defined as 𝐼(𝑠, 𝑡) = ቊ is the identity
0 𝑖𝑓 𝑠 ≠ 𝑡
element for matrix multiplication in 𝔽𝑛×𝑛 .
Indeed, for every matrix 𝐴, 𝐴𝐼 𝑖, 𝑗 = σ𝑛𝑡=1 𝐴(𝑖, 𝑡)𝐼(𝑡, 𝑗) =
𝐴 𝑖, 𝑗 because 𝐴 𝑖, 𝑡 𝐼 𝑡, 𝑗 = 𝐴(𝑖, 𝑗) when 𝑡 = 𝑗 and 0
otherwise. Hence 𝐴𝐼 = 𝐴. A similar argument proves that 𝐼𝐴 = 𝐴.

The existence of the identity element for matrix multiplication in

𝔽𝑛×𝑛 raises the question of invertibility. We will address the
question soon enough.
All entries of the identity matrix 𝐼 are equal to 0 except for the
diagonal entries which are all equal to 1. The term diagonal
entries of a square 𝑛𝑛 matrix 𝐴 refers to the main diagonal of
the 𝑛𝑛 matrix, i.e., the line connecting the top-left with the
bottom-right corner of the matrix. The line consists of all
elements of the form 𝐴(𝑖, 𝑖), i=1,2, … , n.

1 0 0
𝐼= 0 1 0 the 3 × 3 identity matrix.
0 0 1
Theorem.
For every 𝑛𝑘 matrix 𝐴 and for every two 𝑘𝑠 matrices 𝐵 and 𝐶,
𝐴 𝐵 + 𝐶 = 𝐴𝐵 + 𝐴𝐶, i.e. matrix multiplication is distributive
with respect to matrix addition.

Theorem.
For every 𝑛𝑘 matrix 𝐴, 𝑘𝑠 matrix 𝐵 and 𝑠𝑙 matrix 𝐶,
𝐴 𝐵𝐶 = (𝐴𝐵)𝐶, i.e. matrix multiplication is associative.

We postpone proving the last two theorems until we introduce

linear mappings and their matrix representations. Then, the
theorems follow easily from some general facts.
Definition.
Transposition is another matrix-specific operation. If 𝐴 is an mn
matrix then "𝐴 transposed" is the nm matrix 𝐴T such that for
each i and j (1 i n,1 j m) 𝐴𝑇(𝑖, 𝑗) = 𝐴(𝑗, 𝑖).

In other words, the first row of 𝐴 becomes the first column of 𝐴𝑇

and so on: 𝑇
𝑎1,1 𝑎1,2 … 𝑎1,𝑛 𝑎1,1 𝑎2,1 … 𝑎𝑚,1
𝑎2,1 𝑎2,2 … 𝑎2,𝑛 𝑎1,2 𝑎2,2 … 𝑎𝑚,2
⋮ ⋮ … ⋮ = ⋮ ⋮ … ⋮
𝑎𝑚,1 𝑎𝑚,2 … 𝑎𝑚,𝑛 𝑎1,𝑛 𝑎2.𝑛 … 𝑎𝑛,𝑚

Definition.
If 𝐴 = 𝐴𝑇 then 𝐴 is said to be symmetric.
Example.

1
[1 3 4]𝑇 = 3 ,
4
1 𝑇
([1 3 4]𝑇 ) 𝑇 = 3 = [1 3 4]
4

Fact. (obvious)
For every matrix 𝐴, 𝐴𝑇 𝑇 = 𝐴
For every two matrices of matching sizes, 𝐴 + 𝐵 𝑇 = 𝐴𝑇 + 𝐵𝑇
Fact. (less obvious but easy enough)
For every two matrices 𝐴 and 𝐵 such that 𝐴𝐵 exists
𝐴𝐵 𝑇 = 𝐵𝑇 𝐴𝑇
Proof.
𝐴𝐵 𝑇 𝑗, 𝑖 = (𝐴𝐵) 𝑖, 𝑗 =
𝑛 𝑛 𝑛

෍ 𝐴 𝑖, 𝑠 𝐵 𝑠, 𝑗 = ෍ 𝐴𝑇 𝑠, 𝑖 𝐵𝑇 𝑗, 𝑠 = ෍ 𝐵𝑇 𝑗, 𝑠 𝐴𝑇 𝑠, 𝑖 =
𝑠=1 𝑠=1 𝑠=1

𝐵𝑇 𝐴𝑇 (𝑗, 𝑖). QED

Definition.
Let 𝐴 be an 𝑛𝑘 matrix. We say that 𝐴 is a row echelon matrix iff
(a) if 𝑟𝑖 is a nonzero row of 𝐴 then 𝑟𝑖−1 is also a nonzero row,
𝑖 = 2,3, …
(b) if 𝑎𝑖,𝑗 is the first nonzero entry in 𝑟𝑖 and 𝑎𝑖−1,𝑝 is the first
nonzero entry in 𝑟𝑖−1 then 𝑝 < 𝑗
If, in addition,
(c) the first nonzero entry in each nonzero row is equal to 1
(d) the first nonzero entry in each nonzero row is the only
nonzero entry in its column
then A is called a row canonical matrix.
Example.

0 2 1 1 1 2 1 1
1 1 3 0 0 1 2 0
𝐴= 𝐵=
2 1 0 0 0 0 0 0
1 3 4 1 0 0 0 2

1 2 1 1 1 7 0 3
0 1 2 0 0 0 1 2
𝐶= 𝐷=
0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0
Definition.
The following transformations of a matrix are called elementary row
operations (EROS):
1. 𝑟𝑖 ↔ 𝑟𝑗 - replacing row 𝑟𝑖 with 𝑟𝑗 and vice versa (row swapping)
2. 𝑟𝑖 ← 𝑐𝑟𝑖 - replacing row 𝑟𝑖 with 𝑟𝑖 scaled by a nonzero constant c. In
practice, we abbreviate the symbol to 𝑐𝑟𝑖
3. 𝑟𝑖 ← 𝑟𝑖 + 𝑟𝑗 - replacing row 𝑟𝑖 with the sum of 𝑟𝑖 and 𝑟𝑗 (adding of 𝑟𝑗
to 𝑟𝑖 ). Usually, we write simply 𝑟𝑖 + 𝑟𝑗 .
4. 𝑟𝑖 ← 𝑟𝑖 + 𝑐𝑟𝑗 - replacing row 𝑟𝑖 with the sum of 𝑟𝑖 and the multiple of
𝑟𝑗 by a constant c. We just write 𝑟𝑖 + 𝑐𝑟𝑗 for short.
Notice that 4 is a composition of 2 and 3. Namely, we do 𝑐𝑟𝑗 , then 𝑟𝑖 + 𝑟𝑗
(here 𝑟𝑖 denotes the “new” row j, after scaling) and finally 𝑐 −1 𝑟𝑗 to convert
row j to its original form.
Definition.
Matrices 𝐴 and 𝐵 are said to be row-equivalent iff 𝐴 can be
transformed into 𝐵 by a (finite) number of elementary row
operations. We denote row-equivalence by 𝐴~𝐵.

Proposition.
The relation of row-equivalence is an equivalence relation on
𝔽𝑛×𝑚 .
Theorem.
Every matrix 𝐴 is row-equivalent to some row-canonical matrix
𝐵. In other words, every matrix can be row-reduced to a row-
canonical matrix.
Proof. (Row-reduction algorithm)
𝑎1,1 𝑎1,2 … 𝑎1,𝑛
𝑎2,1 𝑎2,2 … 𝑎2,𝑛
𝐴= ⋮ ⋮ … ⋮ .
𝑎𝑚,1 𝑎𝑚,2 … 𝑎𝑚,𝑛
Step 1: Swap rows (if necessary) to get a non-zero number in the
top position, (1,1). If all entries in column 1 are 0 do this for
−1
column 2 instead, if … . Multiply row 1 (new row 1) by 𝑎1,1
(new 𝑎1,1 inverse). Use operation 4 to eliminate (turn into 0)
every entry below the resulting 1)
 1 𝑏1,2 … 𝑏1,𝑛
0 𝑏2,2 … 𝑏2,𝑛
This results in a new matrix, say 𝐴1 = .
⋮ ⋮ … ⋮
0 𝑏𝑚,2 … 𝑏𝑚,𝑛
Step 2: Apply Step 1 to the matrix 𝐴1 without row 1, i.e., to the
0 𝑏2,2 … 𝑏2,𝑛
0 𝑏3,2 … 𝑏3,𝑛
matrix . This results in something like
⋮ ⋮ … ⋮
0 𝑏𝑚,2 … 𝑏𝑚,𝑛

1 𝑏1,2 𝑏1,3 … 𝑏1,𝑛

0 1 𝑐2,3 … 𝑐2,𝑛
. Repeat step 2 until you obtain
⋮ ⋮ ⋮ … ⋮
0 0 𝑐𝑚,3 … 𝑐𝑚,𝑛
something like this
Repeat step 2 until you obtain a matrix like this
1 𝑏1,2 𝑏1,3 … … 𝑏1,𝑛
0 1 𝑐2,3 … … 𝑐2,𝑛
⋮ ⋮ ⋮ … … ⋮
0 0 0 … 1 ?
0 0 0 … 0 0
0 0 0 … … 0

This is a row echelon matrix with a leading 1 in each non-zero

row.
Step 3. Apply operation 4 to eliminate all non-zeroes above the
leading 1's. Thanks to the form of the nonzero rows, this will not
destroy any zero to the left of the leading 1's.
Example.
0 0 2 1 1 0 2 6 4 2 0 1 3 2 1
0 1 1 1 0 0 1 1 1 0 𝑟1 0 1 1 1 0
𝐴= 𝑟 ↔ 𝑟4
0 2 1 0 0 1 0 2 1 0 0 2 0 2 1 0 0
0 2 6 4 2 0 0 2 1 1 0 0 2 1 1
0 1 3 4 1 0 1 3 4 1
0 0 −2 −1 −1 0 0 1 2 0
𝑟2 − 𝑟1 , 𝑟3 − 2𝑟1 2𝑟2 − 𝑟3
0 0 −5 −4 −2 0 0 −5 −4 −2
0 0 2 1 1 0 0 2 1 1

0 1 3 4 1 0 1 3 4 1
0 0 1 2 0 1 1 0 0 1 2 0
𝑟3 + 5𝑟2 , 𝑟4 − 2𝑟2 𝑟4 + 𝑟3 , 𝑟3 1
0 0 0 6 −2 2 6 0 0 0 1 −
3
0 0 0 −3 1 0 0 0 0 0
1
0 1 0 −2 1 0 1 0 0
2 3
0 0 1 0 0 0 1 0
2
3
𝑟1 − 3𝑟2 , 𝑟2 − 2𝑟3 1 𝑟1 + 2𝑟3 3
0 0 0 1 − 0 0 0 1 −
1
3
3
0 0 0 0 0 0 0 0 0 0
Definition.
The row rank of an 𝑛 × 𝑚 matrix 𝐴, 𝑟(𝐴), is the dimension of
the subspace of 𝔽𝑚 spanned by rows of A.
Theorem.
For every two matrices 𝐴 and 𝐵, if 𝐴~𝐵 then 𝑟(𝐴) = 𝑟(𝐵).
Proof. (outline)
We prove this by showing that each elementary row operation
preserves the very space spanned by rows of the matrix hence, it
also preserves its dimension.
Note. Since the rank of any row echelon matrix is clearly the
number of its nonzero rows, the theorem provides a method for
calculating the rank of the matrix - row reduce the matrix to a
row echelon one and count its nonzero rows.
In particular, the rank of the matrix from the last example is 3
Theorem.
For every matrix 𝐴, 𝑟 𝐴 = 𝑟(𝐴𝑇 ).
We skip the proof .
Note. We could just as well define column rather than row
operations and column rank of a matrix. In view of the last
theorem the row and the column rank of every matrix is the same,
so we just use the term rank.
FAQ.
1. Can we do several EROS in one step, like you did in the example?
It depends. A common mistake is to do something like 𝑟1 − 𝑟2 and
𝑟3 − 𝑟1 in one go. What is wrong with this? Row 𝑟1 is modified by
the first operation which means in the second one you should use the
new 𝑟1 . On the other hand, if you first do 𝑟3 − 𝑟1 and then 𝑟1 − 𝑟2 it's
ok. In extreme cases, people might row-reduce any matrix to nil, like
this:
𝑎 𝑏 𝑎−𝑐 𝑏−𝑑 0 0
~ 𝑟1 − 𝑟2 , 𝑟2 − 𝑟1 ~ 𝑟1 + 𝑟2 , 𝑟2 + 𝑟1
𝑐 𝑑 𝑐−𝑎 𝑑−𝑏 0 0
In short, when in doubt do one ERO at a time.
FAQ.
2. Can we mix EROS with ECOS?
It depends. You must avoid doing row and column operations in one
transformation: writing A~(𝑟1 − 𝑟3 , 𝑐4 + 𝑐1 ) 𝐵 is asking for trouble
because after 𝑟1 − 𝑟3 columns 𝑐4 and 𝑐1 are not what they were, a
row operation affects all columns (a row contains one entry from
each column).
3. OK, can we mix EROS with ECOS but using only EROS or only
ECOS within a single transformation?
It depends. If you calculate a determinant (soon to be introduced) it's
ok. If you calculate the rank of a matrix – no worries.
But if you are solving a system of equations – beware. Row
operations correspond to operations on equations (side-to-side
addition and the like) which preserve the solution set of a system.
Column operations would mean adding coefficients of one unknown
to coefficients of another – that makes no sense at all.