This content is protected and may not be shared, uploaded, or distributed. II.

System of Equations

II. System of Equations

7. The four fundamental subspaces of a matrix

Goals

• learn about the orthogonal complement of a vector space and its properties.
• learn about the four fundamental subspaces of a matrix and its properties.
• compute the four fundamental subspaces of a matrix using its 𝐿𝑀 decomposition.
• learn about the Rank-Nullity Theorem relating the nullity and rank of a matrix.

Orthogonal complement
De!nition: orthogonal complement

Let V be a subspace of R𝑁 . The unique orthogonal complement of V, denoted by V → , is de!ned by

V → = {w ↑ R𝑁 | w · v = w↓ v = 0 for all v ↑ V }.

Note: dim(V) + dim(V → ) = 𝑁

Example 1. Let V be a plane in R3 passing through 0, its orthogonal complement V → is a line with

•
V→
dim(V → ) = 𝑁 ↔ dim(V) =

•
V

1 0
!     *
Example 2. If V = span " 0 , 2 +, then
   
# 0 3 ,

V→ =

63 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

Properties of orthogonal complement

Let V and W be subspaces of R𝑁 . Then,

(i) V → is a subspace of R𝑁 .

(ii) V ↗ V → = R𝑁

(iii) (V → ) → = V

(iv) If V ↘ W, then W → ↘ V → .

(v) (V + W) → = V → ≃ W →

(vi) (V ≃ W) → = V → + W →

Proof:

64 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

The four fundamental subspaces of a matrix

De!nition: The four fundamental subspaces of a matrix

Let 𝑂 ↑ R𝑃⇐𝑁 with c 𝑄 , 𝑄 = 1, . . .,𝑁, as its column vectors and r𝑅 , 𝑅 = 1, . . .,𝑃, as its row vectors. The four
fundamental subspaces of 𝑂 are

• Right null space: N (𝑂) = {x ↑ R𝑁 | 𝑂x = 0}

• Left null space: N (𝑂↓ ) = {y ↑ R𝑃 | 𝑂↓ y = 0}

• Column space: R(𝑂) = {y ↑ R𝑃 | 𝑂x = y for x ↑ R𝑁 } = span(c1, . . ., c𝑁 )

• Row space: R(𝑂↓ ) = {x ↑ R𝑁 | 𝑂↓ y = x for y ↑ R𝑃 } = span(r1, . . ., r𝑃 )

. -
1 2
Example 3. Let 𝑂 = . Find the four fundamental subspaces of 𝑂.
1 2

Column space and null space

For a visual intuition, watch this video on “Inverse matrices, column space, and null space” for 𝑁 ⇐𝑁
matrices. And, this video on “Nonsquare matrices as transformations between dimensions” for general
𝑃 ⇐𝑁 matrices.

65 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

Properties

Here are some properties relating the four fundamental subspaces of 𝑂 ↑ R𝑃⇐𝑁 :

(i) N (𝑂) → = R(𝑂↓ )

(ii) R(𝑂) → = N (𝑂↓ )

(iii) N (𝑂) ↗ R(𝑂↓ ) = R𝑁

(iv) R(𝑂) ↗ N (𝑂↓ ) = R𝑃

Proof

(i) N (𝑂) → = R(𝑂↓ )

Proof: Let x ↑ N (𝑂). So, we have that 𝑂x = 0. This is equivalent to y↓𝑂x = 0 for all y ↑ R𝑃 ,
which is equivalent to (𝑂↓y)↓x = (𝑂↓y) · x = 0. Thus, 𝑂x = 0 if and only if x is orthogonal
to all vectors of the form 𝑂↓y; that is, x ↑ R(𝑂↓) → . So, we conclude that N (𝑂) = R(𝑂↓) → ,
which is equivalent to N (𝑂) → = (R(𝑂↓) → ) → = R(𝑂↓).

(ii) R(𝑂) → = N (𝑂↓ )

Proof: We may use the same proof as above but using 𝑂↓ in place of 𝑂. That is, in the above
proof, we showed that N (𝑂) = R(𝑂↓) → . Replacing 𝑂 with 𝑂↓, we have N (𝑂↓) = R(𝑂) → .

(iii) N (𝑂) ↗ R(𝑂↓ ) = R𝑁

Proof: We have that R𝑁 = N (𝑂) ↗ N (𝑂) → . Using (i), we conclude that R𝑁 = N (𝑂) ↗ R(𝑂↓ ).

(iv) R(𝑂) ↗ N (𝑂↓ ) = R𝑃

Proof: We have that R𝑃 = R(𝑂) ↗ R(𝑂) → . Using (ii), we conclude that R𝑃 = R(𝑂) ↗ N (𝑂↓ ).

Example 4. Verify the above properties in the previous example.

66 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

𝐿𝑀 decomposition

Consider the 𝐿𝑀 decomposition of 𝑂; that is, 𝑂 = 𝐿𝑀 . We have that

(i) N (𝑂) = N (𝑀 )

(ii) N (𝑂↓ ) = N (𝐿 ↓ )

(iii) R(𝑂) = R(𝐿)

(iv) R(𝑂↓ ) = R(𝑀 ↓ )

Note: The above holds for any decomposition of the form 𝑂 = 𝑆𝑇 where 𝑆 is a matrix with linearly
independent columns and 𝑇 is a matrix with linearly independent rows. The 𝐿𝑀 decomposition is just one
speci!c example of this decomposition.

Proof:

67 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

Example 5. Given the following 𝐿𝑀 decomposition of the matrix 𝑂

5 2 3 1   1 0  - .
   5 2 3 1
  
𝑂 = 3 1 2 1  = 3/5 1  ,
3 2 1 ↔1 3/5 ↔4 0 ↔1/5 1/5 2/5
   
!nd the four fundamental subspaces of 𝑂.

68 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

The Rank-Nullity Theorem

De!nition: column rank, row rank, nullity

Let 𝑂 ↑ R𝑃⇐𝑁 .
• The number of linearly independent columns in 𝑂, dim(R(𝑂)), is called the column rank of 𝑂.

• The number of linearly independent rows in 𝑂, dim(R(𝑂↓ )), is called the row rank of 𝑂.

• The dimension of the null space of 𝑂, dim(N (𝑂)), is called the nullity of 𝑂.

Theorem

Let 𝑂 ↑ R𝑃⇐𝑁 . The linear map 𝑈 : N (𝑂) → ⇒ R(𝑂) de!ned by 𝑈 (v) = 𝑂v is bijective.

Proof

In order to show the map is bijective, we show that it is injective and surjective:

• injectivity: We want to show that the null space of 𝑈 is equal to {0}. That is, if v ↑ N (𝑂) →
with 𝑈 (v) = 0, then we have that v = 0.
Let x ↑ N (𝑂) → with 𝑈 (x) = 0. By de!nition, this implies 𝑂x = 0, and so, x ↑ N (𝑂). We have
that x ↑ N (𝑂) → and also x ↑ N (𝑂), so x ↑ N (𝑂) ≃ N (𝑂) → . But since N (𝑂) ≃ N (𝑂) → = {0}, we
conclude that x = 0. Thus, 𝑈 is injective.

• surjectivity: We want to show that the range of 𝑈 is equal to R(𝑂). That is, w ↑ R(𝑂) if and
only if w = 𝑈 (v) for some v ↑ N (𝑂) → .
If y ↑ R(𝑂), then y = 𝑂x for some x ↑ R𝑁 . Since R𝑁 = N (𝑂) ↗ N (𝑂) → , we have x = / x2 for
x1 +/
some / x1 ↑ N (𝑂) and /
x2 ↑ N (𝑂) → . So, we have that

y = 𝑂x = 𝑂(/
x1 +/
x2 ) = 𝑂/
x1 + 𝑂/
x2 = 0 + 𝑂/
x2 = 𝑂/
x2 = 𝑈 (/
x2 )

where we used the fact that 𝑂/ x1 = 0 since / x2 ) for some /

x1 ↑ N (𝑂). So, y = 𝑈 (/ x2 ↑ N (𝑂) → . So
we have that the range of 𝑈 is equal to R(𝑂). Thus, 𝑈 is surjective.

We showed that 𝑈 is injective and surjective; thus, 𝑈 is bijective.

Rank-Nullity Theorem

Let 𝑂 ↑ R𝑃⇐𝑁 . We have that

dim(N (𝑂)) + dim(R(𝑂)) = 𝑁.

69 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

Proof

By the previous theorem, since we showed that 𝑈 : N (𝑂) → ⇒ R(𝑂) is a bijective map, we conclude
that dim(N (𝑂) → ) = dim(R(𝑂)). We have that

N (𝑂) ↗ N (𝑂) → = R𝑁
dim(N (𝑂)) + dim(N (𝑂) → ) = dim(R𝑁 )
dim(N (𝑂)) + dim(R(𝑂)) = 𝑁

where in the last equality we used dim(N (𝑂) → ) = dim(R(𝑂)).

Theorem: column rank = row rank

Let 𝑂 ↑ R𝑃⇐𝑁 . We have that

dim(R(𝑂)) = dim(R(𝑂↓ ));

that is, column rank is equal to row rank.

Proof

Since we showed that 𝑈 : N (𝑂) → ⇒ R(𝑂) is a bijective map, we have that dim(N (𝑂) → ) = dim(R(𝑂)).
So we have

dim(R(𝑂)) = dim(N (𝑂) → ) = dim(R(𝑂↓ ))

where in the last equality we used dim(N (𝑂) → ) = dim(R(𝑂↓ )) since N (𝑂) → = R(𝑂↓ ).

Note: We denote dim(R(𝑂)) = dim(R(𝑂↓ )) = rank(𝑂), and we have that

rank(𝑂) ⇑ min{𝑃,𝑁}.

Invertible matrices

The matrix 𝑂 ↑ R𝑁⇐𝑁 is invertible when rank(𝑂) = 𝑁; we say the matrix has full rank.

Note: For a general matrix 𝑂 ↑ R𝑃⇐𝑁 , we say the matrix has full rank if rank(𝑂) = min{𝑃,𝑁}.

Note: If a matrix 𝑂 ↑ R𝑃⇐𝑁 with 𝑃 > 𝑁 has full rank (i.e. rank(𝑂) = 𝑁), then by the Rank-Nullity
Theorem we have

dim(N (𝑂)) = 𝑁 ↔ dim(R(𝑂)) = 𝑁 ↔𝑁 = 0 =⇓ N (𝑂) = {0}.

70 ©Lernik Asserian
This content is protected and may not be shared, uploaded, or distributed. II. System of Equations

Summary

The following !gure summarizes all the above results related to the four fundamental subspaces of a
matrix 𝑂 ↑ R𝑃⇐𝑁 . Recall that

• for all subspaces V of R𝑉 , we have that (V → ) → = V, and V ↗ V → = R𝑉 .

• N (𝑂) → = R(𝑂↓ )

• R(𝑂) → = N (𝑂↓ ) (note that this follows from applying the orthogonal complement to the
previous bullet point and using 𝑂↓ in place of 𝑂.)

• as special cases of V ↗ V → = R𝑉 , we have N (𝑂) ↗ N (𝑂) → = R𝑁 , and R(𝑂) ↗ R(𝑂) → = R𝑃 .

• N (𝑂) ↗ N (𝑂) → = R𝑁 is equivalent to N (𝑂) ↗ R(𝑂↓ ) = R𝑁

• R(𝑂) ↗ R(𝑂) → = R𝑃 is equivalent to R(𝑂) ↗ N (𝑂↓ ) = R𝑃 (note that this is the same as above
applied with 𝑂↓ in place of 𝑂.)

• rank-nullity: dim(N (𝑂)) + dim(R(𝑂)) = 𝑁

• column rank = row rank: dim(R(𝑂)) = dim(R(𝑂↓ ))

• The linear map 𝑈 : N (𝑂) → ⇒ R(𝑂) de!ned by 𝑈 (v) = 𝑂v is bijective.

Rn Rm
A
N
(A
)
↑
:r

R
r

A→
=

(A
=
))

r}
))
R

)
→

r}

(A
(A

y
(A

.,
(R
A
.,
(R

..
)

A
of
..

1,
m

of
di
1,

T
ce

{y
di
{x

ce
a
sp

a
sp
w
ro

!2
x
m

Ax
!2 = y
lu
co

Ax = y y

0 ↑ Rn !1 + x
x=x !2 !1 = 0
Ax 0 ↑ Rm
!1
x
le
ft
nu

nu
ll , . ) =
{x

l
di

sp . .

ls
r+
m

ac , x n →

pa
{y
(N

di
eo n

ce
m

r
(A

fA }

of
(N

1
,.
)

)
→
A
)

(A
(A

..

(A
→

,y
N

N
))

m
}
=

=
r

)↑
m

(A
→
r

71 ©Lernik Asserian