Description

a a a
c c
a a
am
11 a21 am1 x1
⎣a n a n ⋯ amn ⎦
a11x1 a21x2 am1xm
⎣ a nx a nx amnxm Therefore, we have
a1Tx = 0, a2Tx = 0
⋮
anTx = 0 Now, yTx = (c1a1 + c2a2 + ⋯ + cnan)Tx = (c1a1Tx + c2a2Tx + ⋯ + cnanTx) = 0
But,
yTx = y ⋅ x = 0
This is nothing but the dot product of any vector y lying in the column space of A and any vector x lying in the left null space of A. Since the dot product is 0 for any pair of such vectors y,x, the column space of a matrix is orthogonal to its left null space.
□
We consider the system of linear equations given by:
⎡1 2 2 1⎤⎡x1⎤ ⎡1⎤
2 1 1 2 x2 = 1
2 1 2 1 x3 1
⎣1 2 1 2⎦⎣x4⎦ ⎣1⎦
a) To solve this system of linear equations using Gaussian Elimination, we perform the following row operations.
R2 → R2 − 2R1
R3 → R3 − 2R1 R4 → R4 − R1
Thus, we get the following:
⎡1 2 2 1 ⎤⎡x1⎤ ⎡ 1 ⎤
0 −3 −3 0 x2 −1
=
0 −3 −2 −1 x3 −1
⎣0 0 −1 1 ⎦⎣x4⎦ ⎣ 0 ⎦
In the next step, we perform R3 → R3 − R2 to get the following result:
⎡1 2 21 ⎤⎡x1⎤⎡ 1 ⎤
0 −3 −3 0 x2−1
=
0 0 1−1 x30
⎣0 0 −1 1 ⎦⎣x4⎦⎣ 0 ⎦
Further, we perform R4 → R4 + R3 to get:
⎡1 2 21 ⎤⎡x1⎤⎡ 1 ⎤
0 −3 −3 0 x2−1
=
0 0 1−1 x30
⎣0 0 00 ⎦⎣x4⎦⎣ 0 ⎦
As we can see, one of the equations is redundant since it becomes 0 = 0. Hence, the system of equations has infinitely many solutions. Here, the valid equations are:
x1 + 2×2 + 2×3 + x4 =1 3×2 + 3×3 =1 x3 =x4
Hence, to find the parametric solution, we use x3 = x4 =α and get:

x1= x2= x3= α x4= α
where α ∈ R
b) In the first step, we performed the following set of row operations
R2→ R2 − 2R1
R3→ R3 − 2R1 R4→ R4 − R1
Hence, the corresponding matrix is:
⎡ 1 0 0 0⎤ −2 1 0 0
T1 =
−2 0 1 0
⎣−1 0 0 1⎦
In the second step, we performed the operation:
R3→ R3 − R2
⎡1 0 0 0⎤ 0 1 0 0
T2 =
0 −1 1 0
⎣0 0 0 1⎦
Similarly, for the final step, the operation performed is:
R4 → R4 + R3
⎡1 0 0 0⎤
0 1 0 0
T3 = 0 0 1 0
⎣0 0 1 1⎦
Thus, to find the corresponding matrix,
T = T3T2T1
⎡1 0 0 0⎤⎡1 0 0 0⎤⎡ 10 0 0⎤
0 1 0 0 0 1 0 0 −21 0 0
=
0 0 1 0 0 −1 1 0 −20 1 0
⎣0 0 1 1⎦⎣0 0 0 1⎦⎣−10 0 1⎦
⎡ 1 0 0 0⎤
−2 1 0 0
=
0 −1 1 0
⎣−1 −1 1 1⎦
c) To find the Null Space of the matrix:
⎡1 2 2 1⎤⎡x1⎤ ⎡0⎤
2 1 1 2 x2 0
=
2 1 2 1 x3 0
⎣1 2 1 2⎦⎣x4⎦ ⎣0⎦
Applying similar Gaussian Elimination as seen in part (a), we get:
⎡1 2 2 1 ⎤⎡x1⎤ ⎡0⎤
0 −3 −3 0 x2 =0
⎣00 00 01 −01⎦⎣xx34⎦ ⎣00⎦
Here, we can see that one of the equations is redundant i.e. 0= 0. The other equations that we get are:
x1 + 2×2 + 2×3 + x4 = 0 3×2 + 3×3 = 0 x3 = x4
On using x3 = x4 = α, we get the following solution in the parametric form:
x1 = −α x2 = −α x3 = α x4 = α Hence, the null space contains all the vectors of the form
v = α[−1 −1 1 1]T
where α is a constant.
d)
⎡1 2 2 1⎤⎡x1⎤ ⎡1⎤
2 1 1 2 x2 2
=
2 1 2 1 x3 3
⎣1 2 1 2⎦⎣x4⎦ ⎣4⎦
Using similar row operations as performed in earlier parts, we get:
⎡1 2 2 1 ⎤⎡x1⎤ ⎡1⎤
0 −3 −3 0 x2 0
=
0 0 1 −1 x3 1
⎣0 0 0 0 ⎦⎣x4⎦ ⎣4⎦
Here, one of the equations that we get is 0 = 4, which is not possible. Hence, we can say that NO solutions exist for this case.
The column space of A ∈ Rm×n is defined as
C(A) := {Ax|x ∈ Rn}
and the left null space is defined as
N(AT) := {x ∈ Rm|ATx = 0}
Both, C(A) and N(AT) are subspaces of Rm. Along with that, we have proved in question
(2) that C(A) and N(AT) are orthogonal to each other.
Let rank(A) = r = dim(C(A))- then we can define an orthogonal basis {b1,⋯,br} spanning the column space of A.
As C(A) is a subspace of Rm, we extend the above orthogonal basis such that {b1,⋯,br,br+1,⋯,bm} is an orthogonal basis of Rm.
As any vector perpendicular to the column space of A belongs to the left null space of AT, and as the vectors br+1,⋯,bm are perpendicular to the basis vectors of column space of A, we can say that {br+1,⋯,bm} is an orthogonal basis of N(AT).
Thus, we have
dim(C(A)) + dim(N(AT)) = m
⟹ rank(A) + dim(N(AT)) = m
⟹ dim(N(AT)) = m − r
Using rank nullity theorem we have
rank(AT) = m − dim(N(AT))
= m − (m − r)
= r
= rank(A)
□
Let x ∈ N(A) where N(A) is the null space for the matrix A. Then,
Ax = 0
⟹ ATAx = 0
⟹ x ∈ N(ATA)
As ∀x ∈ N(A) we have x ∈ N(ATA) implying N(A) ⊆ N(ATA).
Let x ∈ N(ATA) then
ATAx = 0
⟹ xTATAx = 0
⟹ (Ax)T (Ax) = 0
⟹ Ax = 0
⟹ x ∈ N(A)
As ∀x ∈ N(ATA) we have x ∈ N(A) implying N(ATA) ⊆ N(A).
Thus, N(A) = N(ATA).
Using rank nullity theorem we have
rank(A) = n − dim(N(A))
rank(ATA) = n − dim(N(ATA))
= n − dim(N(A))
Thus,
rank(A) = rank(ATA) = rank(AT) = rank(AAT)
□