4Matrices and linear equations

IA Vectors and Matrices

4.3 Homogeneous and inhomogeneous equations
Consider
Ax
=
b
where
A
is an
n ×n
matrix,
x
and
b
are
n ×
1 column vectors.
Definition
(Homogeneous equation)
.
If
b
=
0
, then the system is homogeneous.
Otherwise, it’s inhomogeneous.
Suppose
det A 6
= 0. Then there is a unique solution
x
=
A
1
b
(
x
=
0
for
homogeneous).
How can we understand this result? Recall that
det A 6
= 0 means that the
columns of
A
are linearly independent. The columns are the images of the stan-
dard basis,
e
0
i
=
Ae
i
. So
det A 6
= 0 means that
e
0
i
are linearly independent and
form a basis of
R
n
. Therefore the image is the whole of
R
n
. This automatically
ensures that b is in the image, i.e. there is a solution.
To show that there is exactly one solution, suppose
x
and
x
0
are both solutions.
Then
Ax
=
Ax
0
=
b
. So
A
(
x x
0
) =
0
. So
x x
0
is in the kernel of
A
. But
since the rank of
A
is
n
, by the rank-nullity theorem, the nullity is 0. So the
kernel is trivial. So x x
0
= 0, i.e. x = x
0
.
4.3.1 Gaussian elimination
Consider a general solution
A
11
x
1
+ A
12
x
2
+ ··· + A
1n
x
n
= d
1
A
21
x
1
+ A
22
x
2
+ ··· + A
2n
x
n
= d
2
.
.
.
A
m1
x
1
+ A
m2
x
2
+ ··· + A
mn
x
n
= d
m
So we have m equations and n unknowns.
Assume
A
11
6
= 0 (if not, we can re-order the equations). We can use the
first equation to eliminate
x
1
from the remaining (
m
1) equations. Then use
the second equation to eliminate
x
2
from the remaining (
m
2) equations (if
anything goes wrong, just re-order until things work). Repeat.
We are left with
A
11
x
1
+ A
12
x
2
+ A
13
x
3
+ ··· + A
1n
x
n
= d
1
A
(2)
22
x
2
+ A
(2)
23
x
3
+ ··· + A
(2)
2n
x
n
= d
2
.
.
.
A
(r)
rr
x
r
+ ··· + A
(r)
rn
x
n
= d
r
0 = d
(r)
r+1
.
.
.
0 = d
(r)
m
Here
A
(i)
ii
6
= 0 (which we can achieve by re-ordering), and the superfix (
i
) refers
to the “version number” of the coefficient, e.g.
A
(2)
22
is the second version of the
coefficient of x
2
in the second row.
Let’s consider the different possibilities:
(i) r < m
and at least one of
d
(r)
r+1
, ···d
(r)
m
6
= 0. Then a contradiction is
reached. The system is inconsistent and has no solution. We say it is
overdetermined.
Example. Consider the system
3x
1
+ 2x
2
+ x
3
= 3
6x
1
+ 3x
2
+ 3x
3
= 0
6x
1
+ 2x
2
+ 4x
3
= 6
This becomes
3x
1
+ 2x
2
+ x
3
= 3
0 x
2
+ x
3
= 6
0 2x
2
+ 2x
3
= 0
And then
3x
1
+ 2x
2
+ x
3
= 3
0 x
2
+ x
3
= 6
0 = 12
We have d
(3)
3
= 12 = 0 and there is no solution.
(ii)
If
r
=
n m
, and all
d
(r)
r+i
= 0. Then from the
n
th equation, there
is a unique solution for
x
n
=
d
(n)
n
/A
(n)
nn
, and hence for all
x
i
by back
substitution. This system is determined.
Example.
2x
1
+ 5x
2
= 2
4x
1
+ 3x
2
= 11
This becomes
2x
1
+ 5x
2
= 2
7x
2
= 7
So x
2
= 1 and thus x
1
= 7/2.
(iii)
If
r < n
and
d
(r)
r+i
= 0, then
x
r+1
, ···x
n
can be freely chosen, and there
are infinitely many solutions. System is under-determined. e.g.
x
1
+ x
2
= 1
2x
1
+ 2x
2
= 2
Which gives
x
1
+ x
2
= 1
0 = 0
So x
1
= 1 x
2
is a solution for any x
2
.
In the
n
=
m
case, there are
O
(
n
3
) operations involved, which is much less than
inverting the matrix. So this is an efficient way of solving equations.
This is also be related to the determinant. Consider the case where
m
=
n
and
A
is square. Since row operations do not change the determinant and
swapping rows give a factor of (1). So
det A = (1)
k
A
11
A
12
··· ··· ··· A
1n
0 A
(2)
22
··· ··· ··· A
(n)
2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· A
(r)
rr
··· A
(n)
rn
0 0 ··· 0 0 ···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
This determinant is an upper triangular one (all elements below diagonal are 0)
and the determinant is the product of its diagonal elements.
Hence if
r < n
(and
d
(r)
i
= 0 for
i > r
), then we have case (ii) and the
det A = 0. If r = n, then det A = (1)
k
A
11
A
(2)
22
···A
(n)
nn
6= 0.