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.