Assignment 4   -   Solutions

Find the basic solutions of the homogeneous linear system AX = O, where

Show that     is a solution to the inhomogeneous system   AX = B, where   .
Hence write down the general solution of   AX = B.

Carry the coefficient matrix   A   to reduced row-echelon form by elementary row operations:



The leading variables are   x₁, x₄ and x₆.
The other three variables are free parameters:
x₂ = s,   x₃ = t     and   x₅ = u,   (where s, t and u are any real numbers).
The solution set for the homogeneous linear system can be read from the reduced row-echelon form as

The general solution for the homogeneous system is therefore

The set of basic solutions then follows immediately:

Substituting the given vector   X_p   into the expression   AX   we find

The vector     is therefore a solution to the inhomogeneous system   AX = B
This immediately tells us that the inhomogeneous system is consistent.
The complete solution is the sum of this particular solution   X_p   to the inhomgeneous system with the general solution   X_h   to the associated homogeneous system:

Find   A ^-1   and hence solve   AX = B, where  

This inverse is easily verified by showing that   A^-1A = I   or   A A^-1 = I.
The unique solution to the linear system   AX = B is

Use block multiplication to find   AB , where

Therefore

Use block multiplication to find   C ^-1,

One may verify this answer by direct matrix multiplication:

Directed Graphs   (Textbook, page 46)

Adam Ant is visiting his four aunts at their homes that are connected by twigs as shown in this directed graph:

There is only one twig connecting homes A and B in each direction. Similarly, there is one twig connecting homes B and C in each direction. There is one twig connecting homes D and A in each direction. However, Adam can travel along the other two twigs only in the directions indicated. In the terminology of directed graphs, each aunt’s home is a vertex and each twig is an edge. We can set up an adjacency matrix A to represent this information. If there is an edge from vertex j to vertex i, then the entry aij (in the ith row and jth column of the matrix A) is a '1'. If there is no edge, then the entry is a zero.

Write down the adjacency matrix   A   for Adam Ant.

Furthermore, an r-path (or path of length r) from vertex j to vertex i is a sequence of r edges that starts at vertex j and ends at vertex i.   The 2-paths for Adam that start at home A and end at home C are:

From:	via:	to:
A	C	C
A	B	C

There are two 2-paths from A to C, so that the entry in row 3, column 1 of the associated matrix is '2'.
Extend this table to find all 2-paths and hence show that the adjacency matrix for 2-paths is
       
Also show that this matrix is the square of the matrix A.

From:

via:

to:

From:

via:

to:

From:

via:

to:

From:

via:

to:

A

B

A

B

A

B

C

B

A

D

A

B

A

B

C

B

A

C

C

B

C

D

A

C

A

C

B

B

A

D

C

C

B

D

A

D

A

C

C

B

C

B

C

C

C

A

D

A

B

C

C

From this table, we see that from home A there is a total of five 2-paths, two of which go back to A, one to B, two to C and none to D.   This is the first column of the adjacency matrix for 2-paths.   The other three columns can be calculated in the same way.

In general the adjacency matrix for r-paths is just A^r.
Find the number of 3-paths from home C to itself and list all such paths.

The number of 3-paths from home C to itself is just the (3,3) entry in the matrix A³, which is the dot product of row 3 of A² with column 3 of A (or vice versa).   It is therefore necessary to evaluate only one of the sixteen elements of A³ !

These four 3-paths from home C to itself are:

C-B-A-C   C-B-C-C   C-C-B-C   C-C-C-C

Use Gaussian elimination to find the inverse matrix of

(if possible; otherwise to show that no such inverse exists).

It is straightforward to verify that

Use Gaussian elimination to find the inverse matrix of

(if possible; otherwise to show that no such inverse exists).

At this point we can deduce that the inverse does not exist.
The fact that rows 3 and 4 of the left hand matrix are identical tells us that the row-echelon form will have a row of all zeros in row 4.   Matrix G will therefore not reduce to the identity matrix I.   Continuing with the row operations,


and now the impossibility of carrying matrix G to matrix I   by elementary row operations is obvious.   Therefore

G-1   does not exist

Use Gaussian elimination to find the inverse matrix of

(if possible; otherwise to show that no such inverse exists).

One can verify that   H^-1H = H H^-1 = I