Calculate the determinant of each of the following matrices. Hence, identify which matrices are invertible and for each invertible matrix calculate its inverse.

(i). $A = \pmatrix{\;\;\,2 & -1 \\ -2 & \;\;\,1}$ (ii). $B = \pmatrix{7 & 3 \\ 2 & 1}$

(iii). $C = \pmatrix{0 & 1 \\ 0 & 1}$ (iv). $M = \pmatrix{\;\;\,2 & \;\;\,0 \\ -2 & -3}$

Solution

(i). $det(A) = 2 \times 1 - (-1) \times (-2) = 2 - 2 = 0$. No Inverse.

(ii). $det(B) = 7 \times 1 - 3 \times 2 = 7 - 6 = 1 \neq 0$. Matrix has an inverse.

$B^{-1} = \ {\Large\frac{1}{1}}\pmatrix{\;\;\,1 & -3 \\ -2 & \;\;\,7}$

$=\pmatrix{\;\;\,1 & -3 \\ -2 & \;\;\,7}$

Exercise: Check that $BB^{-1} = B^{-1}B = I$ .

(iii). $det(C) = 0 \times 1 - 1 \times 0 = 0 - 0 = 0$. No inverse.

(iv). $det(M) = 2 \times (-3) - 0 \times (-2) = -6 \neq 0$.

$M^{-1} = -{\Large\frac{1}{6}}\pmatrix{-3 & 0 \\ \;\;\,2 & 2}$

$= {\Large\frac{1}{6}}\pmatrix{\;\;\,3 & \;\;\,0 \\ -2 & -2}$

Exercise: Check that $MM^{-1} = M^{-1}M = I$.

The calculation of inverses for square matrices larger than $2 \times 2$ is considerably more involved and is beyond the scope of this course.

If $A = \pmatrix{a & b \\ c & d}$ and $ad - bc \neq 0$ show that $AA^{-1} = I$.

Solution

$AA^{-1} = {\Large\frac{1}{ad - bc}}\pmatrix{a & b \\c & d}\pmatrix{\;\;\,d & -b \\ -c & \;\;\,a}$

$= {\Large\frac{1}{ad - bc}}\pmatrix{ad-bc & -ab+ba \\ cd-dc & \;\;\,ad-bc}$

$= {\Large\frac{1}{ad - bc}}\pmatrix{ad-bc & \;\;0 \\ \;\;0 & ad-bc}$

$= \pmatrix{1 & 0 \\ 0 & 1} = I$ as required.

Consider the matrix equation

$\pmatrix{2 & \;\;6 \\ 4 & 10}\pmatrix{a & b \\ c & d} = \pmatrix{4 & 8 \\ 0 & 4}$.

Determine the values of $a, b, c$ and $d$.

Solution

let $A = \pmatrix{2 & \;\;6 \\ 4 & 10}$. Determine $A^{-1}$ and multiply both sides of the equation by $A^{-1}$.

Here $A^{-1} = -{\Large\frac{1}{4}}\pmatrix{\,10 & -6 \\ -4 & \;\;\,2} = {\Large\frac{1}{4}}\pmatrix{-10 & \;\;\;6 \\ \;\;\;4 & -2}$ and so we have

$\pmatrix{a & b \\ c & d} = {\Large\frac{1}{4}}\pmatrix{-10 & \;\;\,6 \\ \;\;\,4 & -2}\pmatrix{4 & 8 \\ 0 & 4}$

$= {\Large\frac{1}{4}}\pmatrix{-40 & -56 \\ \;\;\,16 & \;\;\,24}$

$= \pmatrix{-10 & -14 \\ \;\;\;4 & \;\;\;6}$

Hence, $=\;$ $a=-10$, $b=-14$, $c=4$, $d=6$.

Exercise: An alternative approach involves expanding the matrix equation to obtain a system of simultaneous equations. Use this method to verify the above results.

(i). Solve the system of simultaneous equations

$x + 2y = -1$

$4x - 3y = 18$

using matrix methods.

Solution

First write the equations in the matrix form, $A \underline{x} = \underline{b}$:

$\pmatrix{1 & \;\;\,2 \\ 4 & -3}\pmatrix{x \\ y} = \pmatrix{-1 \\ 18}$

Calculate $A^{-1}$ if it exists.

$det(A) = 1 \times (-3) - 2 \times 4 = -11 \neq 0$ and so the matrix is invertible.

Hence,

$A^{-1} = -{\Large\frac{1}{11}}\pmatrix{-3 & -2 \\ -4 & \;\;\,1} = {\Large\frac{1}{11}}\pmatrix{3 & \;\;\,2 \\ 4 & -1}$

Now solve the system by forming, $\underline{x} = A^{-1} \underline{b}$.

$\pmatrix{x \\ y} = {\Large\frac{1}{11}}\pmatrix{3 & \;\;\,2 \\ 4 & -1}\pmatrix{-1 \\ \;18} = {\Large\frac{1}{11}}\pmatrix{\;\;\,33 \\ -22} = \pmatrix{\;\;\,3 \\ -2}$

Hence, $x=3$ and $y=-2$ as we obtained in Unit 1.

(ii). Solve the system of simultaneous equations

$4x + 2y = 10$

$3x - 7y = -1$

using matrix methods.

Solution

First write the equations in the matrix form, $A \underline{x} = \underline{b}$:

$\pmatrix{4 & \;\;\,2 \\ 3 & -7}\pmatrix{x \\ y} = \pmatrix{\;\;10 \\ -1}$

Calculate $A^{-1}$ if it exists.

$det(A) = -28 - 6 = -34 \neq 0$ and so the matrix is invertible.

Hence,

$A^{-1} = -{\Large\frac{1}{34}}\pmatrix{-7 & -2 \\ -3 & \;\;\,4} = {\Large\frac{1}{34}}\pmatrix{7 & \;\;\,2 \\ 3 & -4}$

Now solve the system by forming, $\underline{x} = A^{-1}\underline{b}$.

$\pmatrix{x \\ y}={\Large\frac{1}{34}}\pmatrix{7 & \;\;\,2 \\ 3 & -4}\pmatrix{\;\;10 \\ -1}= {\Large\frac{1}{34}}\pmatrix{68 \\ 34} = \pmatrix{2 \\ 1}$

Hence, $x=2$ and $y=1$.

A system of two simultaneous equations is given by

$3x + 5y = 8$

$7x - 4y = 50$

(i). Express these simultaneous equations in the form

$A\underline{x} = \underline{b}$

where $A$ is a $2 \times 2$ matrix, $\underline{b}$ is a $2 \times 1$ matrix and $\underline{x} = \pmatrix{x \\ y}$.

(ii). Determine the inverse of $A$.

(iii). Hence, solve the system of simultaneous equations.

Solution

(i). In matrix form we have, $\pmatrix{3 & \;\;\,5 \\ 7 & -4}\pmatrix{x \\ y} = \pmatrix{\;\;\,8 \\ 50}$

(ii). $det(A) = -12 - 35 = -47 \neq 0$ and so $A^{-1}$ exists.

$A^{-1} = -\frac{1}{47}\pmatrix{-4 & -5 \\ -7 & \;\;\,3} = \frac{1}{47}\pmatrix{4 & \;\;\,5 \\ 7 & -3}$

(iii). $\underline{x} = A^{-1}\underline{b}$

$\pmatrix{x \\ y} = \frac{1}{47}\pmatrix{4 & \;\;\,5 \\ 7 & -3}\pmatrix{\;\,8 \\ 50} = \frac{1}{47}\pmatrix{\;282 \\ -94} = \pmatrix{\;\;\,6 \\ -2}$

$x=6$,$y=-2$

Suppose we want to encode the four digit PIN: $1 0 4 9$.

Record this information in a $2 \times 2$ matrix $P$ as, $P = \pmatrix{1 & 4 \\ 0 & 9}$.

Encode the PIN by multiplying $P$ on the left by a key matrix $E$ where, say, $E = \pmatrix{3 & 1 \\ 2 & 1}$

The matrix $C$, containing the enciphered PIN, is then

$C = EP = \pmatrix{3 & 1 \\ 2 & 1}\pmatrix{1 & 4 \\ 0 & 9} = \pmatrix{3 & 21 \\ 2 & 17}$.

The sender transmits this information to the receiver who knows the coding matrix $E$.

To decipher the coded PIN the receiver uses the inverse of the matrix $E$, i.e.

$E^{-1} = \pmatrix{\;\;\,1 & -1 \\ -2 & \;\;\,3}$

Then

$E^{-1}C = \pmatrix{\;\;\,1 & -1 \\ -2 & \;\;\,3}\pmatrix{3 & 21 \\ 2 & 17} = \pmatrix{1 & 4 \\ 0 & 9} = P$

This approach works since

$E^{-1}C = E^{-1}EP = IP = P$.

A message is converted into numeric form by defining,

$A = 0, B = 1, .... , Y = 24, Z = 25$.

The message is then encrypted using the matrix

$E = \pmatrix{1 & 2 \\ 4 & 3}$.

Determine the ciphertext that represents encryption of the message, CODE.

Solution

From the look-up table we find that the word CODE is represented numerically by

$2, \;\;\; 14, \;\;\; 3, \;\;\; 4. $

Divide into blocks of length 2 giving the column vectors $\pmatrix{\;\,2 \\ 14}$ and $\pmatrix{3 \\ 4}$.

To simplify subsequent calculations we form a matrix, $P$, whose columns consist of these vectors,

$P = \pmatrix{\;\,2 & 3 \\ 14 & 4}$

Encrypt the message by multiplying $P$ on the left by the encryption matrix $E$. Note that we could equally well multiply $P$ on the right by $E$ to obtain a different ciphertext.

The matrix $C$ containing the numerical values corresponding to the ciphertext for the word CODE is then

$C = EP = \pmatrix{1 & 2 \\ 4 & 3}\pmatrix{\;\,2 & 3 \\ 14 & 4} = \pmatrix{30 & 11 \\ 50 & 24 }$

Reading the values from $C$ we have,

$30 \;\;\; 50 \;\;\; 11 \;\;\; 24$.

Operating modulo 26, these values become, $4 \;\; 24 \;\; 11 \;\; 24$.

From the look-up table given above the ciphertext for the message CODE is, EYLY.

Note: To decrypt a ciphertext, constructed using a Hill cipher, we use the inverse matrix $E^{-1}$ operating with modular arithmetic.

Use the binary parity check matrix

$H = \pmatrix{1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1}$

to calculate the error syndrome associated with the vectors

$\pmatrix{1 & 1 & 1 & 0 & 0 & 0}^T$ and $\pmatrix{0 & 1 & 1 & 1 & 1 & 0}^T$.

Hence, identify which of the two is a valid codeword as recognised by the parity check.

Note that this example is for illustration purposes and is therefore optional.

Solution

As we have a binary check matrix we operate modulo 2, i.e.

$\pmatrix{1 & 1 & 0 & 1 & 0 & 0 \\0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1}\pmatrix{1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0} = \pmatrix{0 \\ 0 \\ 0}$

and $\pmatrix{1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1}\pmatrix{0 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0} = \pmatrix{0 \\ 1 \\ 1}$.

The first is a valid codeword since it multiplies to the zero vector.

A rectangle has its vertices at the points $A(2, 1)$, $B(5, 1)$, $C(5, 3)$ and $D(2, 3)$. Find the coordinates of the image of the rectangle when it is reflected in the line $x = 0$, i.e. the $y$-axis.

Solution

The matrix for a reflection in the line $x = 0$ is given by

$Q = \pmatrix{-1 & 0 \\ \;\;\,0 & 1}$.

(Note that derivation of the reflection matrix is beyond the scope of this course).

We now form a matrix $M$, say, from the coordinates of the rectangle, i.e.

$M = \pmatrix{2 & 5 & 5 & 2 \\ 1 & 1 & 3 & 3}$

Next evaluate the product of the reflection and coordinate matrices as,

$QM = \pmatrix{-1 & 0 \\ \;\;\,0 & 1}\pmatrix{2 & 5 & 5 & 2 \\ 1 & 1 & 3 & 3} = \pmatrix{-2 & -5 & -5 & -2 \\ \;\;\,1 & \;\;\,1 & \;\;\,3 & \;\;\,3}$

The resulting matrix gives the coordinates of the reflected rectangle which is shown in the diagram. Note that these coordinates appear in the same order as they do in the original matrix so, for example, the point $A(2, 1)$ is mapped to the point $A^{'}(-2, 1)$ , etc.

A rectangle has its vertices at the points $A(2, 1)$, $B(5, 1)$, $C(5, 3)$ and $D(2, 3)$. Find the coordinates of the image of the rectangle when it is rotated through 900 anticlockwise about the origin.

Solution

The matrix for a 900 anticlockwise rotation about the origin is given by

$R = \pmatrix{0 & -1 \\ 1 & \;\;\,0}$.

(Note that derivation of the rotation matrix is beyond the scope of this course).

We now form a matrix $M$, say, from the coordinates of the rectangle, i.e.

$M = \pmatrix{2 & 5 & 5 & 2 \\ 1 & 1 & 3 & 3}$.

Now evaluate the product of the rotation and coordinate matrices as,

$RM = \pmatrix{0 & -1 \\ 1 & \;\;\,0}\pmatrix{2 & 5 & 5 & 2 \\ 1 & 1 & 3 & 3} = \pmatrix{-1 & -1 & -3 & -3 \\ \;\;\,2 & \;\;\,5 & \;\;\,5 & \;\;\,2}$.

The resulting matrix gives the coordinates of the vertices of the rotated rectangle which is shown in the diagram. Note that these coordinates appear in the same order as they do in the original matrix so, for example, the point $A(2, 1)$ is mapped to the point $A^{'} (-1, 2)$ , etc.

Consider the following graph which shows the number of direct flights per day, regardless of direction, between four cities $P$, $Q$, $R$ and $S$. The cities are represented by nodes and any two cities that are connected by a direct flight are connected by a line called an edge. For example, there are two flights per day between $P$ and $S$ but no daily direct flights between $S$ and $R$.

There are a number of ways to represent the information in this graph on a computer, including forming an edge list, or an adjacency list or, of particular interest here, an adjacency matrix. Each method has advantages and disadvantages as regards demands on computing memory and runtime. We briefly look at the adjacency matrix approach which employs a matrix to record whether or not nodes are connected to each other.

If $G$ is a graph with $n$ vertices its adjacency matrix, $A$ is defined as the $n \times n$ matrix whose $ij$-th entry is the number of edges joining node $i$ and node $j$.

As our graph contains four nodes we will have a $4 \times 4$ adjacency matrix with the first row, corresponding to node $P$, being constructed as follows:

0 edges connect node $P$ to node $P$, so the entry in Row1/Column1 is a ‘0’

1 edge connects node $P$ to node $Q$, so the entry in Row1/Column2 is a ‘1’

0 edges connect node $P$ to node $R$, so the entry in Row1/Column3 is a ‘0’

2 edges connect node $P$ to node $S$, so the entry in Row1/Column4 is a ‘2’

Continuing in this way, for each node in turn, we obtain the following adjacency matrix:

$\matrix{P \;\; Q \;\;\, R \;\;\; S}$

$A = \matrix{P \\ Q \\ R \\ S}\pmatrix{0 & 1 & 0 & 2 \\1 & 0 & 1 & 1 \\0 & 1 & 0 & 0 \\2 & 1 & 0 & 0}$.

It can be seen that $A$ is a symmetric matrix.

Note that when the number of edges and nodes in a graph are small, as was the case here, it is relatively easy to show relationships in graphical form. However, as graphs become large it is no longer feasible to display them visually and so options like an adjacency matrix are invaluable.